Método multipolar rápido

El método multipolar rápido ( FMM ) es una técnica numérica que se desarrolló para acelerar el cálculo de fuerzas de largo alcance en el problema de n cuerpos . Esto se logra expandiendo la función de Green del sistema mediante una expansión multipolar , que permite agrupar fuentes que se encuentran cerca unas de otras y tratarlas como si fueran una sola fuente. ^[1]

El FMM también se ha aplicado para acelerar el solucionador iterativo en el método de momentos (MOM) aplicado a problemas de electromagnetismo computacional , ^[2] y en particular en bioelectromagnetismo computacional . El FMM fue introducido por primera vez de esta manera por Leslie Greengard y Vladimir Rokhlin Jr. ^[3] y se basa en la expansión multipolar de la ecuación vectorial de Helmholtz . Al tratar las interacciones entre funciones de base lejanas utilizando el FMM, los elementos de matriz correspondientes no necesitan almacenarse explícitamente, lo que resulta en una reducción significativa en la memoria requerida. Si el FMM se aplica luego de manera jerárquica, puede mejorar la complejidad de los productos matriz-vector en un solucionador iterativo de a aritmética finita, es decir, dada una tolerancia , se garantiza que el producto matriz-vector esté dentro de una tolerancia La dependencia de la complejidad de la tolerancia es , es decir, la complejidad del FMM es . Esto ha ampliado el área de aplicabilidad del MOM a problemas mucho mayores de lo que era posible anteriormente. ${\displaystyle {\mathcal {O}}(N^{2})}$ ${\displaystyle {\mathcal {O}}(N)}$ ${\displaystyle \varepsilon }$ ${\displaystyle \varepsilon .}$ ${\displaystyle \varepsilon }$ ${\displaystyle {\mathcal {O}}(\log(1/\varepsilon ))}$ ${\displaystyle {\mathcal {O}}(N\log(1/\varepsilon ))}$

Se ha dicho que el FMM, introducido por Rokhlin Jr. y Greengard, es uno de los diez mejores algoritmos del siglo XX. ^[4] El algoritmo FMM reduce la complejidad de la multiplicación matriz-vector que involucra un cierto tipo de matriz densa que puede surgir de muchos sistemas físicos.

El FMM también se ha aplicado para tratar eficientemente la interacción de Coulomb en el método Hartree-Fock y en los cálculos de la teoría funcional de la densidad en química cuántica .

Bosquejo del algoritmo

Método multipolar rápido: interpolación de un polo en x=3 con un polinomio de Chebyshev de orden 5

En su forma más simple, el método multipolar rápido busca evaluar la siguiente función:

${\displaystyle f(y)=\sum _{\alpha =1}^{N}{\frac {\phi _{\alpha }}{y-x_{\alpha }}}}$,

donde son un conjunto de polos y son los pesos de polos correspondientes en un conjunto de puntos con . Esta es la forma unidimensional del problema, pero el algoritmo se puede generalizar fácilmente a múltiples dimensiones y núcleos distintos de . ${\displaystyle x_{\alpha }\in [-1,1]}$ ${\displaystyle \phi _{\alpha }\in \mathbb {C} }$ ${\displaystyle \{y_{1},\ldots ,y_{M}\}}$ ${\displaystyle y_{\beta }\in [-1,1]}$ ${\displaystyle (y-x)^{-1}}$

De manera ingenua, la evaluación de puntos requiere operaciones. La observación crucial detrás del método multipolar rápido es que si la distancia entre y es lo suficientemente grande, entonces se aproxima bien mediante un polinomio . Específicamente, sean los nodos de orden de Chebyshev y sean los polinomios de base de Lagrange correspondientes . Se puede demostrar que el polinomio de interpolación: ${\displaystyle f(y)}$ ${\displaystyle M}$ ${\displaystyle {\mathcal {O}}(MN)}$ ${\displaystyle y}$ ${\displaystyle x}$ ${\displaystyle (y-x)^{-1}}$ ${\displaystyle -1<t_{1}<\ldots <t_{p}<1}$ ${\displaystyle p\geq 2}$ ${\displaystyle u_{1}(y),\ldots ,u_{p}(y)}$

${\displaystyle {\frac {1}{y-x}}=\sum _{i=1}^{p}{\frac {1}{t_{i}-x}}u_{i}(y)+\epsilon _{p}(y)}$

converge rápidamente con orden polinomial, , siempre que el polo esté lo suficientemente alejado de la región de interpolación, y . Esto se conoce como "expansión local". ${\displaystyle |\epsilon _{p(y)}|<5^{-p}}$ ${\displaystyle |x|\geq 3}$ ${\displaystyle |y|<1}$

