El método rápido multipolar ( 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, amplía la función de Green del sistema mediante una expansión multipolar , que permite agrupar fuentes que se encuentran 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 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, los elementos de matriz correspondientes no necesitan ser almacenados 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 de matriz-vector en un solucionador iterativo de a en 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 de FMM es . Esto ha ampliado el área de aplicabilidad del MOM a problemas mucho mayores de lo que era posible anteriormente.
Se dice 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 eficazmente 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 .
Ver también
Referencias
- ^ 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.
- ^ Nader Engheta , William D. Murphy, Vladimir Rokhlin y Marius Vassiliou (1992), "El método rápido multipolar para el cálculo de dispersión electromagnética", Transacciones IEEE sobre antenas y propagación 40, 634-641.
- ^ "Copia archivada" . Archivado desde el original el 3 de junio de 2011 . Consultado el 10 de diciembre de 2010 .CS1 maint: copia archivada como título ( enlace )
- ^ 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áticas Industriales y Aplicadas . 33 (4): 2 . Consultado el 27 de febrero de 2019 .
enlaces externos
- Gibson, Walton C. El método de los momentos en electromagnetismo . Chapman y Hall / CRC, 2008. ISBN 978-1-4200-6145-1
- FEKO de Altair HyperWorks incluye el FMM multinivel como opción de solución.
- Serenity Un código de sección transversal de radar (RCS) de alta fidelidad que utiliza el método del momento y el FMM.
- Resumen del artículo original de Greengard y Rokhlin
- Un curso corto sobre métodos rápidos multipolares 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 alto rendimiento, paralelo, de código abierto, Método de Momentos / Método multinivel rápido y multipolo.
- KIFMM3d El método 3d multipolo 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.
- FastBEM Programas de elementos delimitadores multipolares rápidos y gratuitos para resolver problemas de potencial 2D / 3D, elasticidad, flujo de carga y problemas acústicos.
- 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 del circuito (inductancia y capacitancia) utilizando el FMM.
- ExaFMM ExaFMM es un código FMM 3D compatible con CPU / GPU para núcleos de Laplace / Helmholtz que se centra en la escalabilidad paralela.
- ScalFMM ScalFMM es una biblioteca de software C ++ desarrollada en Inria Bordeaux con un gran énfasis en la genéricaidad y la paralelización (usando OpenMP / MPI ).
- DASHMM DASHMM es una biblioteca de software C ++ desarrollada en la Universidad de Indiana que utiliza el sistema de tiempo de ejecución HPX-5 multitarea asíncrona. Proporciona una ejecución unificada en computadoras con memoria compartida y distribuida y proporciona kernels 3D Laplace, Yukawa y Helmholtz.
- RECFMM Adaptive FMM con paralelismo dinámico en multinúcleos.