Método multigrid

Método de resolución de ecuaciones diferenciales

En análisis numérico , un método multigrid ( método MG ) es un algoritmo para resolver ecuaciones diferenciales utilizando una jerarquía de discretizaciones . Son un ejemplo de una clase de técnicas llamadas métodos multiresolución , muy útiles en problemas que exhiben múltiples escalas de comportamiento. Por ejemplo, muchos métodos básicos de relajación exhiben diferentes tasas de convergencia para componentes de longitud de onda corta y larga, lo que sugiere que estas diferentes escalas se traten de manera diferente, como en un enfoque de análisis de Fourier para multigrid. ^[1] Los métodos MG se pueden utilizar como solucionadores y preacondicionadores .

La idea principal de la multimalla es acelerar la convergencia de un método iterativo básico (conocido como relajación, que generalmente reduce el error de longitud de onda corta) mediante una corrección global de la aproximación de la solución de la malla fina de vez en cuando, lograda mediante la solución de un problema burdo . El problema burdo, si bien es más económico de resolver, es similar al problema de la malla fina en que también tiene errores de longitud de onda corta y larga. También se puede resolver mediante una combinación de relajación y apelación a mallas aún más burdas. Este proceso recursivo se repite hasta que se llega a una malla donde el costo de la solución directa allí es insignificante en comparación con el costo de un barrido de relajación en la malla fina. Este ciclo multimalla generalmente reduce todos los componentes de error en una cantidad fija acotada muy por debajo de uno, independientemente del tamaño de la malla de la malla fina. La aplicación típica de la multimalla es en la solución numérica de ecuaciones diferenciales parciales elípticas en dos o más dimensiones. ^[2]

Los métodos multigrid se pueden aplicar en combinación con cualquiera de las técnicas de discretización comunes. Por ejemplo, el método de elementos finitos puede reformularse como un método multigrid. ^[3] En estos casos, los métodos multigrid se encuentran entre las técnicas de solución más rápidas conocidas en la actualidad. A diferencia de otros métodos, los métodos multigrid son generales en el sentido de que pueden tratar regiones arbitrarias y condiciones de contorno . No dependen de la separabilidad de las ecuaciones u otras propiedades especiales de la ecuación. También se han utilizado ampliamente para sistemas de ecuaciones no simétricos y no lineales más complicados, como las ecuaciones de elasticidad de Lamé o las ecuaciones de Navier-Stokes . ^[4]

Algoritmo

Visualización del algoritmo iterativo Multigrid para convergencia rápida O(n).

Existen muchas variantes de algoritmos multigrid, pero las características comunes son que se considera una jerarquía de discretizaciones (grids). Los pasos importantes son: ^{[5] [6]}

• Suavizado : reducción de errores de alta frecuencia, por ejemplo, utilizando unas cuantas iteraciones del método de Gauss-Seidel .
• Cálculo residual : cálculo del error residual después de las operaciones de suavizado.
• Restricción : reducir el error residual a una cuadrícula más gruesa.
• Interpolación o prolongación : interpolar una corrección calculada en una cuadrícula más gruesa en una cuadrícula más fina.
• Corrección : agregar una solución de rejilla más gruesa prolongada sobre la rejilla más fina.

Existen muchas opciones de métodos multigrid con diferentes compensaciones entre la velocidad de resolución de una única iteración y la tasa de convergencia con dicha iteración. Los 3 tipos principales son V-Cycle, F-Cycle y W-Cycle. Estos se diferencian en cuáles y cuántos ciclos de grano grueso se realizan por iteración fina. El algoritmo V-Cycle ejecuta un V-Cycle de grano grueso. F-Cycle realiza un V-Cycle de grano grueso seguido de un F-Cycle de grano grueso, mientras que cada W-Cycle realiza dos W-Cycles de grano grueso por iteración. Para un problema 2D discreto , F-Cycle tarda un 83% más de tiempo en calcularse que una iteración V-Cycle, mientras que una iteración W-Cycle tarda un 125% más. Si el problema se plantea en un dominio 3D, entonces una iteración F-Cycle y una iteración W-Cycle toman aproximadamente un 64% y un 75% más de tiempo respectivamente que una iteración V-Cycle ignorando los gastos generales . Normalmente, W-Cycle produce una convergencia similar a F-Cycle. Sin embargo, en casos de problemas de convección-difusión con números de Péclet altos , W-Cycle puede mostrar superioridad en su tasa de convergencia por iteración sobre F-Cycle. La elección de operadores de suavizado es extremadamente diversa, ya que incluyen métodos de subespacio de Krylov y pueden preacondicionarse .

