Comment le Multigrid accéléré par Krylov (utilisant MG comme préconditionneur) est-il motivé?

Multigrid (MG) peut être utilisé pour résoudre un système linéaire en construisant une supposition initiale et en répétant ce qui suit pour jusqu'à la convergence:$Ax=b$$x_0$$i=0,1..$

1. Calculer le$r_i = b-Ax_i$
2. Appliquer un cycle multigrille pour obtenir une approximation , où .$\Delta x_i \approx e_i$$Ae_i = r_i$
3. Mettre à jour$x_{i+1} \gets x_i + \Delta x_i$

Le cycle multigrille est une séquence d'opérations de lissage, d'interpolation, de restriction et de résolution de grille grossière exacte appliquées à pour produire . Il s'agit généralement d'un cycle en V ou d'un cycle en W. Ceci est une opération linéaire donc nous écrivons .$r_i$$\Delta x_i$$\Delta x_i = B r_i$

On peut interpréter ce processus comme une itération de Richardson préconditionnée. Autrement dit, nous mettons à jour .$x_{i+1} \gets x_i + B r_i$

L'itération de Richardson est une méthode prototypique de sous-espace de Krylov, qui suggère l'utilisation de cycles multigrilles pour préconditionner d'autres méthodes de sous-espace de Krylov. Ceci est parfois appelé «accélération» multigrille avec une méthode Krylov, ou alternativement peut être considéré comme le choix d'un préconditionneur pour une méthode Krylov.

Une autre façon d'étendre l'algorithme ci-dessus consiste à utiliser Full Multigrid (FMG). Voir cette réponse pour une description concise.

Dans quelles situations la MG accélérée par Krylov est-elle préférable à la MG ou à la FMG?

$b-Ax$

Cependant, dans de nombreux cas pratiques, une méthode multigrille optimale ou efficace n'est pas utilisée. Cela peut être dû au fait

• une telle méthode est inconnue ou indisponible pour le problème donné
• les lisseurs et les opérateurs d'intergrid ne suffisent pas à assurer la convergence des manuels
• le solveur de grille grossière est inexact

$BA$

Notez que le choix d'utiliser une méthode sous-optimale peut entraîner un cycle multigrille beaucoup "moins cher", au point que l'accélération de Krylov est payante. Autrement dit, il pourrait y avoir des problèmes (et des systèmes informatiques) où la MG accélérée par Krylov peut surpasser la MG. Je serais intéressé à en trouver un exemple concret.

(Merci à @chris ci-dessus et Matt Knepley qui a mentionné certains des éléments ci-dessus dans un tutoriel)