¿Cómo se motiva la Multigrid acelerada por Krylov (usando MG como preacondicionador)?

Multigrid (MG) puede usarse para resolver un sistema lineal construyendo una conjetura inicial y repitiendo lo siguiente para hasta la convergencia: $Ax=b$ $x_0$ $i=0,1..$

Calcule el residuo $r_i = b-Ax_i$
Aplique un ciclo de cuadrículas múltiples para obtener una aproximación , donde . $\Delta x_i \approx e_i$ $Ae_i = r_i$
Actualizar $x_{i+1} \gets x_i + \Delta x_i$

El ciclo de múltiples cuadrículas es una secuencia de operaciones de suavizado, interpolación, restricción y resolución exacta de grillas gruesas aplicadas a para producir . Esto es típicamente un ciclo V o un ciclo W. Esta es una operación lineal, por lo que escribimos . $r_i$ $\Delta x_i$ $\Delta x_i = B r_i$

Uno puede interpretar este proceso como una iteración precondicionada de Richardson. Es decir, actualizamos . $x_{i+1} \gets x_i + B r_i$

La iteración de Richardson es un método prototípico del subespacio de Krylov, que sugiere el uso de ciclos de múltiples cuadrículas para preacondicionar otros métodos del subespacio de Krylov. Esto a veces se denomina multirredes "acelerado" con un método de Krylov, o alternativamente se puede ver como una opción de un preacondicionador para un método de Krylov.

Otra forma de extender el algoritmo anterior es emplear Full Multigrid (FMG). Vea esta respuesta para una descripción concisa.

¿En qué situaciones es preferible MG acelerado por Krylov a MG o FMG?

linear-algebra linear-solver multigrid krylov-method Patrick Sanan
fuente

(F) MG es bastante sensible, si un modo no está correctamente amortiguado por la corrección más suave o de dos niveles, todo se cuelga. El método de Krylov puede ayudar a amortiguar estos modos problemáticos. Así que, según tengo entendido, está principalmente motivado por la robustez.

Chris

Respuestas:

$b-Ax$

Sin embargo, en muchos casos prácticos, no se utiliza un método de cuadrícula óptimo o efectivo. Esto puede ser porque

dicho método es desconocido o no está disponible para el problema dado
suavizadores y operadores intergrid no son suficientes para dar convergencia de libros de texto
el solucionador de grilla gruesa es inexacto

$BA$

Tenga en cuenta que la elección de utilizar un método subóptimo podría dar como resultado un ciclo de cuadrícula mucho más "barato", hasta el punto de que la aceleración de Krylov valga la pena. Es decir, podría haber problemas (y sistemas informáticos) donde la MG acelerada por Krylov puede superar a la MG. Me interesaría encontrar un ejemplo concreto de esto.

(Gracias a @chris arriba y Matt Knepley que mencionaron algunos de los anteriores en un tutorial)

Patrick Sanan
fuente