Problèmes où le gradient conjugué fonctionne beaucoup mieux que GMRES

Je m'intéresse aux cas où le gradient conjugué fonctionne bien mieux que la méthode GMRES.

En général, le CG est le choix préférable dans de nombreux cas de SPD (symétrique-positif-défini) car il nécessite moins de stockage et le taux théorique de convergence pour le CG est le double de celui du GMRES. Y a-t-il des problèmes où ces taux sont effectivement observés? Existe-t-il une caractérisation des cas où GMRES fonctionne mieux ou est comparable à CG pour le même nombre de spmv (multiplications matricielles-vecteur éparses).

Une chose que CG a en sa faveur est qu'elle ne minimise pas la norme discrète pour ses polynômes résiduels (ce que fait GMRES). Cela minimise plutôt une norme induite par la matrice, et très souvent cette norme induite par la matrice finit par être très proche de la norme énergétique pour la discrétisation des problèmes physiques, et souvent c'est une norme beaucoup plus raisonnable pour mesurer l'erreur en raison des propriétés de conservation à venir de la physique.$l^2$

Vous pouvez également obtenir ce type d'effet avec GMRES si effectuer une factorisation Cholesky d'une matrice de masse n'est pas trop cher, vous pouvez forcer les produits internes à être les produits énergétiques internes que vous souhaitez.

Ensuite, les cas où l'on devrait s'attendre à ce que CG fonctionne très différemment de GMRES, c'est quand les constantes impliquées dans l'équivalence de normes sont très différentes. Cela peut être vrai par exemple dans une méthode spectrale de Galerkin d'ordre élevé où la norme discrète utilisée dans GMRES traite tous les degrés de liberté comme étant égaux, alors qu'en réalité les gradients polynomiaux sont les plus nets près des frontières (d'où le regroupement de nœuds), etc. les constantes d'équivalence de norme entre cette norme et disons que la norme continue donnée par la matrice de masse peut être très grande.L $l^2$$L^2$

Je soupçonne qu'il n'y a en général pas beaucoup de différence entre GMRES et CG pour une matrice SPD.

Disons que nous résolvons avec A défini positif symétrique et la supposition de départ x 0 = 0 et générons des itérations avec CG et GMRES, appelons-les x c k et x g k . Les deux méthodes itératives construiront x k à partir du même espace de Krylov K k = { b , A b , A 2 b , … } . Ils le feront de manières légèrement différentes.$Ax = b$$A$$x_0 = 0$$x_k^c$$x_k^g$$x_k$$K_k = \{ b, Ab, A^2b, \ldots \}$

CG se caractérise en minimisant l'erreur dans la norme d'énergie induite par A , de sorte que ( A e c k , e c k ) = ( A ( x - x c k ) , x - x c k ) = min y ∈ K ( A ( x - y ) , x $e_k^c = x - x_k^c$$A$

$$\begin{equation} (A e_k^c, e_k^c) = (A (x - x_k^c), x - x_k^c) = \min_{y \in K} (A (x-y), x-y). \end{equation}$$

GMRES minimise à la place le résidu , et le fait dans la norme discrète ℓ 2 , de sorte que ( r k , r k ) = ( b - A x g k , b - A x g k ) = min y ∈ K ( b - A y , b - A y ) $r_k = b - A x^g_k$$\ell^2$

$$\begin{equation} (r_k, r_k) = (b - A x_k^g, b - A x_k^g) = \min_{y \in K} (b - Ay, b - Ay). \end{equation}$$ Maintenant, en utilisant l'équation d'erreur nous pouvons également écrire GMRES comme minimisant ( r k , r k ) = ( A e g k , A e g k ) = ( A 2 e g k , e g k ) où Je tiens à souligner que ce ne vaut que pour une matrice SPD A . Ensuite, nous avons CG minimisant l'erreur par rapport à l' $A e_k = r_k$ $$\begin{equation} (r_k, r_k) = (A e_k^g, A e_k^g) = (A^2 e_k^g, e_k^g) \end{equation}$$ $A$$A$norme et GMRES minimisant l'erreur par rapport à la norme . Si nous voulons qu'ils se comportent très différemment, nous aurions besoin intuitivement d'un A tel que ces deux normes soient très différentes. Mais pour le SPD A, ces normes se comporteront de manière assez similaire.$A^2$$A$$A$

Pour être encore plus précis, dans la première itération avec l'espace de Krylov , CG et GMRES construiront une approximation de la forme x 1 = α b . CG choisira α = ( b , b $K_1 = \{ b \}$$x_1 = \alpha b$

$$\begin{equation} \alpha = \frac{ (b,b) }{ (Ab,b) } \end{equation}$$ $$\begin{equation} \alpha = \frac{ (Ab,b) }{ (A^2b,b) }. \end{equation}$$ $A$$(\epsilon,1,1,1,\ldots)$$b = (1,1,0,0,0,\ldots)$$\epsilon \rightarrow 0$$A$$b$ de sorte que ce facteur de différence deux continue tout au long de l'itération, mais je doute qu'il s'aggrave.

Une chose est que GMRES n'est jamais utilisé partout où CG peut être appliqué. Je ne pense pas qu'il soit logique de comparer ces deux. Pour les matrices SPD, CG est définitivement le gagnant en raison des exigences de stockage et des raisons que vous avez mentionnées ci-dessus. Une question qui serait intéressante est de trouver une extension de CG, applicable aux problèmes où CG ne peut pas être appliqué. Il existe des méthodes comme BiCG-stab qui ne nécessitent pas d'augmentation linéaire de la mémoire comme GMRES, mais la convergence n'est pas aussi bonne que GMRES (parfois même avec GMRES redémarré).