Cualquier iteración de ciclo multicuadrícula geométrica se realiza en una jerarquía de cuadrículas y, por lo tanto, se puede codificar mediante recursión. Dado que la función se llama a sí misma con parámetros de menor tamaño (más gruesos), la cuadrícula más gruesa es donde se detiene la recursión. En los casos en que el sistema tiene un número de condición alto , el procedimiento de corrección se modifica de modo que solo una fracción de la solución de cuadrícula más gruesa prolongada se agregue a la cuadrícula más fina.

Costo computacional[ cita requerida ]

Suponiendo una configuración de problema bidimensional, el cálculo se mueve a través de la jerarquía de la cuadrícula de manera diferente para varios ciclos de múltiples cuadrículas.

Este enfoque tiene la ventaja sobre otros métodos de que suele escalar linealmente con el número de nodos discretos utilizados. En otras palabras, puede resolver estos problemas con una precisión determinada en un número de operaciones que es proporcional al número de incógnitas.

Supongamos que tenemos una ecuación diferencial que se puede resolver de forma aproximada (con una precisión dada) en una cuadrícula con una densidad de puntos de cuadrícula dada . Supongamos además que se puede obtener una solución en cualquier cuadrícula con un esfuerzo dado a partir de una solución en una cuadrícula más gruesa . Aquí, es la relación de puntos de cuadrícula en cuadrículas "vecinas" y se supone que es constante en toda la jerarquía de cuadrículas, y es una constante que modela el esfuerzo de calcular el resultado para un punto de cuadrícula. ${\displaystyle i}$ ${\displaystyle N_{i}}$ ${\displaystyle N_{i}}$ ${\displaystyle W_{i}=\rho KN_{i}}$ ${\displaystyle i+1}$ ${\displaystyle \rho =N_{i+1}/N_{i}<1}$ ${\displaystyle K}$

Se obtiene entonces la siguiente relación de recurrencia para el esfuerzo de obtener la solución en la cuadrícula : ${\displaystyle k}$

${\displaystyle W_{k}=W_{k+1}+\rho KN_{k}}$

Ejemplo de tasas de convergencia de ciclos multigrid en comparación con otros operadores de suavizado.

Y en particular, encontramos que para la cuadrícula más fina ${\displaystyle N_{1}}$

${\displaystyle W_{1}=W_{2}+\rho KN_{1}}$

Combinando estas dos expresiones (y usando ) obtenemos ${\displaystyle N_{k}=\rho ^{k-1}N_{1}}$

${\displaystyle W_{1}=KN_{1}\sum _{p=0}^{n}\rho ^{p}}$

Usando la serie geométrica , encontramos entonces (para finito ) ${\displaystyle n}$

${\displaystyle W_{1}<KN_{1}{\frac {1}{1-\rho }}}$

Es decir, se puede obtener una solución a tiempo. Cabe mencionar que existe una excepción a la multimalla de ciclo W utilizada en un problema unidimensional: resultaría compleja. ^{[ cita requerida ]} ${\displaystyle O(N)}$ ${\displaystyle O(N)}$ ${\displaystyle O(Nlog(N))}$

Preacondicionamiento multirred

Un método multigrid con una tolerancia reducida intencionalmente se puede utilizar como un preacondicionador eficiente para un solucionador iterativo externo, p. ej., ^[7] La ​​solución aún se puede obtener en el tiempo así como en el caso en que se utilice el método multigrid como solucionador. El preacondicionamiento multigrid se utiliza en la práctica incluso para sistemas lineales, típicamente con un ciclo por iteración, p. ej., en Hypre . Su principal ventaja frente a un solucionador puramente multigrid es particularmente clara para problemas no lineales, p. ej., problemas de valores propios . ${\displaystyle O(N)}$

Si la matriz de la ecuación original o un problema de valor propio es definida positiva simétrica (SPD), el preacondicionador se construye comúnmente para que también sea SPD, de modo que aún se puedan usar los métodos iterativos de gradiente conjugado (CG) estándar . Tales restricciones SPD impuestas pueden complicar la construcción del preacondicionador, por ejemplo, requiriendo pre y post suavizado coordinado. Sin embargo, se ha demostrado ^{[8] que los métodos} de descenso más empinado preacondicionado y CG flexible para sistemas lineales SPD y LOBPCG para problemas de valor propio simétricos son robustos si el preacondicionador no es SPD.

