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 . Para ello, expande la función de Green del sistema mediante una expansión multipolar , que permite agrupar fuentes que se encuentran muy juntas 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 los momentos (MOM) aplicado a problemas electromagnéticos computacionales . ^[2] 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, no es necesario almacenar explícitamente los elementos de la matriz correspondientes, lo que resulta en una reducción significativa de la memoria requerida. Si luego se aplica el FMM de manera jerárquica, puede mejorar la complejidad de los productos matriz-vector en un solucionador iterativo desde aritmética finita, es decir, dada una tolerancia , se garantiza que el producto matriz-vector estará dentro de una tolerancia . La dependencia de la complejidad de la tolerancia es , es decir, la complejidad de FMM es . Esto ha ampliado el área de aplicabilidad del MOM a problemas mucho mayores de los que antes eran posibles. ${\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 dice que el FMM, presentado 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 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 los 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}}$

Ingenuamente, evaluar 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 está bien aproximada 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 lejos 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 "lejos", evaluamos la suma sólo en los nodos de Chebyshev con un coste 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_{p}-x_{\alpha }}}\phi _{\alpha }}$

Dado que , ¿dónde está 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 realmente bien separados, se subdivide recursivamente el intervalo unitario de manera que sólo 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 el escalado, ya que se necesitan en la mayoría de los niveles dentro de la tolerancia dada. ${\displaystyle {\mathcal {O}}(p)}$ ${\displaystyle \log(1/\epsilon )}$

Ver 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 del Potencial Clásica". J. Física Computacional 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 la dispersión electromagnética”, IEEE Transactions on Antennas and Propagation 40, 634–641.
3. "El método rápido multipolar". 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 algoritmos principales". Noticias SIAM . Sociedad de Matemática Industrial y Aplicada . 33 (4): 2 . Consultado el 27 de febrero de 2019 .

enlaces externos

• Gibson, Walton C. El método de los momentos en electromagnético (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 impartido por Rick Beatson y Leslie Greengard.
• Animación JAVA del Método Fast Multipole Bonita animación del Método Fast Multipole con diferentes adaptaciones.

Software libre

• Puma-EM Un código electromagnético de método de momentos/método multipolar rápido multinivel, de alto rendimiento, paralelizado y de código abierto.
• KIFMM3d El método 3d multipolar rápido independiente del kernel (kifmm3d) es una nueva implementación de FMM que no requiere las expansiones multipolares explícitas del kernel subyacente y se basa en evaluaciones del kernel.
• 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 acústicos, de potencial, elasticidad, flujo de avivamiento y potencial 2D/3D.
• FastFieldSolvers mantiene la distribución de las herramientas, denominadas 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 con capacidad de CPU/GPU para kernels Laplace/Helmholtz que se centra en la escalabilidad paralela.
• ScalFMM ScalFMM es una biblioteca de software C++ desarrollada en Inria Bordeaux con alto énfasis en genericidad y paralelización (usando OpenMP / MPI ).
• DASHMM DASHMM es una biblioteca de software C++ desarrollada en la Universidad de Indiana que utiliza el sistema de ejecución asincrónico multitarea HPX-5. Proporciona una ejecución unificada en computadoras con memoria compartida y distribuida y proporciona núcleos 3D de Laplace, Yukawa y Helmholtz.
• RECFMM FMM adaptativo con paralelismo dinámico en multinúcleos.