Snabb multipolmetod

Den snabba multipolmetoden ( FMM ) är en numerisk teknik som utvecklades för att påskynda beräkningen av långdistanskrafter i n -kroppsproblemet . Den gör detta genom att utöka systemets Greens funktion med hjälp av en multipolexpansion , som gör att man kan gruppera källor som ligger nära varandra och behandla dem som om de vore en enda källa.

FMM har också använts för att accelerera den iterativa lösaren i momentmetoden (MOM) som tillämpas på beräkningselektromagnetiska problem. FMM introducerades först på detta sätt av Leslie Greengard och Vladimir Rokhlin Jr. och är baserad på multipolexpansionen av vektorn Helmholtz-ekvationen . Genom att behandla interaktionerna mellan fjärrbaserade basfunktioner med användning av FMM, behöver motsvarande matriselement inte explicit lagras, vilket resulterar i en betydande minskning av erforderligt minne. Om FMM sedan tillämpas på ett hierarkiskt sätt, kan det förbättra komplexiteten hos matris-vektorprodukter i en iterativ lösare från ${\mathcal {O}}(N^{2})$ till ${\mathcal {O}}(N)$ i finit aritmetik, dvs givet en tolerans $\varepsilon$ , är matris-vektorprodukten garanterat inom en tolerans $\varepsilon .$ Komplexitetens beroende av toleransen $\varepsilon$ är ${\mathcal {O}}(\log(1/\ varepsilon ))$ , dvs komplexiteten för FMM är ${\mathcal {O}}(N\log(1/\varepsilon ))$ . Detta har utökat tillämpningsområdet för MOM till mycket större problem än vad som tidigare varit möjligt.

FMM, introducerad av Rokhlin Jr. och Greengard har sagts vara en av de tio bästa algoritmerna under 1900-talet. FMM-algoritmen minskar komplexiteten i matris-vektormultiplikation som involverar en viss typ av tät matris som kan uppstå ur många fysiska system.

FMM har också använts för att effektivt behandla Coulomb-interaktionen i Hartree-Fock-metoden och densitetsfunktionella teoriberäkningar i kvantkemi .

Se även

externa länkar

Gibson, Walton C. The Method of Moments in Electromagnetics . Chapman & Hall/CRC, 2008. ISBN 978-1-4200-6145-1
Sammanfattning av Greengard och Rokhlins originaltidning
En kort kurs om snabba multipolmetoder av Rick Beatson och Leslie Greengard.
JAVA-animering av den snabba multipolmetoden Trevlig animering av den snabba multipolmetoden med olika anpassningar.

Gratis mjukvara

Puma-EM En högpresterande, parallelliserad, öppen källkod Method of Moments / Multilevel Fast Multipole Method elektromagnetisk kod.
KIFMM3d Den kärnoberoende snabba multipole 3d-metoden (kifmm3d) är en ny FMM-implementation som inte kräver de explicita flerpoliga expansionerna av den underliggande kärnan, och den är baserad på kärnutvärderingar.
FastBEM Gratis snabba flerpoliga gränselementprogram för att lösa 2D/3D-potential, elasticitet, stokes flow och akustiska problem.
FastFieldSolvers upprätthåller distributionen av verktygen, kallade FastHenry och FastCap, utvecklade vid MIT för lösning av Maxwell-ekvationer och extraktion av kretsparasiter (induktans och kapacitans) med hjälp av FMM.
ExaFMM ExaFMM är en CPU/GPU-kapabel 3D FMM-kod för Laplace/Helmholtz-kärnor som fokuserar på parallell skalbarhet.
ScalFMM ScalFMM är ett C++ mjukvarubibliotek utvecklat på Inria Bordeaux med hög tonvikt på genericitet och parallellisering (med hjälp av OpenMP / MPI ).
DASHMM DASHMM är ett C++-programbibliotek som utvecklats vid Indiana University med användning av Asynchronous Multi-Tasking HPX-5 runtime-system. Det ger en enhetlig exekvering på datorer med delat och distribuerat minne och tillhandahåller 3D Laplace-, Yukawa- och Helmholtz-kärnor.
RECFMM Adaptiv FMM med dynamisk parallellitet på flerkärnor.