Preacondicionador Bramble–Pasciak–Xu

Originalmente descrito en la tesis doctoral de Xu ^[9] y posteriormente publicado en Bramble-Pasciak-Xu, ^[10] el preacondicionador BPX es uno de los dos principales enfoques multigrid (el otro es el algoritmo multigrid clásico como el ciclo V) para resolver sistemas algebraicos a gran escala que surgen de la discretización de modelos en ciencia e ingeniería descritos por ecuaciones diferenciales parciales. En vista del marco de corrección del subespacio, ^[11] el preacondicionador BPX es un método de corrección del subespacio paralelo mientras que el ciclo V clásico es un método de corrección del subespacio sucesivo. Se sabe que el preacondicionador BPX es naturalmente más paralelo y en algunas aplicaciones más robusto que el método multigrid clásico del ciclo V. El método ha sido ampliamente utilizado por investigadores y profesionales desde 1990.

Métodos multigrid generalizados

Los métodos multigrid se pueden generalizar de muchas maneras diferentes. Se pueden aplicar de forma natural en una solución de ecuaciones diferenciales parciales parabólicas en pasos de tiempo , o se pueden aplicar directamente a ecuaciones diferenciales parciales dependientes del tiempo . ^[12] Se están realizando investigaciones sobre técnicas multinivel para ecuaciones diferenciales parciales hiperbólicas . ^[13] Los métodos multigrid también se pueden aplicar a ecuaciones integrales o a problemas de física estadística . ^[14]

Otro conjunto de métodos multirresolución se basa en wavelets . Estos métodos wavelets se pueden combinar con métodos multigrid. ^{[15] [16]} Por ejemplo, un uso de wavelets es reformular el enfoque de elementos finitos en términos de un método multinivel. ^[17]

La multigrid adaptativa exhibe un refinamiento de malla adaptativo , es decir, ajusta la cuadrícula a medida que avanza el cálculo, de una manera que depende del cálculo mismo. ^[18] La idea es aumentar la resolución de la cuadrícula solo en las regiones de la solución donde se necesita.

Multimalla algebraica (AMG)

Las extensiones de importancia práctica de los métodos multigrid incluyen técnicas en las que no se utiliza ninguna ecuación diferencial parcial ni un fondo de problemas geométricos para construir la jerarquía multinivel. ^[19] Estos métodos multigrid algebraicos (AMG) construyen su jerarquía de operadores directamente a partir de la matriz del sistema. En el AMG clásico, los niveles de la jerarquía son simplemente subconjuntos de incógnitas sin ninguna interpretación geométrica. (De manera más general, las incógnitas de la cuadrícula gruesa pueden ser combinaciones lineales particulares de incógnitas de la cuadrícula fina). Por lo tanto, los métodos AMG se convierten en solucionadores de caja negra para ciertas clases de matrices dispersas . AMG se considera ventajoso principalmente cuando la multigrid geométrica es demasiado difícil de aplicar, ^[20] pero a menudo se utiliza simplemente porque evita la codificación necesaria para una verdadera implementación multigrid. Si bien el AMG clásico se desarrolló primero, un método algebraico relacionado se conoce como agregación suavizada (SA).

En un artículo de revisión ^[21] de Jinchao Xu y Ludmil Zikatanov, los métodos de "multimalla algebraica" se entienden desde un punto de vista abstracto. Desarrollaron un marco unificado y los métodos de multimalla algebraica existentes se pueden derivar de manera coherente. Se derivó una teoría abstracta sobre cómo construir un espacio grueso óptimo, así como espacios cuasi-óptimos. Además, demostraron que, bajo supuestos apropiados, el método abstracto AMG de dos niveles converge de manera uniforme con respecto al tamaño del sistema lineal, la variación del coeficiente y la anisotropía. Su marco abstracto cubre la mayoría de los métodos AMG existentes, como el AMG clásico, el AMG de minimización de energía, el AMG de agregación suavizado y no suavizado, y el AMGe espectral.

Métodos de multigrid en el tiempo

Los métodos multigrid también se han adoptado para la solución de problemas de valor inicial . ^[22] De particular interés aquí son los métodos multigrid paralelos en el tiempo: ^[23] en contraste con los métodos Runge-Kutta clásicos o los métodos multipaso lineales , pueden ofrecer concurrencia en dirección temporal. El conocido método de integración Parareal paralelo en el tiempo también se puede reformular como una multigrid de dos niveles en el tiempo.

