Quelles directives dois-je utiliser lors de la recherche de bonnes méthodes de préconditionnement pour un problème spécifique?

Pour la solution de grands systèmes linéaires utilisant des méthodes itératives, il est souvent intéressant d'introduire un préconditionnement, par exemple résoudre à la place M - 1 ( A x = b ) , où M est ici utilisé pour le préconditionnement à gauche du système. Typiquement, nous devrions avoir M - 1 ≈ A - 1 et fournir la base d'une solution (beaucoup plus) efficace ou d'une réduction des ressources de calcul (par exemple le stockage de la mémoire) par rapport à la solution du système d'origine (c'est-à-dire lorsque M = $Ax=b$$M^{-1}(Ax=b)$$M$$M^{-1}\approx A^{-1}$$M=A$). Cependant, quelles directives devrions-nous utiliser pour choisir le préconditionneur? Comment les praticiens font-ils cela pour leur problème spécifique?

Au départ, je ne voulais pas donner de réponse car cela mérite un traitement très long, et j'espère que quelqu'un d'autre le donnera toujours. Cependant, je peux certainement donner un très bref aperçu de l'approche recommandée:

1. Effectuez une recherche documentaire approfondie .
2. Si cela échoue, essayez tous les préconditionneurs qui ont du sens et que vous pouvez mettre la main sur. MATLAB, PETSc et Trilinos sont des environnements agréables pour cela.
3. Si cela échoue, vous devriez réfléchir soigneusement à la physique de votre problème et voir s'il est possible de trouver une solution approximative bon marché, peut-être même une version légèrement modifiée de votre problème.

Des exemples de 3 sont les versions déplacées de Helmholtz en laplacien et les travaux récents de Jinchao Xu sur le préconditionnement de l'opérateur biharmonique avec des laplaciens.

D'autres ont déjà commenté la question du préconditionnement de ce que j'appellerai des matrices "monolithiques", c'est-à-dire par exemple la forme discrétisée d'une équation scalaire telle que l'équation de Laplace, l'équation de Helmholtz ou, si vous voulez la généraliser, la valeur vectorielle équation d'élasticité. Pour ces choses, il est clair que la multigrille (algébrique ou géométrique) est gagnante si l'équation est elliptique, et pour d'autres équations, elle n'est pas aussi claire - mais quelque chose comme SSOR fonctionne souvent assez bien (pour une certaine signification de "raisonnable").

Pour moi, la grande révélation a été de savoir quoi faire à propos de problèmes qui ne sont pas monolithiques, par exemple pour l'opérateur de Stokes Lorsque j'ai commencé l'analyse numérique il y a une quinzaine d'années, je pense que les gens espéraient que les mêmes techniques pourraient être appliquées à de telles matrices comme ci-dessus, et la direction de la recherche était soit d'essayer directement plusieurs grilles, soit d'utiliser des généralisations de SSOR lisseurs de point "comme Vanka) et des méthodes similaires. Mais cela a disparu car cela ne fonctionne pas très bien.

$$\begin{pmatrix} A & B \\ B^T & 0 \end{pmatrix}.$$

Ce qui est venu remplacer cela était ce qui était initialement appelé "préconditionneurs basés sur la physique" et plus tard simplement (et peut-être plus précisément) "préconditionneurs de blocs" comme celui de Silvester et Wathen. Ceux-ci sont souvent basés sur des éliminations de blocs ou des compléments Schur et l'idée est de construire un préconditionneur de telle manière que l'on puisse réutiliser des préconditionneurs pour des blocs individuels qui sont connus pour bien fonctionner. Dans le cas de l'équation de Stokes, par exemple, le préconditionneur Silvester / Wathen utilise la matrice

$$\begin{pmatrix} A & B \\ 0 & B^T A^{-1} B \end{pmatrix}^{-1}$$ lorsqu'il est utilisé comme préconditionneur avec GMRES, il en résulterait une convergence en exactement deux itérations. Puisqu'il est triangulaire, l'inversion est également beaucoup plus simple, mais nous avons toujours le problème de ce que nous devons faire avec les blocs diagonaux, et là on utilise des approximations: où le tilde signifie remplacer l'inverse exact par une approximation. C'est souvent beaucoup plus simple: parce que le bloc A est un opérateur elliptique, ~ A - $$\begin{pmatrix} \widetilde{A^{-1}} & B \\ 0 & \widetilde{(B^T A^{-1} B)^{-1}} \end{pmatrix}$$ $A$$\widetilde{A^{-1}}$est bien approximé par un cycle en V multigrille, par exemple, et il s'avère qu'ici, est bien approximé par une ILU d'une matrice de masse.$\widetilde{(B^T A^{-1} B)^{-1}}$

Cette idée de travailler avec les blocs individuels qui composent la matrice et de réutiliser des préconditionneurs sur des blocs individuels s'est avérée extrêmement puissante et a complètement changé notre façon de penser les systèmes d'équations de préconditionnement aujourd'hui. Bien sûr, cela est pertinent car la plupart des problèmes réels sont, en fait, des systèmes d'équations.

Jack a donné une bonne procédure pour trouver un préconditionneur. Je vais essayer une adresse à la question "Qu'est-ce qui fait un bon préconditionneur?". La définition opérationnelle est:

$A x = b$$M^{-1}$$A^{-1}$

cependant, cela ne nous donne aucune idée de la conception d'un préconditionneur. La plupart des préconditionneurs sont basés sur la manipulation du spectre de l'opérateur. De manière générique, les méthodes de Krylov convergent plus rapidement lorsque les valeurs propres sont regroupées, voir Itérations matricielles ou fonctions méromorphes et Algèbre linéaire . Parfois, nous pouvons prouver qu'un résultat de préconditionneur n'est que quelques valeurs propres uniques, par exemple une note sur le préconditionnement pour les systèmes linéaires indéfinis .

Une stratégie commune est illustrée par Multigrid. Les préconditionneurs de relaxation (ici plus doux) comme le SOR éliminent les composants haute fréquence dans l'erreur. Lorsque le résidu est projeté sur une grille grossière, les composantes d'erreur de fréquence inférieure deviennent plus fréquentes et peuvent à nouveau être attaquées par le SOR. Cette stratégie de base sous-tend des versions plus complexes de MG, comme AMG. Notez qu'en bas, le solveur doit résoudre avec précision les fréquences les plus basses de l'erreur.

Une autre stratégie consiste à résoudre l'équation dans de petits sous-espaces, ce qui est exactement ce que font les solveurs de Krylov. Dans sa forme la plus simple, il s'agit de la méthode Kaczmarz ou de la méthode Additive Schwarz . La souche avancée de la théorie ici, la décomposition de domaine , se concentre sur l'approximation spectrale de l'erreur sur l'interface, car les domaines sont supposés être résolus assez précisément.

$A$