Lignes directrices pour les préconditionneurs imbriqués

Considérez la situation où vous souhaitez résoudre un système linéaire à l'aide d'une méthode Krylov préconditionnée, mais l'application du préconditionneur lui-même implique la résolution d'un système auxiliaire, ce qui se fait avec une autre méthode Krylov préconditionnée.

• À un extrême, vous pouvez exécuter la résolution interne pour qu'elle converge à chaque étape de la résolution externe.

• À l'autre extrême, vous ne pouviez pas du tout résoudre le problème intérieur, mais plutôt le remplacer par le préconditionneur intérieur.

• Quelque part au milieu, vous pourriez tronquer la boucle interne de Krylov après un certain nombre d'itérations fixe ou après qu'une certaine tolérance soit atteinte.

Empiriquement, j'ai rencontré des situations où le premier extrême est meilleur et différentes situations où le second extrême est meilleur (en termes de coût total). Cependant, je ne trouve aucune raison claire pour laquelle certaines situations favorisent une stratégie plutôt qu'une autre.

Existe-t-il une orientation ou une théorie sur le moment où ces différentes stratégies sont préférables?

Cette question est ouverte depuis longtemps, mais je pense qu'elle mérite encore une réponse.

Le problème fondamental avec l'utilisation de solveurs de l'espace Krylov sur des blocs individuels comme préconditionneurs internes est qu'ils ne sont pas des opérateurs linéaires. Pour comprendre cela, notons le vecteur que vous obtenez comme solution en exécutant une méthode spatiale de Krylov K sur le système linéaire A x = b pour au plus N itérations ou jusqu'à ce qu'une tolérance τ soit atteinte, en utilisant un préconditionneur P ≈ A - 1 . En d'autres termes, vous pouvez penser à$\tilde x = K(A,P,\tau,N; b)$$K$$Ax=b$$N$$\tau$$P\approx A^{-1}$ comme un opérateur qui agit sur b .$K$$b$

Notez maintenant que est un opérateur linéaire: il faudrait résoudre exactement A x = b , c'est-à-dire K ( A , P , 0 , ∞ ; b ) = A - 1 b , qui est linéaire en b . Dans de nombreux cas, l'exécution d'une méthode spatiale de Krylov pour exactement une itération à partir d'un vecteur zéro est également un opérateur linéaire appliqué à $K(A,P,0,\infty;\cdot)$$Ax=b$$K(A,P,0,\infty;b)=A^{-1}b$$b$$b$$r^{(0)}=b-Ax^{(0)}$$K(A,P,\tau,N; \cdot)$$N$$\tau$

$K(A,P,\tau,N; \cdot)$$A$

Cela contraste avec de nombreuses autres méthodes utilisées pour préconditionner: par exemple, une étape SSOR est une opération linéaire sur le vecteur auquel vous l'appliquez, comme le sont toutes les autres méthodes qui appliquent une étape d'une itération à point fixe.

Le problème fondamental est maintenant que la plupart des méthodes spatiales de Krylov nécessitent que le préconditionneur soit un opérateur linéaire. Ils ne convergeront tout simplement pas si le préconditionneur n'est pas linéaire, expliquant votre observation. D'autre part, il existe des variantes de certaines méthodes spatiales de Krylov - généralement préfixées par le mot "Flexible", telles que F-GMRES dans "Flexible GMRES" - qui fonctionnent autour de cela et qui peuvent traiter des préconditionneurs qui ne sont pas linéaires les opérateurs. Ces variantes flexibles des méthodes originales convergeront toujours et sont souvent des méthodes puissantes lorsqu'elles sont associées à de bons (mais non linéaires) préconditionneurs.