Snabb multipolmetod

Fast Multipole Method (FMM) är en numerisk metod utformad för att påskynda beräkningen av långdistanskrafter i n-kroppens gravitationsproblem . Detta uppnås genom att utöka Greens funktion i systemet med en flerpolig förlängning, vilket gör att kraftkällor som ligger nära varandra kan grupperas och behandlas som om de vore en enda kraftkälla. [ett]

BMM används också för att påskynda den iterativa lösningen i boundary element-metoden i relation till beräkningsproblem med elektromagnetism. [2] BMM introducerades först av Leslie Greengard och Vladimir Rokhlin [3] och baserades på multipolexpansionen av vektorn Helmholtz-ekvationen. Genom att hantera interaktionerna mellan fjärrbasfunktioner med hjälp av BMM, behöver inte motsvarande matriselement lagras, vilket resulterar i en betydande minskning av det erforderliga minnet. Om BMM tillämpas hierarkiskt kan detta förbättra komplexiteten hos algoritmen i den iterativa metoden från till , det vill säga för ett givet fel är matris-vektorprodukten garanterat inom felet . Detta utökar omfattningen av BMM till fler uppgifter. ${\mathcal {O}}(N^{2})$ ${\mathcal {O}}(N)$ $\varepsilon$ $\varepsilon.$ $\varepsilon$ ${\mathcal {O}}(\log(1/\varepsilon ))$ ${\mathcal {O}}(\log(1/\varepsilon )N)$

BMM anses vara en av de tio bästa algoritmerna på 1900-talet. [4] Denna metod reducerar komplexiteten av matris-vektor multiplikation med hjälp av en viss typ av tät matris som förekommer i många fysiska system.

Se även

Gravitationsproblem med N-kroppar

octree

Länkar

Fast Multifield Method, N.A. Gumerov,

Anteckningar

↑ V Rokhlin. Snabb lösning av integralekvationer för klassisk potentialteori (engelska) // Journal of Computational Physics. - 1985-09-15. — Vol. 60 , iss. 2 . — S. 187–207 . — ISSN 0021-9991 . - doi : 10.1016/0021-9991(85)90002-6 . Arkiverad från originalet den 4 april 2019.
↑ Eric Darve. Den snabba multipolmetoden: Numerisk implementering // Journal of Computational Physics. - 1999. - Nr 160 . - S. 195-240 . Arkiverad från originalet den 6 november 2020.
↑ Den snabba multipolmetoden . web.archive.org (3 juni 2011). Hämtad: 8 mars 2020. (obestämd)
↑ SIAM: Det bästa av 1900-talet: Redaktörernas namn på de 10 bästa algoritmerna . archive.siam.org. Hämtad 8 mars 2020. Arkiverad från originalet 20 september 2018. (obestämd)