Multigrid para problemas casi singulares

Los problemas casi singulares surgen en varias aplicaciones físicas y de ingeniería importantes. Un ejemplo simple, pero importante de problemas casi singulares se puede encontrar en la formulación de desplazamiento de elasticidad lineal para materiales casi incompresibles. Por lo general, el problema principal para resolver tales sistemas casi singulares se reduce a tratar el operador casi singular dado por de manera robusta con respecto al parámetro positivo, pero pequeño . Aquí hay un operador semidefinido simétrico con un gran espacio nulo , mientras que es un operador definido positivo simétrico . Hubo muchos trabajos para intentar diseñar un método multigrid robusto y rápido para tales problemas casi singulares. Se ha proporcionado una guía general como principio de diseño para lograr una tasa de convergencia independiente de los parámetros (por ejemplo, tamaño de malla y parámetros físicos como el coeficiente de Poisson que aparecen en el operador casi singular) del método multigrid aplicado a tales sistemas casi singulares, ^[24] es decir, en cada cuadrícula, se debe construir una descomposición espacial en base a la cual se aplica el suavizado, de modo que el espacio nulo de la parte singular del operador casi singular se debe incluir en la suma de los espacios nulos locales, la intersección del espacio nulo y los espacios locales resultantes de las descomposiciones espaciales. ${\displaystyle A+\varepsilon M}$ ${\displaystyle \varepsilon }$ ${\displaystyle A}$ ${\displaystyle M}$

Notas