La aceleración del método multipolar rápido se deriva de esta interpolación: siempre que todos los polos estén "lejanos", evaluamos la suma solo en los nodos de Chebyshev a un costo de , y luego la interpolamos en todos los puntos deseados a un costo de : ${\displaystyle {\mathcal {O}}(Np)}$ ${\displaystyle {\mathcal {O}}(Mp)}$

${\displaystyle \sum _{\alpha =1}^{N}{\frac {\phi _{\alpha }}{y_{\beta }-x_{\alpha }}}=\sum _{i=1}^{p}u_{i}(y_{\beta })\sum _{\alpha =1}^{N}{\frac {1}{t_{i}-x_{\alpha }}}\phi _{\alpha }}$

Dado que , donde es la tolerancia numérica, el costo total es . ${\displaystyle p=-\log _{5}\epsilon }$ ${\displaystyle \epsilon }$ ${\displaystyle {\mathcal {O}}((M+N)\log(1/\epsilon ))}$

Para garantizar que los polos estén bien separados, se subdivide recursivamente el intervalo unitario de modo que solo los polos terminen en cada intervalo. Luego se utiliza la fórmula explícita dentro de cada intervalo y la interpolación para todos los intervalos que estén bien separados. Esto no estropea la escala, ya que se necesitan como máximo niveles dentro de la tolerancia dada. ${\displaystyle {\mathcal {O}}(p)}$ ${\displaystyle \log(1/\epsilon )}$

Véase también

• Simulación de Barnes-Hut
• Expansión multipolar
• Simulación de n -cuerpos

Referencias

1. Rokhlin, Vladimir (1985). "Solución rápida de ecuaciones integrales de la teoría clásica del potencial". J. Computational Physics, vol. 60, págs. 187-207.
2. Nader Engheta , William D. Murphy, Vladimir Rokhlin y Marius Vassiliou (1992), “El método multipolar rápido para el cálculo de dispersión electromagnética”, IEEE Transactions on Antennas and Propagation 40, 634–641.
3. "El método multipolar rápido". Archivado desde el original el 3 de junio de 2011. Consultado el 10 de diciembre de 2010 .
4. Cipra, Barry Arthur (16 de mayo de 2000). "Lo mejor del siglo XX: los editores nombran los 10 mejores algoritmos". SIAM News . 33 (4). Society for Industrial and Applied Mathematics : 2 . Consultado el 27 de febrero de 2019 .

Enlaces externos

• Gibson, Walton C. El método de momentos en electromagnetismo (3.ª ed.), Chapman & Hall/CRC, 2021. ISBN 9780367365066 . 
• Resumen del artículo original de Greengard y Rokhlin
• Un curso breve sobre métodos multipolares rápidos por Rick Beatson y Leslie Greengard.
• Animación JAVA del Método Multipolar Rápido Bonita animación del Método Multipolar Rápido con diferentes adaptaciones.

Software libre

• Puma-EM Un código electromagnético de método de momentos / método multipolar rápido multinivel, paralelizado y de código abierto de alto rendimiento.
• KIFMM3d El método multipolar 3D rápido independiente del núcleo (kifmm3d) es una nueva implementación de FMM que no requiere las expansiones multipolares explícitas del núcleo subyacente y se basa en evaluaciones del núcleo.
• PVFMM Una implementación paralela optimizada de KIFMM para calcular potenciales de fuentes de partículas y volumen.
• FastBEM Programas gratuitos y rápidos de elementos de contorno multipolares para resolver problemas de potencial 2D/3D, elasticidad, flujo de Stokes y acústicos.
• FastFieldSolvers mantiene la distribución de las herramientas, llamadas FastHenry y FastCap, desarrolladas en el MIT para la solución de ecuaciones de Maxwell y extracción de parásitos de circuitos (inductancia y capacitancia) utilizando el FMM.
• ExaFMM ExaFMM es un código FMM 3D compatible con CPU/GPU para núcleos Laplace/Helmholtz que se centra en la escalabilidad paralela.
• ScalFMM Archivado el 2 de mayo de 2017 en Wayback Machine ScalFMM es una biblioteca de software C++ desarrollada en Inria Bordeaux con gran énfasis en la genericidad y la paralelización (utilizando OpenMP / MPI ).
• DASHMM DASHMM es una biblioteca de software C++ desarrollada en la Universidad de Indiana que utiliza el sistema de ejecución multitarea asincrónica HPX-5. Proporciona una ejecución unificada en computadoras con memoria compartida y distribuida y proporciona núcleos 3D Laplace, Yukawa y Helmholtz.
• RECFMM FMM adaptativo con paralelismo dinámico en multinúcleos.