Método de red múltiple - Multigrid method

En el análisis numérico , un método de redes múltiples ( 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 denominadas métodos multirresolución , muy útiles en problemas que presentan 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 deben tratarse de manera diferente, como en un enfoque de análisis de Fourier para multirredes. Los métodos MG se pueden utilizar como solucionadores y como preacondicionadores .

La idea principal de la red múltiple 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 red fina de vez en cuando, lograda resolviendo un problema general . El problema grueso, aunque más barato de resolver, es similar al problema de la cuadrícula 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 rejillas aún más gruesas. Este proceso recursivo se repite hasta que se alcanza una cuadrícula 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 cuadrícula fina. Este ciclo de redes múltiples normalmente reduce todos los componentes de error en una cantidad fija delimitada muy por debajo de uno, independientemente del tamaño de la malla de la malla fina. La aplicación típica de multirredes es la solución numérica de ecuaciones diferenciales parciales elípticas en dos o más dimensiones.

Los métodos de redes múltiples 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 de redes múltiples. En estos casos, los métodos de redes múltiples se encuentran entre las técnicas de solución más rápidas que se conocen en la actualidad. A diferencia de otros métodos, los métodos de redes múltiples son generales porque pueden tratar regiones arbitrarias y condiciones de contorno . 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 complicados, como las ecuaciones de elasticidad de Lamé o las ecuaciones de Navier-Stokes .

Algoritmo

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

Hay muchas variaciones de algoritmos de redes múltiples, pero las características comunes son que se considera una jerarquía de discretizaciones (cuadrículas). Los pasos importantes son:

Suavizado : reducción de errores de alta frecuencia, por ejemplo, utilizando algunas iteraciones del método Gauss-Seidel .
Cálculo residual : cálculo del error residual después de las operaciones de suavizado.
Restricción : reducción de resolución del error residual a una cuadrícula más gruesa.
Interpolación o prolongación : interpolación de 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 a la rejilla más fina.

Hay muchas opciones de métodos de redes múltiples con diferentes compensaciones entre la velocidad de resolución de una sola iteración y la tasa de convergencia con dicha iteración. Los 3 tipos principales son V-Cycle, F-Cycle y W-Cycle. Para un problema 2D discreto , F-Cycle tarda un 83% más en calcularse que una iteración de V-Cycle, mientras que una iteración de W-Cycle tarda un 125% más. Si el problema se configura en un dominio 3D, entonces una iteración de F-Cycle y una iteración de W-Cycle toman aproximadamente un 64% y un 75% más de tiempo, respectivamente, que una iteración de V-Cycle que ignora 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 los operadores de suavizado es extremadamente diversa, ya que incluyen métodos subespaciales de Krylov y pueden preacondicionarse .

Cualquier iteración de ciclo de cuadrícula múltiple geométrica se realiza en una jerarquía de cuadrículas y, por lo tanto, se puede codificar mediante recursividad. 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 recursividad. 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 rejilla más gruesa prolongada se agregue a la rejilla más fina.

Estos pasos se pueden utilizar como se muestra en el pseudocódigo de estilo MATLAB para 1 iteración de V-Cycle Multigrid :

function phi = V_Cycle(phi,f,h)
    % Recursive V-Cycle Multigrid for solving the Poisson equation (\nabla^2 phi = f) on a uniform grid of spacing h

    % Pre-Smoothing
    phi = smoothing(phi,f,h);

    % Compute Residual Errors
    r = residual(phi,f,h);

    % Restriction
    rhs = restriction(r);

    eps = zeros(size(rhs));

    % stop recursion at smallest grid size, otherwise continue recursion
    if smallest_grid_size_is_achieved
        eps = smoothing(eps,rhs,2*h);
    else
        eps = V_Cycle(eps,rhs,2*h);
    end

    % Prolongation and Correction
    phi = phi + prolongation(eps);

    % Post-Smoothing
    phi = smoothing(phi,f,h);
end

Lo siguiente representa multigrid F-ciclo . Este ciclo de redes múltiples es más lento que el ciclo V por iteración, pero da como resultado una convergencia más rápida.

function phi = F_Cycle(phi,f,h)
    % Recursive F-cycle multigrid for solving the Poisson equation (\nabla^2 phi = f) on a uniform grid of spacing h

    % Pre-smoothing
    phi = smoothing(phi,f,h);

    % Compute Residual Errors
    r = residual(phi,f,h);

    % Restriction
    rhs = restriction(r);

    eps = zeros(size(rhs));

    % stop recursion at smallest grid size, otherwise continue recursion
    if smallest_grid_size_is_achieved
        eps = smoothing(eps,rhs,2*h);
    else
        eps = F_Cycle(eps,rhs,2*h);
    end

    % Prolongation and Correction
    phi = phi + prolongation(eps);

    % Re-smoothing
    phi = smoothing(phi,f,h);

    % Compute residual errors
    r = residual(phi,f,h);

    % Restriction
    rhs = restriction(r);

    % stop recursion at smallest grid size, otherwise continue recursion
    if smallest_grid_size_is_achieved
        eps = smoothing(eps,rhs,2*h);
    else
        eps = V_Cycle(eps,rhs,2*h);
    end

    % Prolongation and Correction
    phi = phi + prolongation(eps);

    % Post-smoothing
    phi = smoothing(phi,f,h);
end

De manera similar, los procedimientos se pueden modificar como se muestra en el pseudocódigo de estilo MATLAB para 1 iteración de red múltiple de ciclo W para una tasa de convergencia incluso superior en ciertos casos:

function phi = W_cycle(phi,f,h)
    % Recursive W-cycle multigrid for solving the Poisson equation (\nabla^2 phi = f) on a uniform grid of spacing h

    % Pre-smoothing
    phi = smoothing(phi,f,h);

    % Compute Residual Errors
    r = residual(phi,f,h);

    % Restriction
    rhs = restriction(r);

    eps = zeros(size(rhs));

    % stop recursion at smallest grid size, otherwise continue recursion
    if smallest_grid_size_is_achieved
        eps = smoothing(eps,rhs,2*h);
    else
        eps = W_cycle(eps,rhs,2*h);
    end

    % Prolongation and correction
    phi = phi + prolongation(eps);

    % Re-smoothing
    phi = smoothing(phi,f,h);

    % Compute residual errors
    r = residual(phi,f,h);

    % Restriction
    rhs = restriction(r);

    % stop recursion at smallest grid size, otherwise continue recursion
    if smallest_grid_size_is_achieved
        eps = smoothing(eps,rhs,2*h);
    else
        eps = W_cycle(eps,rhs,2*h);
    end

    % Prolongation and correction
    phi = phi + prolongation(eps);

    % Post-smoothing
    phi = smoothing(phi,f,h);
end

Costo computacional

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 redes.

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

Suponga que se tiene una ecuación diferencial que se puede resolver aproximadamente (con una precisión determinada) en una cuadrícula con una densidad de puntos de cuadrícula determinada . Suponga 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í, está la proporción de puntos de la cuadrícula en las cuadrículas "vecinas" y se supone que es constante en toda la jerarquía de la cuadrícula, y es un modelado constante del esfuerzo de calcular el resultado para un punto de la 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}$