1. Roman Wienands; Wolfgang Joppich (2005). Análisis práctico de Fourier para métodos multimalla. CRC Press. p. 17. ISBN 978-1-58488-492-7.
2. U. Trotenberg; CW Oosterlee; A. Schüller (2001). Multired. Prensa académica. ISBN 978-0-12-701070-0.
3. Yu Zhu; Andreas C. Cangellaris (2006). Métodos de elementos finitos multimalla para modelado de campos electromagnéticos. Wiley. p. 132 y siguientes . ISBN 978-0-471-74110-7.
4. Shah, Tasneem Mohammad (1989). Análisis del método multigrid (Tesis). Universidad de Oxford. Código Bibliográfico :1989STIN...9123418S.
5. MT Heath (2002). "Sección 11.5.7 Métodos multigrid". Computación científica: una revisión introductoria . McGraw-Hill Higher Education. pág. 478 y siguientes . ISBN 978-0-07-112229-0.
6. P. Wesseling (1992). Introducción a los métodos multigrid. Wiley. ISBN 978-0-471-93083-9.
7. Andrew V Knyazev, Klaus Neymeyr. Solución eficiente de problemas de valores propios simétricos utilizando preacondicionadores multimalla en el método de gradiente conjugado de bloques localmente óptimo. Electronic Transactions on Numerical Analysis, 15, 38–55, 2003.
8. Bouwmeester, Henricus; Dougherty, Andrew; Knyazev, Andrew V. (2015). "Preacondicionamiento no simétrico para métodos de gradiente conjugado y descenso más pronunciado 1". Procedia Computer Science . 51 : 276–285. arXiv : 1212.6680 . doi : 10.1016/j.procs.2015.05.241 . S2CID  51978658.
9. Xu, Jinchao. Teoría de métodos multinivel. Vol. 8924558. Ithaca, NY: Cornell University, 1989.
10. Bramble, James H., Joseph E. Pasciak y Jinchao Xu. "Preacondicionadores multinivel paralelos". Mathematics of Computation 55, núm. 191 (1990): 1–22.
11. Xu, Jinchao. "Métodos iterativos por descomposición espacial y corrección del subespacio". Revista SIAM 34, núm. 4 (1992): 581-613.
12. F. Hülsemann; M. Kowarschik; M. Mohr; U. Rüde (2006). "Multimalla geométrica paralela". En Are Magnus Bruaset; Aslak Tveito (eds.). Solución numérica de ecuaciones diferenciales parciales en computadoras paralelas . Birkhäuser. pág. 165. ISBN 978-3-540-29076-6.
13. Por ejemplo, J. Blaz̆ek (2001). Dinámica de fluidos computacional: principios y aplicaciones. Elsevier. p. 305. ISBN 978-0-08-043009-6.y Achi Brandt y Rima Gandlin (2003). "Multigrid para la asimilación de datos atmosféricos: análisis". En Thomas Y. Hou; Eitan Tadmor (eds.). Problemas hiperbólicos: teoría, numérica, aplicaciones: actas de la Novena Conferencia Internacional sobre Problemas Hiperbólicos de 2002. Springer. pág. 369. ISBN 978-3-540-44333-9.
14. Achi Brandt (2002). "Computación científica multiescala: revisión". En Timothy J. Barth; Tony Chan; Robert Haimes (eds.). Métodos multiescala y multiresolución: teoría y aplicaciones . Springer. p. 53. ISBN 978-3-540-42420-8.
15. Björn Engquist; Olof Runborg (2002). "Homogeneización numérica basada en wavelets con aplicaciones". En Timothy J. Barth; Tony Chan; Robert Haimes (eds.). Métodos multiescala y multiresolución . Vol. 20 de Lecture Notes in Computational Science and Engineering. Springer. pág. 140 y siguientes . ISBN 978-3-540-42420-8.
16. U. Trotenberg; CW Oosterlee; A. Schüller (2001). Multired. Prensa académica. ISBN 978-0-12-701070-0.
17. Albert Cohen (2003). Análisis numérico de métodos wavelet. Elsevier. pág. 44. ISBN 978-0-444-51124-9.
18. U. Trotenberg; CW Oosterlee; A. Schüller (2001). "Capítulo 9: Multired adaptativa". Multired . Prensa académica. pag. 356.ISBN​ 978-0-12-701070-0.
19. Yair Shapira (2003). "Multimalla algebraica". Multimalla basada en matrices: teoría y aplicaciones . Springer. pág. 66. ISBN 978-1-4020-7485-1.
20. U. Trotenberg; CW Oosterlee; A. Schüller (2001). Multired. Prensa académica. pag. 417.ISBN​ 978-0-12-701070-0.
21. Xu, J. y Zikatanov, L., 2017. Métodos multimalla algebraica. Acta Numerica, 26, págs. 591-721. [1]
22. Hackbusch, Wolfgang (1985). "Métodos parabólicos de múltiples cuadrículas". Métodos de computación en ciencias aplicadas e ingeniería, VI : 189-197. ISBN 9780444875976. Recuperado el 1 de agosto de 2015 .
23. Horton, Graham (1992). "El método multigrid de tiempo paralelo". Communications in Applied Numerical Methods . 8 (9): 585–595. doi :10.1002/cnm.1630080906.
24. Young-Ju Lee, Jinbiao Wu, Jinchao Xu y Ludmil Zikatanov, Métodos de corrección de subespacios robustos para sistemas casi singulares, Modelos matemáticos y métodos en ciencias aplicadas, vol. 17, n.º 11, págs. 1937-1963 (2007)

Referencias

• GP Astrachancev (1971), Un método iterativo para resolver problemas de redes elípticas. URSS Comp. Math. Math. Phys. 11, 171–182.
• NS Bakhvalov (1966), Sobre la convergencia de un método de relajación con restricciones naturales en el operador elíptico. URSS Comp. Math. Math. Phys. 6, 101–13.
• Achi Brandt (abril de 1977), "Soluciones adaptativas multinivel para problemas de valores en la frontera", Mathematics of Computation , 31 : 333–90.
• William L. Briggs, Van Emden Henson y Steve F. McCormick (2000), A Multigrid Tutorial (2.ª ed.), Filadelfia: Society for Industrial and Applied Mathematics , ISBN 0-89871-462-1 . 
• RP Fedorenko (1961), Un método de relajación para resolver ecuaciones diferenciales elípticas. URSS Comput. Math. Math. Phys. 1, pág. 1092.
• RP Fedorenko (1964), La velocidad de convergencia de un proceso iterativo. URSS Comput. Math. Math. Phys. 4, pág. 227.
• Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). "Sección 20.6. Métodos multimalla para problemas de valores en la frontera". Recetas numéricas: el arte de la computación científica (3.ª ed.). Nueva York: Cambridge University Press. ISBN 978-0-521-88068-8.

Enlaces externos

• Repositorio para métodos de agregación, corrección de defectos, descomposición de dominios, multiescala, multinivel y multicuadrícula
• Tutorial de multicuadrícula
• Tutorial de cuadrículas múltiples algebraicas
• Enlaces a presentaciones de AMG