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 redes múltiples. [1]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 básico . 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. [2]
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. [3] En estos casos, los métodos de redes múltiples 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 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 . [4]
Algoritmo
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: [5] [6]
- 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 la (s) operación (es) 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 de tiempo 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 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 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 se pueden preacondicionar .
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 : función phi = V_Cycle ( phi, f, h ) % Recursivo V-Cycle Multigrid para resolver la ecuación de Poisson (\ nabla ^ 2 phi = f) en una cuadrícula uniforme de espaciado h% Pre-suavizadophi = suavizado ( phi , f , h ); % Calcular errores residualesr = residual ( phi , f , h ); % De restricciónrhs = restricción ( r ); eps = ceros ( tamaño ( dcha. )); % detiene la recursividad en el tamaño de cuadrícula más pequeño; de lo contrario, continúa la recursividadsi se ha conseguido el tamaño_de_rejilla_más pequeño eps = suavizado ( eps , rhs , 2 * h ); más eps = V_Cycle ( eps , rhs , 2 * h ); final % De prolongación y correcciónphi = phi + prolongación ( eps ); % Post-suavizadophi = suavizado ( phi , f , h ); final | 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. función phi = F_Cycle ( phi, f, h ) % De cuadrícula múltiple de ciclo F recursivo para resolver la ecuación de Poisson (\ nabla ^ 2 phi = f) en una cuadrícula uniforme de espaciado h% Pre-suavizadophi = suavizado ( phi , f , h ); % Calcular errores residualesr = residual ( phi , f , h ); % De restricciónrhs = restricción ( r ); eps = ceros ( tamaño ( dcha. )); % detiene la recursividad en el tamaño de cuadrícula más pequeño; de lo contrario, continúa la recursividadsi se ha conseguido el tamaño_de_rejilla_más pequeño eps = suavizado ( eps , rhs , 2 * h ); más eps = F_Cycle ( eps , rhs , 2 * h ); final % De prolongación y correcciónphi = phi + prolongación ( eps ); % Re-suavizadophi = suavizado ( phi , f , h ); % Calcular errores residualesr = residual ( phi , f , h ); % De restricciónrhs = restricción ( r ); % detiene la recursividad en el tamaño de cuadrícula más pequeño; de lo contrario, continúa la recursividadsi se ha conseguido el tamaño_de_rejilla_más pequeño eps = suavizado ( eps , rhs , 2 * h ); más eps = V_Cycle ( eps , rhs , 2 * h ); final % De prolongación y correcciónphi = phi + prolongación ( eps ); % Post-suavizadophi = suavizado ( phi , f , h ); final | 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: función phi = W_cycle ( phi, f, h ) % Red múltiple de ciclo W recursivo para resolver la ecuación de Poisson (\ nabla ^ 2 phi = f) en una red uniforme de espaciado h% Pre-suavizadophi = suavizado ( phi , f , h ); % Calcular errores residualesr = residual ( phi , f , h ); % De restricciónrhs = restricción ( r ); eps = ceros ( tamaño ( dcha. )); % detiene la recursividad en el tamaño de cuadrícula más pequeño; de lo contrario, continúa la recursividadsi se ha conseguido el tamaño_de_rejilla_más pequeño eps = suavizado ( eps , rhs , 2 * h ); más eps = W_cycle ( eps , rhs , 2 * h ); final % Prolongación y correcciónphi = phi + prolongación ( eps ); % Re-suavizadophi = suavizado ( phi , f , h ); % Calcular errores residualesr = residual ( phi , f , h ); % De restricciónrhs = restricción ( r ); % detiene la recursividad en el tamaño de cuadrícula más pequeño; de lo contrario, continúa la recursividadsi se ha conseguido el tamaño_de_rejilla_más pequeño eps = suavizado ( eps , rhs , 2 * h ); más eps = W_cycle ( eps , rhs , 2 * h ); final % Prolongación y correcciónphi = phi + prolongación ( eps ); % Post-suavizadophi = suavizado ( phi , f , h ); final |
Costo computacional
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 uno 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 una solución en cualquier cuadrícula se puede obtener con un esfuerzo determinado de una solución en una cuadrícula más gruesa . Aquí, es la proporción de puntos de cuadrícula en cuadrículas "vecinas" y se supone que es constante en toda la jerarquía de cuadrícula, y es un modelado constante del esfuerzo de calcular el resultado para un punto de la cuadrícula.
Luego se obtiene la siguiente relación de recurrencia para el esfuerzo de obtener la solución en la cuadrícula :
Y en particular, encontramos para la mejor cuadrícula que
Combinando estas dos expresiones (y usando ) da
Usando la serie geométrica , encontramos (para finito)
es decir, se puede obtener una solución en hora. Cabe mencionar que existe una excepción a laes decir, red múltiple de ciclo W utilizada en un problema 1D; resultaría encomplejidad.
Preacondicionamiento de redes múltiples
Un método de red múltiple con una tolerancia reducida intencionalmente se puede utilizar como un preacondicionador eficiente para un solucionador iterativo externo, por ejemplo, [7] La solución aún se puede obtener entiempo, así como en el caso en el que el método multigrid se utiliza como 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 .
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. Tales 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 [8] robustos si el preacondicionador no es SPD.
Preacondicionador Bramble-Pasciak-Xu
Descrito originalmente en el Ph.D. de Xu. tesis [9] y posteriormente publicada en Bramble-Pasciak-Xu, [10] 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, [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 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 . [12] Se están realizando investigaciones sobre técnicas multinivel para ecuaciones diferenciales parciales hiperbólicas . [13] Los métodos de redes múltiples también se pueden aplicar a ecuaciones integrales o para problemas de física estadística . [14]
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. [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 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í. [18] 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. [19] Estos 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, [20] pero a menudo se utiliza 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 [21] 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 tiempo
También se han adoptado métodos de redes múltiples para la solución de problemas de valor inicial . [22] De particular interés aquí son los métodos de redes múltiples paralelas en el tiempo: [23] 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. Típicamente, el principal problema para resolver estos sistemas casi singulares se reduce a tratar el operador casi singular dado por robustamente con respecto al parámetro positivo, pero pequeño . Aquíes un operador semidefinido simétrico con un gran espacio nulo , mientras quees 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 estos 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 debe incluirse en la suma de los espacios nulos locales, la intersección del espacio nulo y los espacios locales resultantes de las descomposiciones espaciales.
Notas
- ^ Roman Wienands; Wolfgang Joppich (2005). Análisis práctico de Fourier para métodos multirredes . Prensa CRC. pag. 17. ISBN 978-1-58488-492-7.
- ^ U. Trottenberg; CW Oosterlee; A. Schüller (2001). Multirredes . Prensa académica. ISBN 978-0-12-701070-0.
- ^ Yu Zhu; Andreas C. Cangellaris (2006). Métodos de elementos finitos de redes múltiples para el modelado de campos electromagnéticos . Wiley. pag. 132 y sigs . ISBN 978-0-471-74110-7.
- ^ Shah, Tasneem Mohammad (1989). Análisis del método multirredes (Tesis). Universidad de Oxford. Código bibliográfico : 1989STIN ... 9123418S .
- ^ MT Heath (2002). "Sección 11.5.7 Métodos de redes múltiples" . Computación científica: una encuesta introductoria . Educación superior McGraw-Hill. pag. 478 ff . ISBN 978-0-07-112229-0.
- ^ P. Wesseling (1992). Introducción a los métodos de redes múltiples . Wiley. ISBN 978-0-471-93083-9.
- ^ Andrew V Knyazev, Klaus Neymeyr. Solución eficiente de problemas de valores propios simétricos utilizando preacondicionadores de redes múltiples en el método de gradiente conjugado de bloques localmente óptimo . Transacciones electrónicas sobre análisis numérico, 15, 38–55, 2003.
- ^ Henricus Bouwmeester, Andrew Dougherty, Andrew V Knyazev. Preacondicionamiento no simétrico para métodos de gradiente conjugado y descenso más pronunciado . Procedia Computer Science, Volumen 51, páginas 276–285, Elsevier, 2015. doi : 10.1016 / j.procs.2015.05.241
- ^ Xu, Jinchao. Teoría de los métodos multinivel. Vol. 8924558. Ithaca, NY: Cornell University, 1989.
- ^ Zarza, James H., Joseph E. Pasciak y Jinchao Xu. "Preacondicionadores multinivel en paralelo". Matemáticas de la Computación 55, no. 191 (1990): 1–22.
- ^ Xu, Jinchao. "Métodos iterativos por descomposición espacial y corrección subespacial". Revista SIAM 34, no. 4 (1992): 581-613.
- ^ F. Hülsemann; M. Kowarschik; M. Mohr; U. Rüde (2006). "Multirredes geométricas paralelas" . En Are Magnus Bruaset; Aslak Tveito (eds.). Solución numérica de ecuaciones diferenciales parciales en computadoras paralelas . Birkhäuser. pag. 165. ISBN 978-3-540-29076-6.
- ^ Por ejemplo, J. Blaz̆ek (2001). Dinámica de fluidos computacional: principios y aplicaciones . Elsevier. pag. 305. ISBN 978-0-08-043009-6. y Achi Brandt y Rima Gandlin (2003). "Multirredes para 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 . Saltador. pag. 369. ISBN 978-3-540-44333-9.
- ^ Achi Brandt (2002). "Computación científica multiescala: revisión" . En Timothy J. Barth; Tony Chan; Robert Haimes (eds.). Métodos multiescala y multirresolución: teoría y aplicaciones . Saltador. pag. 53. ISBN 978-3-540-42420-8.
- ^ 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 las notas de clase en ciencias e ingeniería computacionales. Saltador. pag. 140 ff . ISBN 978-3-540-42420-8.
|volume=
tiene texto extra ( ayuda ) - ^ U. Trottenberg; CW Oosterlee; A. Schüller (2001). Multirredes . ISBN 978-0-12-701070-0.
- ^ Albert Cohen (2003). Análisis numérico de métodos wavelet . Elsevier. pag. 44. ISBN 978-0-444-51124-9.
- ^ U. Trottenberg; CW Oosterlee; A. Schüller (2001). "Capítulo 9: Multirredes adaptables" . Multirredes . pag. 356. ISBN 978-0-12-701070-0.
- ^ Yair Shapira (2003). "Multirredes algebraicas" . Multirredes basadas en matrices: teoría y aplicaciones . Saltador. pag. 66. ISBN 978-1-4020-7485-1.
- ^ U. Trottenberg; CW Oosterlee; A. Schüller (2001). Multirredes . pag. 417. ISBN 978-0-12-701070-0.
- ^ Xu, J. y Zikatanov, L., 2017. Métodos algebraicos de redes múltiples. Acta Numerica, 26, págs. 591-721.
- ^ Hackbusch, Wolfgang (1985). "Métodos parabólicos de redes múltiples" . Métodos de computación en ciencias aplicadas e ingeniería, VI : 189-197 . Consultado el 1 de agosto de 2015 .
- ^ Horton, Graham (1992). "El método de redes múltiples paralelas en el tiempo". Comunicaciones en métodos numéricos aplicados . 8 (9): 585–595. doi : 10.1002 / cnm.1630080906 .
- ^ Young-Ju Lee, Jinbiao Wu, Jinchao Xu y Ludmil Zikatanov, Métodos robustos de corrección del subespacio 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. 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 (2a 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.
enlaces externos
- Repositorio para métodos de descomposición de dominios, corrección de defectos y multirredes, niveles, escalas, agregación
- Tutorial de redes múltiples
- Tutorial de cuadrícula múltiple algebraica
- Enlaces a presentaciones AMG