Nopea moninapamenetelmä

Fast Multipole Method (FMM) on numeerinen menetelmä , joka on suunniteltu nopeuttamaan pitkän kantaman voimien laskemista n-kehon painovoimaongelmassa . Tämä saavutetaan laajentamalla Greenin toimintoa järjestelmässä moninapaisella jatkeella, jonka avulla lähellä toisiaan olevat voimalähteet voidaan ryhmitellä yhteen ja käsitellä ikään kuin ne olisivat yksi voimalähde. [yksi]

BMM:ää käytetään myös nopeuttamaan iteratiivista ratkaisua rajaelementtimenetelmässä sähkömagnetismin laskennallisiin ongelmiin. [2] BMM:n esittelivät ensimmäisenä Leslie Greengard ja Vladimir Rokhlin [3] , ja se perustui vektorin Helmholtzin yhtälön moninapalaajennukseen. Käsittelemällä etäkantatoimintojen välisiä vuorovaikutuksia BMM:n avulla vastaavia matriisielementtejä ei tarvitse tallentaa, mikä johtaa tarvittavan muistin merkittävään vähenemiseen. Jos BMM:ää sovelletaan hierarkkisesti, tämä voi parantaa iteratiivisen lähestymistavan algoritmin monimutkaisuutta välillä - , eli tietylle virheelle matriisivektoritulo on taatusti virheen sisällä . Tämä laajentaa BMM:n soveltamisalaa useampiin tehtäviin. ${\mathcal {O}}(N^{2})$ ${\mathcal {O}}(N)$ $\varepsilon$ $\varepsilon.$ $\varepsilon$ ${\mathcal {O}}(\log(1/\varepsilon ))$ ${\mathcal {O}}(\log(1/\varepsilon )N)$

BMM:ää pidetään yhtenä 1900-luvun kymmenestä parhaasta algoritmista. [4] Tämä menetelmä vähentää matriisi-vektorikertomisen monimutkaisuutta käyttämällä tietyntyyppistä tiheää matriisia, jota esiintyy monissa fysikaalisissa järjestelmissä.

Katso myös

Gravitaatio N-kappaleen ongelma

oktreen

Linkit

Fast Multifield Method, N.A. Gumerov,

Muistiinpanot

↑ V Rokhlin. Klassisen potentiaaliteorian integraaliyhtälöiden nopea ratkaisu (englanniksi) // Journal of Computational Physics. - 15.9.1985. — Voi. 60 , iss. 2 . — s. 187–207 . — ISSN 0021-9991 . - doi : 10.1016/0021-9991(85)90002-6 . Arkistoitu alkuperäisestä 4. huhtikuuta 2019.
↑ Eric Darve. Nopea moninapamenetelmä: numeerinen toteutus // Journal of Computational Physics. - 1999. - Nro 160 . - S. 195-240 . Arkistoitu alkuperäisestä 6. marraskuuta 2020.
↑ Nopea moninapamenetelmä . web.archive.org (3. kesäkuuta 2011). Haettu: 8.3.2020. (määrätön)
↑ SIAM: 1900-luvun parhaat: Toimittajat nimeävät 10 parasta algoritmia . archive.siam.org. Haettu 8. maaliskuuta 2020. Arkistoitu alkuperäisestä 20. syyskuuta 2018. (määrätön)