Préconditionnement

Le préconditionnement transforme un système linéaire en un système équivalent doté d'un spectre plus favorable, permettant ainsi à un solveur itératif de converger en beaucoup moins d'étapes ; il représente souvent le facteur le plus important pour la performance des grands solveurs de systèmes creux.

Definition

Un préconditionneur est une matrice, appliquée implicitement ou explicitement à un système linéaire, qui approxime la matrice des coefficients ou son inverse de manière à ce que le système préconditionné possède des propriétés spectrales conduisant à une convergence beaucoup plus rapide d'une méthode itérative.

Scope

Ce sujet aborde le concept d'une inverse approximative qui regroupe les valeurs propres ou réduit le nombre de conditionnement, les principales familles de préconditionneurs — diagonaux et bloc-diagonaux, les factorisations LU et de Cholesky incomplètes, les inverses approximatives creuses, ainsi que les préconditionneurs de décomposition de domaine et multigrilles — et le compromis entre l'efficacité d'un préconditionneur et son coût de construction et d'application.

Core questions

• Comment un préconditionneur modifie-t-il le spectre d'un système pour accélérer la convergence itérative ?
• Qu'est-ce qui caractérise un bon préconditionneur, en équilibrant la qualité de l'approximation et le coût de construction et d'application ?
• Comment sont construites les factorisations incomplètes et les inverses approximatives creuses ?
• Quand les méthodes multigrilles ou de décomposition de domaine sont-elles utilisées comme préconditionneurs plutôt que comme solveurs autonomes ?

Key theories

Transformation spectrale

L'application d'un préconditionneur qui approxime l'inverse de la matrice produit un opérateur préconditionné dont les valeurs propres sont regroupées ou dont le nombre de conditionnement est réduit ; étant donné que la convergence de Krylov dépend du spectre, cela peut réduire le nombre d'itérations de plusieurs ordres de grandeur.

Préconditionneurs par factorisation incomplète

Les factorisations LU incomplètes et de Cholesky incomplètes calculent des facteurs triangulaires approximatifs tout en rejetant le remplissage (fill-in) au-delà d'un motif de sparsité ou d'un seuil choisi, produisant ainsi un préconditionneur peu coûteux qui capture une grande partie de l'action de la matrice.

Mechanisms

Un préconditionneur M est choisi de sorte que la résolution de systèmes avec M soit peu coûteuse et que l'opérateur préconditionné soit proche de l'identité, regroupant ainsi ses valeurs propres. Le préconditionnement diagonal (Jacobi) se contente de rééchelonner ; les factorisations LU ou de Cholesky incomplètes construisent des facteurs triangulaires creux approximatifs en omettant les entrées de faible valeur ou hors-motif (out-of-pattern) pendant l'élimination ; les inverses approximatives creuses construisent directement une matrice M creuse approximant l'inverse, de sorte que seuls des produits matrice-vecteur sont nécessaires. Des préconditionneurs plus puissants appliquent un cycle multigrille ou une résolution par décomposition de domaine par itération. Dans chaque cas, le préconditionneur est appliqué à chaque étape d'une méthode de Krylov, et sa conception équilibre la qualité de son approximation de l'inverse avec son coût de formation et d'application.

Clinical relevance

Le préconditionnement est décisif pour la résolution des systèmes énormes et mal conditionnés issus des discrétisations d'équations aux dérivées partielles (EDP) et de l'optimisation à grande échelle ; le bon préconditionneur peut transformer une itération qui stagne en une qui converge en quelques étapes, et le choix et l'ajustement des préconditionneurs constituent une préoccupation pratique centrale dans les logiciels de science computationnelle et d'ingénierie.

History

Le préconditionnement s'est développé parallèlement aux méthodes de Krylov à partir des années 1970, avec l'introduction des factorisations incomplètes par Meijerink et van der Vorst en 1977 et le développement depuis d'un large éventail de préconditionneurs algébriques et multiniveaux ; il est désormais souvent reconnu comme plus important pour la performance des solveurs que le choix de la méthode de Krylov elle-même.

Key figures

• Yousef Saad
• Michele Benzi
• Henk van der Vorst
• Olof Widlund

Seminal works

• saad2003
• benzi2002

Frequently asked questions

Qu'est-ce qui fait un bon préconditionneur ?

Un bon préconditionneur approxime étroitement l'inverse de la matrice afin que le système préconditionné soit facile à résoudre pour la méthode itérative, tout en étant peu coûteux à construire et à appliquer. L'art consiste à équilibrer ces objectifs contradictoires : un préconditionneur plus précis coûte plus cher par étape mais nécessite moins d'étapes.

Un solveur peut-il être utilisé comme préconditionneur ?

Oui. Un seul cycle multigrille ou une seule résolution par décomposition de domaine est fréquemment utilisé comme préconditionneur au sein d'une méthode de Krylov, combinant la robustesse de l'itération de Krylov avec la réduction rapide de l'erreur du solveur interne.