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:
- Comience con el problema de la cuadrícula fina
- Proyecta en una grilla gruesa (también conocida como restricción )
- Aproxima la solución en la grilla gruesa (usando algún otro solucionador)
- Proyecte la solución de cuadrícula gruesa en la cuadrícula más fina (también conocida como prolongación )
- 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.
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.
Briggs, Tutorial de múltiples cuadrículas , SIAM, 2000 (puede descargar diapositivas aquí y aquí ) Esta es una fuente informal, que proporciona una introducción suave a los principios de múltiples cuadrículas, principalmente para problemas elípticos.
Brandt, Multigrid Techniques , edición revisada, SIAM 2011 , (o descargue el pdf ). Este es un gran desarrollo de la filosofía multigrid y el modelado multiescala y tiene una buena oportunidad de cambiar profundamente su forma de pensar sobre los solucionadores implícitos. El sitio web de Achi Brandt contiene muchas más referencias, incluida su Revisión de 2000 de la computación científica multiescala .
Trottenberg, Oosterlee y Schueller, Multigrid , Academic Press, 2001 Esto tiene ejemplos más trabajados que Brandt, incluidos muchos experimentos y detalles sobre métodos específicos, especialmente en el contexto de la dinámica de fluidos.
Hackbusch, Métodos y aplicaciones de cuadrículas múltiples , Springer, 1985 Esto proporciona una teoría de convergencia rigurosa, que incluye "multirredes del segundo tipo" para operadores integrales de Fredholm.
fuente
Otro clásico:
Se pueden encontrar códigos de ejemplo en MGNet
fuente