Méthodes des sous-espaces de Krylov

Les méthodes des sous-espaces de Krylov résolvent les grands systèmes linéaires creux en extrayant la meilleure approximation du sous-espace généré par des produits matrice-vecteur répétés, ne nécessitant que l'action de la matrice plutôt que ses éléments.

Definition

Une méthode des sous-espaces de Krylov est un solveur itératif qui, à la m-ième étape, recherche une solution approchée dans le sous-espace de Krylov de dimension m engendré par le résidu et ses images successives par la matrice, en choisissant l'itéré par une condition de projection ou de minimisation.

Scope

Ce thème couvre le sous-espace de Krylov et sa construction par les processus d'Arnoldi et de Lanczos, la méthode du gradient conjugué pour les systèmes symétriques définis positifs, MINRES et GMRES pour les matrices symétriques indéfinies et générales, les méthodes de biorthogonalisation telles que BiCGSTAB, ainsi que la théorie de la convergence reliant le nombre d'itérations au spectre et au nombre de conditionnement.

Core questions

• Qu'est-ce que le sous-espace de Krylov, et comment une base orthonormée pour celui-ci est-elle construite de manière stable ?
• Pourquoi la méthode du gradient conjugué est-elle optimale et à récurrence courte pour les systèmes symétriques définis positifs ?
• Comment GMRES gère-t-il les systèmes non symétriques généraux, et pourquoi nécessite-t-il un stockage croissant ?
• Comment les propriétés spectrales de la matrice déterminent-elles le taux de convergence ?

Key theories

Méthode du gradient conjugué

Pour les systèmes symétriques définis positifs, la méthode du gradient conjugué minimise la norme d'énergie de l'erreur sur le sous-espace de Krylov en utilisant une récurrence courte à trois termes, convergeant en au plus n étapes en arithmétique exacte et beaucoup plus rapidement lorsque les valeurs propres sont regroupées.

GMRES et le processus d'Arnoldi

Pour les matrices générales, GMRES utilise le processus d'Arnoldi pour construire une base de Krylov orthonormée et minimise la norme du résidu sur le sous-espace, mais comme il n'existe pas de récurrence courte en général, il doit stocker tous les vecteurs de base, ce qui motive les variantes redémarrées.

Mechanisms

Chaque méthode multiplie de manière répétée un vecteur par la matrice pour étendre le sous-espace de Krylov et orthogonalise la nouvelle direction par rapport aux précédentes. Pour les matrices symétriques, le processus de Lanczos produit une projection tridiagonale et une récurrence courte, de sorte que les méthodes du gradient conjugué et MINRES ne nécessitent que le stockage de quelques vecteurs. Pour les matrices non symétriques, le processus d'Arnoldi génère une projection de Hessenberg supérieure complète, et GMRES minimise le résidu en résolvant un petit problème de moindres carrés à chaque étape, au prix du stockage de toute la base ; le redémarrage limite ce coût. La convergence est dictée par la distribution favorable des valeurs propres, que le préconditionnement vise à améliorer.

Clinical relevance

Les méthodes de Krylov, en particulier le gradient conjugué préconditionné et GMRES, sont les solveurs standards utilisés dans les codes de simulation par éléments finis et volumes finis, l'optimisation à grande échelle et le calcul scientifique en général ; leur nature sans matrice leur permet de résoudre des systèmes avec des millions ou des milliards d'inconnues qu'aucune méthode directe ne pourrait factoriser.

History

La méthode du gradient conjugué a été introduite par Hestenes et Stiefel en 1952 et le processus de Lanczos sous-jacent en 1950 ; leur pleine puissance en tant que solveurs itératifs a été reconnue dans les années 1970, et le développement de GMRES par Saad et Schultz en 1986 ainsi que des méthodes biorthogonales stabilisées a étendu l'approche aux systèmes non symétriques généraux.

Key figures

• Magnus Hestenes
• Eduard Stiefel
• Cornelius Lanczos
• Yousef Saad
• Henk van der Vorst

Seminal works

• saad2003
• greenbaum1997

Frequently asked questions

Pourquoi la méthode du gradient conjugué ne fonctionne-t-elle que pour les matrices symétriques définies positives ?

Sa récurrence courte et efficace et son optimalité dans la norme d'énergie reposent sur le fait que la matrice est symétrique définie positive. Pour les matrices symétriques indéfinies ou non symétriques, différentes méthodes telles que MINRES ou GMRES sont nécessaires, généralement avec plus de stockage ou de travail par étape.

Pourquoi GMRES nécessite-t-il autant de mémoire ?

Pour une matrice non symétrique générale, il n'existe pas de récurrence courte qui maintienne la base de Krylov orthogonale, GMRES doit donc stocker chaque vecteur de base pour minimiser le résidu. GMRES redémarré limite la mémoire en rejetant périodiquement la base, au prix d'une convergence plus lente.