Luego se obtiene la siguiente relación de recurrencia para el esfuerzo de obtener la solución en la red : ${\ Displaystyle k}$

{\ Displaystyle W_ {k} = W_ {k + 1} + \ rho KN_ {k}}

Ejemplo de tasas de convergencia de ciclos de redes múltiples en comparación con otros operadores de suavizado.

Y en particular, encontramos para la mejor cuadrícula que ${\ Displaystyle N_ {1}}$

{\ Displaystyle W_ {1} = W_ {2} + \ rho KN_ {1}}

La combinación de estas dos expresiones (y el uso ) da ${\ 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 (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 hay una excepción a la red múltiple de ciclo W, por ejemplo, utilizada en un problema de 1D; resultaría en complejidad. ${\ Displaystyle O (N)}$ ${\ Displaystyle O (N)}$ ${\ Displaystyle O (Nlog (N))}$

Preacondicionamiento de redes múltiples

Un método de redes múltiples con una tolerancia intencionalmente reducida se puede utilizar como un preacondicionador eficiente para un solucionador iterativo externo, por ejemplo, la solución aún puede obtenerse a tiempo, así como en el caso en el que se utilice el método de redes múltiples como un solucionador. El preacondicionamiento de redes múltiples 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 es particularmente clara para problemas no lineales, por ejemplo, problemas de valores propios . ${\ Displaystyle O (N)}$

Si la matriz de la ecuación original o un problema de valor propio es simétrico positivo definido (SPD), el preacondicionador también se construye comúnmente para ser SPD, de modo que los métodos iterativos estándar de gradiente conjugado (CG) aún se pueden usar. Dichas restricciones de SPD impuestas pueden complicar la construcción del preacondicionador, por ejemplo, requiriendo un suavizado previo y posterior coordinado. Sin embargo, el descenso más empinado preacondicionado y los métodos CG flexibles para sistemas lineales SPD y LOBPCG para problemas de valores propios simétricos se muestran todos robustos si el preacondicionador no es SPD.

Preacondicionador Bramble-Pasciak-Xu

Descrito originalmente en el Ph.D. de Xu. tesis y posteriormente publicado en Bramble-Pasciak-Xu, el precondicionador BPX es uno de los dos enfoques principales de redes múltiples (el otro es el algoritmo clásico de redes múltiples 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, 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 clásico de redes múltiples de ciclo en V. El método ha sido ampliamente utilizado por investigadores y profesionales desde 1990.

Métodos multirredes generalizados

Los métodos de redes múltiples se pueden generalizar de muchas formas diferentes. Pueden aplicarse de forma natural en una solución escalonada en el tiempo de ecuaciones diferenciales parciales parabólicas , o pueden aplicarse directamente a ecuaciones diferenciales parciales dependientes del tiempo . Se están realizando investigaciones sobre técnicas multinivel para ecuaciones diferenciales parciales hiperbólicas . Los métodos de redes múltiples también se pueden aplicar a ecuaciones integrales o para problemas de física estadística .

Otro conjunto de métodos de resolución múltiple se basa en ondículas . Estos métodos de ondículas se pueden combinar con métodos de redes múltiples. Por ejemplo, un uso de wavelets es reformular el enfoque de elementos finitos en términos de un método multinivel.

La red múltiple adaptativa exhibe un refinamiento de la malla adaptativa , es decir, ajusta la red a medida que avanza el cálculo, de una manera que depende del cálculo en sí. La idea es aumentar la resolución de la cuadrícula solo en las regiones de la solución donde se necesita.

Multirrejilla algebraica (AMG)

Extensiones prácticamente importantes de los métodos de redes múltiples incluyen técnicas en las que no se utilizan ecuaciones diferenciales parciales ni antecedentes de problemas geométricos para construir la jerarquía de niveles múltiples. Dichos métodos algebraicos de redes múltiples (AMG) construyen su jerarquía de operadores directamente a partir de la matriz del sistema. En la AMG clásica, 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 cuadrícula gruesa pueden ser combinaciones lineales particulares de incógnitas de 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 multirrejilla geométrica es demasiado difícil de aplicar, pero a menudo se usa simplemente porque evita la codificación necesaria para una verdadera implementación de multirredes. 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 general de Jinchao Xu y Ludmil Zikatanov, los métodos de "red múltiple algebraica" se entienden desde un punto de vista abstracto. Desarrollaron un marco unificado y los métodos algebraicos de redes múltiples existentes pueden derivarse de manera coherente. Se derivó una teoría abstracta sobre cómo construir un espacio aproximado óptimo, así como espacios cuasi-óptimos. 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 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 suavizada y sin suavizar y el AMG espectral.

Métodos de cuadrícula múltiple en el tiempo

También se han adoptado métodos de redes múltiples para la solución de problemas de valor inicial . De particular interés aquí son los métodos de redes múltiples paralelas en el tiempo: a diferencia de los métodos clásicos de Runge-Kutta o de múltiples pasos lineales , pueden ofrecer concurrencia en la dirección temporal. El conocido método de integración paralela en el tiempo de Parareal también se puede reformular como una red múltiple de dos niveles en el tiempo.

Multirredes para problemas casi singulares

Surgen problemas casi singulares en una serie de importantes aplicaciones físicas y de ingeniería. Se puede encontrar un ejemplo simple pero importante de problemas casi singulares en la formulación de desplazamiento de la elasticidad lineal para materiales casi incompresibles. Por lo general, el principal problema para resolver estos 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 semidefinito 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 multirredes robusto y rápido para problemas tan singulares. Se ha proporcionado una guía general como principio de diseño para lograr parámetros (p. Ej., 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 de redes múltiples aplicado a tales sistemas casi singulares, es decir, en cada cuadrícula, una descomposición espacial basada en la cual se aplica el suavizado, debe construirse de modo que el espacio nulo de la parte singular del operador casi singular debe incluirse en la suma de los espacios nulos locales, la intersección del nulo el espacio y los espacios locales resultantes de las descomposiciones espaciales. ${\ Displaystyle A + \ varepsilon M}$ ${\ Displaystyle \ varepsilon}$ ${\ Displaystyle A}$ ${\ Displaystyle M}$

Notas

Referencias

GP Astrachancev (1971), Un método iterativo para resolver problemas de redes elípticas . URSS Comp. Matemáticas. Matemáticas. 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. Matemáticas. Matemáticas. Phys. 6, 101-13.
Achi Brandt (abril de 1977), " Soluciones adaptativas multinivel para problemas de valores en la frontera ", Matemáticas de la computación , 31 : 333–90.
William L. Briggs, Van Emden Henson y Steve F. McCormick (2000), A Multigrid Tutorial (2ª ed.), Filadelfia: Sociedad de Matemáticas Industriales y Aplicadas , ISBN 0-89871-462-1 .
RP Fedorenko (1961), Un método de relajación para resolver ecuaciones en diferencias elípticas . Computación de la URSS. Matemáticas. Matemáticas. Phys. 1, pág. 1092.
RP Fedorenko (1964), La velocidad de convergencia de un proceso iterativo. Computación de la URSS. Matemáticas. Matemáticas. Phys. 4, pág. 227.
Presione, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). "Sección 20.6. Métodos de redes múltiples para problemas de valor límite" . Recetas numéricas: el arte de la informática científica (3ª ed.). Nueva York: Cambridge University Press. ISBN 978-0-521-88068-8.

Languages

In other projects