Problemas donde el gradiente conjugado funciona mucho mejor que GMRES

Estoy interesado en casos en los que el gradiente Conjugate funciona mucho mejor que el método GMRES.

En general, CG es la opción preferible en muchos casos de SPD (simétrica-positiva-definida) porque requiere menos almacenamiento y el límite teórico en la tasa de convergencia para CG es el doble de ese GMRES. ¿Hay algún problema donde tales tasas se observan realmente? ¿Existe alguna caracterización de los casos en que GMRES se desempeña mejor o comparable a CG para el mismo número de spmvs (multiplicaciones de matriz-vector dispersas).

Una cosa que CG tiene a su favor es que no está minimizando la discreta norma para sus polinomios residuales (lo que hace GMRES). En cambio, está minimizando una norma inducida por la matriz, y muy a menudo esta norma inducida por la matriz termina siendo muy cercana a la norma de energía para la discretización de problemas físicos, y con frecuencia esta es una norma mucho más razonable para medir el error debido a las propiedades de conservación. de la física$l^2$

De hecho, también puede lograr este tipo de efecto con GMRES si realizar una factorización Cholesky de una matriz de masa no es demasiado costoso, puede forzar a los productos internos a ser los productos internos de energía que desea.

Entonces, los casos en los que uno debería esperar que CG funcione de manera muy diferente a GMRES es cuando las constantes implicadas en la equivalencia de normas son muy diferentes. Esto puede ser cierto, por ejemplo, en un método de Galerkin espectral de alto orden donde la discreta norma utilizada en GMRES trata todos los grados de libertad como iguales, cuando en realidad los gradientes polinomiales son límites cercanos más nítidos (por lo tanto, agrupamiento de nodos), y así las constantes de equivalencia de la norma entre esa norma y decir la norma continua dada por la matriz de masa puede ser muy grande.L $l^2$$L^2$

Sospecho que en general no hay mucha diferencia entre GMRES y CG para una matriz SPD.

Digamos que estamos resolviendo con A simétrica definida positiva y la suposición de partida x 0 = 0 y itera generando con CG y GMRES, los llaman x c k y x g k . Ambos métodos iterativos construirán x k desde el mismo espacio de Krylov K k = { b , A b , A 2 b , ... } . Lo harán de maneras ligeramente diferentes.$Ax = b$$A$$x_0 = 0$$x_k^c$$x_k^g$$x_k$$K_k = \{ b, Ab, A^2b, \ldots \}$

CG se caracteriza por reducir al mínimo el error en la norma de la energía inducida por A , de manera 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 minimiza en cambio el residuo , y lo hace en la norma discreta ℓ 2 , de modo 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}$$ Ahora, utilizando la ecuación de error podemos GMRES escribir también como minimizar ( r k , r k ) = ( A e g k , A e g k ) = ( A 2 e g k , e g k ) donde Quiero hacer hincapié en que esto sólo es válido para una matriz SPD a . Entonces tenemos CG minimizando el error con respecto a la $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$norma y GMRES minimizando el error con respecto a la norma . Si queremos que se comporten de manera muy diferente, de manera intuitiva que necesitaríamos un Un tal que estas dos normas son muy diferentes. Pero para SPD A, estas normas se comportarán de manera bastante similar.$A^2$$A$$A$

Para ser aún más específico, en la primera iteración con el espacio Krylov , tanto CG como GMRES construirán una aproximación de la forma x 1 = α b . CG elegirá α = ( b , b $K_1 = \{ b \}$$x_1 = \alpha b$ y GMRES elegirá α=(Ab,b

$$\begin{equation} \alpha = \frac{ (b,b) }{ (Ab,b) } \end{equation}$$ SiAes diagonal con entradas(ε,1,1,1,...)yb=(1,1,0,0,0,...)entonces comoε→0el primer paso CG se convierte en doble de grande que los primeros GMRES paso. Probablemente se puede construirunay $$\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$ por lo que este factor de dos diferencia continúa a través de la iteración, pero dudo de que empeore que eso.

Una cosa es que GMRES nunca se utiliza siempre que sea CG se puede aplicar. No creo que tiene sentido comparar estos dos. Para matrices SPD, CG es sin duda el ganador debido a los requisitos de almacenamiento y las razones que usted ha mencionado anteriormente. Una pregunta que sería interesante es, para encontrar una extensión de CG, que es aplicable a problemas donde CG no se puede aplicar. Existen métodos como BICG-puñalada que no requieren que aumenta linealmente memoria como GMRES, pero la convergencia no es tan buena como GMRES (algunas veces incluso con GMRES renovadas).