método de múltiples cuadrículas para resolver PDE

15

Necesito una explicación simple del Método Multigrid o alguna literatura sobre esto.

Estoy familiarizado con los métodos iterativos que incluyen BiCGStab, CG, GS, Jacobi y el preacondicionamiento, pero soy un principiante con el método de múltiples cuadrículas.

¿Alguien puede explicar esto en detalle o al menos proporcionar claramente pseudocódigo o código fuente, incluso con buena literatura para principiantes? ¡Gracias!

Nurlan
fuente

Respuestas:

15

La idea principal detrás de multigrid es la proyección. Intento pensarlo de la siguiente manera:

Supongamos que quiero resolver un PDE con mucha precisión, así que procedo a discretizar el dominio (digamos, usando el método de diferencia finita) en una cuadrícula muy fina con muchos puntos. Al final, configuré mi sistema de ecuaciones y estoy listo para resolverlo. Intento usar mi solucionador iterativo favorito (jacobi, gauss seidel, gradiente conjugado, etc.). ¡Procedo a esperar más de un día y me doy cuenta de que mi computadora todavía está tratando de calcular la respuesta!

La razón por la cual estos métodos iterativos no funcionan rápidamente es porque (típicamente) cuando configura un sistema grande de ecuaciones como esta, la matriz en sí tiene valores propios extremadamente cercanos a 1. ¿Por qué es importante? Debido a que la tasa de convergencia de muchos métodos iterativos está inversamente relacionada con el valor propio más grande (vea el enlace de Christian Clason a las Diapositivas del Tutorial de Multigrid de Brigg, parte 1, página 27). Entonces, cuanto más cercano es el valor propio más grande a 1, más lento es el método iterativo. (Nota: esto simplifica un poco las cosas, pero ayuda a motivar la necesidad de múltiples cuadrículas).

Obviamente, siempre es más rápido resolver el problema si hay menos incógnitas (es decir, en una cuadrícula gruesa con menos puntos de cuadrícula). Pero lo más importante, la solución (o solución aproximada) en una cuadrícula más gruesa es un buen punto de partida para resolver el problema en una cuadrícula más fina. Esta es la idea clave detrás de la mayoría (si no todos) los métodos multirredes. ¿Por qué es este el caso? Intuitivamente, tiene sentido, pero hay una forma matemáticamente rigurosa de justificar esto.

Veamos los modos de Fourier del error en un método iterativo (por el bien de los argumentos, digamos jacobi o gauss seidel) aplicado al problema original de la cuadrícula fina. ¡Veríamos que en las primeras iteraciones, se elimina la mayoría de los errores de alta frecuencia (altamente oscilatorios)! Esto es genial, pero hay un error de baja frecuencia (menos oscilatorio) que aún permanece y no desaparece rápidamente. De hecho, es un error de baja frecuencia que impide que un método iterativo estándar converja rápidamente.

cuando resolvemos el problema en una cuadrícula más gruesa (digamos, mediante un método iterativo como jacobi o gauss-seidel), somos esencialmente capaces de eliminar los errores de frecuencia más baja mucho más rápido (es decir, en menos iteraciones) que en la cuadrícula fina . Entonces, si resolvemos el problema de una grilla gruesa, tenemos una solución cuyos errores de baja frecuencia se han reducido significativamente. Por lo tanto, sería útil como punto de partida para un método iterativo en la cuadrícula más fina.

Si bien existen diferentes métodos de múltiples cuadrículas, la mayoría de ellos funcionan con alguna variación de lo siguiente:

  1. Comience con el problema de la cuadrícula fina
  2. Proyecta en una grilla gruesa (también conocida como restricción )
  3. Aproxima la solución en la grilla gruesa (usando algún otro solucionador)
  4. Proyecte la solución de cuadrícula gruesa en la cuadrícula más fina (también conocida como prolongación )
  5. Usando la proyección de 4. como una suposición inicial, resuelva el problema de la cuadrícula fina mediante un método iterativo.

Para mí, la parte más difícil del método de cuadrícula múltiple son las proyecciones entre cuadrículas. Los tutoriales de Briggs sugeridos por @ChristianClason manejan este tema mucho mejor que yo.

Paul
fuente
Gracias por la respuesta detallada! Ahora tengo algunos conocimientos básicos sobre el método multigrdi. Ahora tengo una pregunta específica sobre los procesos de restricción y prolongación. Leí que algunas matrices de restricción R y matriz de interpolación M y fórmulas como A2 = RAI solían hacer proyecciones entre cuadrículas. Pero no entendí cómo construir matrices R y I ... ¿Hay alguna idea sobre esto?
Nurlan
Mire las diapositivas 45-57 del tutorial multigrid de Briggs (parte 1) que publicó ChristianClason. Allí, Briggs describe el proceso para el método de cuadrícula geométrica. Esa es la explicación más simple que puedo encontrar. Si tiene más preguntas al respecto, ¡no dude en publicar una nueva pregunta! :)
Paul
15

Este sitio posiblemente no sea un buen lugar para pedir una explicación detallada con pseudocódigo (como se indica en las Preguntas frecuentes , "Si puede imaginar un libro completo que responda a su pregunta, está pidiendo demasiado"), por lo que es posible que desee para comenzar con uno de los libros clásicos sobre este tema (que se enumeran a continuación) y volver con preguntas específicas sobre detalles concretos con los que tiene problemas.

Christian Clason
fuente
2
¡Briggs es realmente bueno!
vanCompute
5

Otro clásico:

  • Wesseling, An Introduction to Multigrid Methods, John Wiley & Sons, 1992.

Se pueden encontrar códigos de ejemplo en MGNet

Chris
fuente