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

13

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

  1. Calcule el residuo ri=bAxi
  2. Aplique un ciclo de cuadrículas múltiples para obtener una aproximación , donde A e i = r i .ΔxieiAei=ri
  3. Actualizar xi+1xi+Δxi

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 Δ x i . Esto es típicamente un ciclo V o un ciclo W. Esta es una operación lineal, por lo que escribimos Δ x i = B r i .riΔxiΔxi=Bri

Uno puede interpretar este proceso como una iteración precondicionada de Richardson. Es decir, actualizamos .xi+1xi+Bri

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?

Patrick Sanan
fuente
2
(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:

10

bAx

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

siUN

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