Méthodes numériques avancées

Fiches de cours et sous-notions liées à ce chapitre.

Pas assez de questions pour un entraînement ciblé sur cette notion.

Méthodes multigrilles

Non commencé

Définitions

Multigrille (MG) résout $Au=b$ en combinant lissage (Jacobi/GS élimine hautes fréquences) et correction grossière (erreur basse fréquence sur maillage grossier). Cycle V/W : descendre niveaux, remonter avec prolongation + correction.

Complexité idéale $O(N)$ pour Laplacien. Prolongation/restriction entre grilles. Paramètres : nb pre/post-smoothing, niveaux. Méthode géométrique vs algébrique (AMG).

Multigrilles : résoudre sur maillages grossiers pour corriger les modes lisses de l'erreur ; cycles V/W. Accélère les solveurs elliptiques.

Complexité proche de $O(N)$ pour Poisson.

Pourquoi c’est central : cette notion structure les preuves et calculs du programme ; maîtriser définitions et hypothèses évite les applications hors cadre.

Formules

$u^{k+1} = S^\nu u^k + C(b - Au^k) \quad \text{(cycle MG)}$
$\text{Erreur haute fréq. : lissée rapidement}$
$\text{Erreur basse fréq. : corrigée sur grille grossière}$
$\text{Complexité : } O(N) \text{ si } \rho < 1 \text{ indépendant de } h$

Exemples

Exemple 1

Pourquoi le lissage ?

Méthode

(1) Lire l'énoncé et repérer les hypothèses / la forme utile. (2) Gauss-Seidel amortit bien les hautes fréquences ; les basses restent → grille grossière. (3) Vérifier le résultat (ordre de grandeur, cas particulier, ou dérivation/substitution).

Résultat

Lisser HF, corriger BF au grossier.

Exemple 2

Coût cible.

Méthode

(1) Lire l'énoncé et repérer les hypothèses / la forme utile. (2) Pour $N$ inconnues, viser $O(N)$ au lieu de $O(N^{1.5})$ direct sparse 2D. (3) Vérifier le résultat (ordre de grandeur, cas particulier, ou dérivation/substitution).

Résultat

Idéal $O(N)$ .

À retenir

Solveurs haute performance

Non commencé

Définitions

Solveurs haute performance (HPC) : parallélisation MPI (mémoire distribuée), OpenMP (shared memory), GPU (CUDA). Décomposition domaine : sous-domaines + échange ghost cells. Préconditionneurs parallèles (ILU, multigrille).

Scalabilité faible/forte. BLAS/LAPACK, PETSc, Trilinos. GMRES/CG parallèles pour systèmes creux $10^8$ – $10^{10}$ inconnues. ILU(0) : factorisation incomplète préconditionneur.

Solveurs HPC : parallélisme (MPI/OpenMP), Krylov + préconditionneurs (ILU, multigrid), scalabilité forte/faible.

Mémoire, communication, équilibrage de charge.

Pourquoi c’est central : cette notion structure les preuves et calculs du programme ; maîtriser définitions et hypothèses évite les applications hors cadre.

Formules

$T_{\mathrm{par}} = T_{\mathrm{seq}}/p + T_{\mathrm{comm}}$
$\text{Speedup } S(p) = T_1 / T_p$
$\text{Efficiency } E(p) = S(p)/p$
$\text{GMRES : Krylov } \mathcal{K}_m(A,r_0) \text{ avec précond. } M^{-1}$

Exemples

Exemple 1

Scalabilité forte.

Méthode

(1) Lire l'énoncé et repérer les hypothèses / la forme utile. (2) Fixer $N$ , augmenter procs : temps $\searrow$ jusqu'à saturation communication. (3) Vérifier le résultat (ordre de grandeur, cas particulier, ou dérivation/substitution).

Résultat

Speedup limité par Amdahl / comm.

Exemple 2

Préconditionneur.

Méthode

(1) Lire l'énoncé et repérer les hypothèses / la forme utile. (2) Réduire $\kappa$ effectif pour CG/GMRES : moins d'itérations. (3) Vérifier le résultat (ordre de grandeur, cas particulier, ou dérivation/substitution).

Résultat

ILU / AMG courants.