Método multigrid

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 de multirresolución , muy útiles en problemas que exhiben múltiples escalas de comportamiento. Por ejemplo, muchos métodos de relajación básicos 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 así como precondicionadores .

La idea principal del método multigrid 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 en la malla fina, realizada periódicamente, resolviendo un problema grueso . Este problema grueso, si bien es más económico de resolver, es similar al problema de la malla fina, ya que también presenta errores de longitud de onda corta y larga. También puede resolverse mediante una combinación de relajación y el uso de mallas aún más gruesas. Este proceso recursivo se repite hasta alcanzar una malla donde el costo de la solución directa es insignificante en comparación con el costo de una iteración de relajación en la malla fina. Este ciclo multigrid reduce típicamente todos los componentes del error en una cantidad fija, acotada muy por debajo de uno, independientemente del tamaño de la malla fina. La aplicación típica del método multigrid se encuentra en la solución numérica de ecuaciones diferenciales parciales elípticas en dos o más dimensiones. ^{[ 2 ]}

Los métodos multigrid pueden aplicarse 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 actualmente. A diferencia de otros métodos, los métodos multigrid son generales, ya que pueden tratar regiones y condiciones de contorno arbitrarias . No dependen de la separabilidad de las ecuaciones ni de 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 complejos, como las ecuaciones de elasticidad de Lamé o las ecuaciones de Navier-Stokes . ^{[ 4 ]}

Existen muchas variantes de algoritmos multigrid, pero la característica común es que se considera una jerarquía de discretizaciones (rejillas). Los pasos importantes son: ^{[ 5 ] [ 6 ]}

• Suavizado : reducción de errores de alta frecuencia, por ejemplo, mediante el uso de varias iteraciones del método de Gauss-Seidel .
• Cálculo residual : cálculo del error residual después de la(s) operación(es) de suavizado.
• Restricción : reducción del muestreo del error residual a una cuadrícula más gruesa.
• Interpolación o prolongación : interpolar una corrección calculada en una malla más gruesa a una malla más fina.
• Corrección : Añadir una solución de malla más gruesa prolongada a la malla más fina.

Existen diversas opciones de métodos multigrid con diferentes ventajas y desventajas en cuanto a la velocidad de resolución de una sola iteración y la tasa de convergencia de dicha iteración. Los tres tipos principales son V-Cycle, F-Cycle y W-Cycle. Estos se diferencian en qué ciclos de grano grueso se realizan por cada iteración fina, y en cuántos. El algoritmo V-Cycle ejecuta un ciclo V de grano grueso. F-Cycle realiza un ciclo V de grano grueso seguido de un ciclo F de grano grueso, mientras que cada ciclo W realiza dos ciclos W de grano grueso por iteración. Para un problema discreto en 2D , F-Cycle requiere un 83 % más de tiempo de cálculo que una iteración de V-Cycle, mientras que una iteración de W-Cycle requiere un 125 % más. Si el problema se plantea en un dominio 3D, entonces una iteración de ciclo F y una iteración de ciclo W requieren aproximadamente un 64 % y un 75 % más de tiempo respectivamente que una iteración de ciclo V sin considerar los costos generales . Por lo general, el ciclo W produce una convergencia similar a la del ciclo F. Sin embargo, en casos de problemas de convección-difusión con números de Péclet altos , el ciclo W puede mostrar una superioridad en su tasa de convergencia por iteración sobre el ciclo F. La elección de operadores de suavizado es extremadamente diversa, ya que incluyen métodos de subespacio de Krylov y pueden ser precondicionados .

Cualquier iteración del ciclo de multigrid geométrico se realiza sobre una jerarquía de mallas y, por lo tanto, puede codificarse mediante recursión. Dado que la función se llama a sí misma con parámetros más pequeños (más gruesos), la recursión se detiene en la malla más gruesa. En los casos en que el sistema tiene un número de condición alto , el procedimiento de corrección se modifica de manera que solo una fracción de la solución de la malla más gruesa prolongada se añade a la malla más fina.

Este enfoque tiene la ventaja, frente a otros métodos, de que su rendimiento suele ser lineal 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 proporcional al número de incógnitas.

Supongamos que tenemos una ecuación diferencial que puede resolverse aproximadamente (con una precisión dada) en una cuadrícula.${\displaystyle i}$con una densidad de puntos de cuadrícula determinada${\displaystyle N_{i}}$Supongamos además que existe una solución en cualquier cuadrícula.${\displaystyle N_{i}}$puede obtenerse con un esfuerzo determinado${\displaystyle W_{i}=\rho KN_{i}}$a partir de una solución en una cuadrícula más gruesa${\displaystyle i+1}$. Aquí,${\displaystyle \rho =N_{i+1}/N_{i}<1}$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${\displaystyle K}$es algún modelado constante del esfuerzo de calcular el resultado para un punto de la cuadrícula.

A continuación se obtiene 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}}$$

Y en particular, encontramos para la cuadrícula más fina${\displaystyle N_{1}}$eso $${\displaystyle W_{1}=W_{2}+\rho KN_{1}}$$ Combinando estas dos expresiones (y usando${\displaystyle N_{k}=\rho ^{k-1}N_{1}}$) da $${\displaystyle W_{1}=KN_{1}\sum _{p=0}^{n}\rho ^{p}}$$

Utilizando la serie geométrica , encontramos entonces (para un valor finito)${\displaystyle n}$) $${\displaystyle W_{1}<KN_{1}{\frac {1}{1-\rho }}}$$

es decir, se puede obtener una solución en${\displaystyle O(N)}$tiempo. Cabe mencionar que hay una excepción a la${\displaystyle O(N)}$Por ejemplo, el multigrid de ciclo W se utiliza en un problema 1D; daría como resultado:${\displaystyle O(N\log N)}$complejidad.

Un método multigrid con una tolerancia intencionalmente reducida puede usarse como un precondicionador eficiente para un solucionador iterativo externo, por ejemplo, ^{[ 7 ].} La solución aún puede obtenerse en${\displaystyle O(N)}$tanto en el caso de utilizar el método multigrid como solucionador como en el caso de que se emplee dicho método. El preacondicionamiento multigrid se utiliza en la práctica incluso para sistemas lineales, normalmente con un ciclo por iteración, por ejemplo, en Hypre . Su principal ventaja frente a un solucionador puramente multigrid resulta especialmente clara para problemas no lineales, como los problemas de valores propios .

Si la matriz de la ecuación original o de un problema de valores propios es simétrica definida positiva (SPD), el precondicionador también se suele construir como SPD, de modo que se puedan seguir utilizando los métodos iterativos estándar de gradiente conjugado (CG) . Estas restricciones SPD impuestas pueden complicar la construcción del precondicionador, por ejemplo, al requerir un suavizado previo y posterior coordinado. Sin embargo, se ha demostrado ^{[ 8 ]} que los métodos de descenso más pronunciado precondicionado y CG flexible para sistemas lineales SPD, así como LOBPCG para problemas de valores propios simétricos, son robustos si el precondicionador no es SPD.

Originalmente descrito en la tesis doctoral de Xu ^{[ 9 ]} y publicado posteriormente en Bramble-Pasciak-Xu ^{[ 10 ],} el precondicionador 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 de subespacios ^{[ 11 ]} , el precondicionador BPX es un método de corrección de subespacios paralelo, mientras que el ciclo V clásico es un método de corrección de subespacios sucesivo. Se sabe que el precondicionador BPX es intrínsecamente 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.

Los métodos multigrid pueden generalizarse de muchas maneras diferentes. Pueden aplicarse de forma natural en la solución de ecuaciones diferenciales parciales parabólicas con discretización temporal, o directamente a ecuaciones diferenciales parciales dependientes del tiempo . ^{[ 12 ]} Se están llevando a cabo investigaciones sobre técnicas multinivel para ecuaciones diferenciales parciales hiperbólicas . ^{[ 13 ]} Los métodos multigrid también pueden aplicarse a ecuaciones integrales o a problemas de física estadística . ^{[ 14 ]}

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

El método multigrid adaptativo presenta un refinamiento de malla adaptativo , es decir, ajusta la malla a medida que avanza el cálculo, de una manera que depende del propio cálculo. ^{[ 18 ]} La idea es aumentar la resolución de la malla solo en las regiones de la solución donde sea necesario.

Las extensiones prácticas importantes de los métodos multigrid incluyen técnicas donde no se utiliza ninguna ecuación diferencial parcial ni fondo de problema geométrico 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. (Más generalmente, las incógnitas de la malla gruesa pueden ser combinaciones lineales particulares de las incógnitas de la malla fina). Por lo tanto, los métodos AMG se convierten en solucionadores de caja negra para ciertas clases de matrices dispersas . El AMG se considera ventajoso principalmente cuando el multigrid geométrico es demasiado difícil de aplicar, ^{[ 20 ]} pero a menudo se usa 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 "multigrid algebraico" se entienden desde un punto de vista abstracto. Desarrollaron un marco unificado y los métodos de multigrid algebraico existentes pueden derivarse de manera coherente. Se derivó una teoría abstracta sobre cómo construir espacios gruesos óptimos, así como espacios cuasi-óptimos. Cabe destacar que este resultado apareció por primera vez en una nota sobre multigrid algebraico de Brannick y Zikatanov y fue simplemente reescrito en el artículo de revisión. Además, demostraron que, bajo supuestos apropiados, el método AMG abstracto de dos niveles converge uniformemente con respecto al tamaño del sistema lineal, la variación de coeficientes y la anisotropía. Su marco abstracto abarca 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 suavizada y no suavizada, y el AMGe espectral.

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 ]} a diferencia de los métodos clásicos de Runge-Kutta o los métodos lineales multipaso , pueden ofrecer concurrencia en la dirección temporal. El conocido método de integración paralelo en el tiempo de Parareal también puede reformularse como un multigrid de dos niveles en el tiempo.

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 la elasticidad lineal para materiales casi incompresibles. Típicamente, el problema principal para resolver tales sistemas casi singulares se reduce a tratar el operador casi singular dado por${\displaystyle A+\varepsilon M}$robustamente con respecto al parámetro positivo pero pequeño${\displaystyle \varepsilon }$. Aquí${\displaystyle A}$es un operador semidefinido simétrico con un gran espacio nulo , mientras que${\displaystyle M}$es un operador simétrico definido positivo . 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 parámetros (por ejemplo, tamaño de malla y parámetros físicos como la relación de Poisson que aparecen en el operador casi singular) tasa de convergencia independiente del método multigrid aplicado a tales sistemas casi singulares, ^{[ 24 ]} es decir, en cada cuadrícula, se debe construir una descomposición espacial sobre la cual se aplica el suavizado, de modo que el espacio nulo de la parte singular del operador casi singular debe estar incluido en la suma de los espacios nulos locales, la intersección del espacio nulo y los espacios locales resultantes de las descomposiciones espaciales.

• Enlaces a las presentaciones de AMG