Algoritmul Barnes-Hut

O simulare de 100 de corpuri cu arborele Barnes - Hut reprezentat vizual de cutiile albastre.

Algoritmul Barnes - Hut , propus de Josh Barnes și Piet Hut ^[1] , este un algoritm de aproximare pentru efectuarea simulării corpului n . Este cunoscut pentru că are complexitate $O(n\log n)$ ${\ displaystyle O (n \ log n)}$ $O (n \ log n)$ , spre deosebire de metoda exhaustivă care are ordine $O(n^{2})$ ${\ displaystyle O (n ^ {2})}$ $O (n ^ {2})$ . ^[2]

Spațiul de simulare este de obicei împărțit în celule cubice printr-un octree (în spațiu tridimensional), astfel încât numai particulele din celulele vecine sunt tratate individual, în timp ce cele îndepărtate pot fi considerate ca o particulă mare situată în centrul de masă al celulei . ( sau ca o trunchiere a dezvoltării multipolare ). Acest lucru reduce dramatic numărul de interacțiuni dintre perechile de particule care urmează să fie calculate.

Unele dintre proiectele de înaltă performanță care necesită mult efort de calcul utilizează algoritmul arborelui Barnes-Hut în astrofizică de calcul ^[3], cum ar fi DEGIMA.

Algoritm

Arborele Barnes - Hut

Într-o simulare n- corp, algoritmul Barnes-Hut subdivizează recursiv $n$ ${\ displaystyle n}$ $n$ corpuri în grupuri și le stochează într-un octree (sau un quad-copac în două dimensiuni). Fiecare nod al arborelui reprezintă o regiune a spațiului tridimensional. Rădăcina reprezintă întregul spațiu, iar cei opt copii ai săi indică cei opt octanți ai volumului. Spațiul este împărțit recursiv în octanți până când fiecare subdiviziune conține cel mult un corp (o anumită regiune nu are corp în niciunul dintre octanții săi). Există două tipuri de noduri în octree: nodurile interne și frunzele. Frunzele nu au copii și fie reprezintă un singur corp, fie sunt goale. Fiecare nod intern descrie în schimb grupul de corpuri de sub el, memorând centrul de masă și masa totală a tuturor corpurilor sale copil.

Galerie de imagini

Distribuția particulelor similară cu două galaxii din apropiere.
Barnes complet - copac Hut. (Nodurile care nu conțin particule nu au fost trase)
Nodurile arborelui Barnes - Hut folosit pentru a calcula forța asupra unei particule plasate la origine.
Redați fișierul media
Simulare N-body bazată pe algoritmul Barnes - Hut.

Calculați forța care acționează asupra unui corp

Pentru a calcula forța rezultată pe un anumit corp, vizităm nodurile arborelui, începând de la rădăcină. Dacă centrul de masă al unui nod intern este suficient de departe de corp, toate particulele conținute în acea parte a copacului sunt tratate ca unul singur, a cărui locație și masă sunt centrul de masă și masa totală a nodului, respectiv. Dacă, pe de altă parte, nodul intern este suficient de aproape, procesul se repetă pe fiecare dintre copiii săi.

Dacă un nod este sau nu suficient de departe de un corp depinde de coeficient $s/d$ ${\ displaystyle s / d}$ ${\ displaystyle s / d}$ , unde este $s$ ${\ displaystyle s}$ $s$ este lățimea octantei reprezentată de nodul intern, e $d$ ${\ displaystyle d}$ $d$ este distanța dintre corp și centrul de masă al nodului. Nodul este suficient de departe dacă acest raport este mai mic decât o valoare prag $\theta$ ${\ displaystyle \ theta}$ $\ theta$ . Parametrul $\theta$ ${\ displaystyle \ theta}$ $\ theta$ determină acuratețea algoritmului; valori mai mari decât $\theta$ ${\ displaystyle \ theta}$ $\ theta$ cresc viteza simulării, dar scad acuratețea acesteia. De sine $\theta =0$ ${\ displaystyle \ theta = 0}$ $\ theta = 0$ , niciun nod intern nu este tratat ca o singură particulă și algoritmul degenerează în metoda exhaustivă a sumei directe.

Implementare

C.

Structură de copac scrisă pe C folosind structurile typedef și struct.

 typedef struct barnes {
// coordonatele nodului
dublu x , y ;
// masa nodului
masa dubla ;
// indicații către subarburi
struct barnes * NW , * NE , * SE , * SW ;
} barnes_t ;

Notă

^ J. Barnes și P. Hut, Un algoritm ierarhic de calcul al forței O ( N log N ) , în Nature , vol. 324, nr. 4, decembrie 1986, pp. 446-449, Bibcode : 1986 Nat . 324..446B , DOI : 10.1038 / 324446a0 .
^ Susanne Pfalzner și Paul Gibbon, Metode de copac cu multe corpuri în fizică , Cambridge Univ Press , 1996, pp. 2 -3, ISBN 978-0-521-49564-6 .
^ T. Hamada și colab. , Un nou algoritm paralel cu mai multe plimbări pentru codul de arbore Barnes-Hut de pe GPU - spre simulare rentabilă, de înaltă performanță a corpului N , în Comp. Sci. Res. Dev . Vol. 24, n. 1-2, 2009, pp. 21–31, DOI : 10.1007 / s00450-009-0089-1 .

Bibliografie

J. Dubinski, A Parallel Tree Code , în New Astronomy , vol. 1, nr. 2, octombrie 1996, pp. 133-147, Bibcode : 1996NewA .... 1..133D , DOI : 10.1016 / S1384-1076 (96) 00009-7 , arXiv : astro-ph / 9603097v1 .
U. Becciani și colab. , Un cod de arbore paralel pentru simulare de corp N mare: echilibrul dinamic al sarcinii și distribuția datelor pe un sistem CRAY T3D , în Computer Physics Communications , vol. 106, nr. 1-2, octombrie 1997, pp. 105-113, Bibcode : 1997CoPhC.106..105B , DOI : 10.1016 / S0010-4655 (97) 00102-1 , arXiv : physics / 9709003 .
T. Ventimiglia și K. Wayne, Algoritmul Barnes - Hut , pe arborjs.org . Adus pe 27 martie 2020 .

Elemente conexe

linkuri externe

Treecodes, J. Barnes , pe ifa.hawaii.edu .
Paralel TreeCode , pe cita.utoronto.ca .
Exemplu Graphical Barnes - Hut Simulation , pe andrew.cmu.edu (arhivat din original la 13 aprilie 2014) .
PEPC - Solverul Coulomb paralel destul de eficient , la fz-juelich.de . , un cod open source paralel care folosește un arbore Barnes - Hut cu nuclee de interacțiune modificabile pentru o multitudine de aplicații

Portalul fizicii : accesați intrările Wikipedia care se ocupă cu fizica

[1] J. Barnes și P. Hut, Un algoritm ierarhic de calcul al forței O ( N log N ) , în Nature , vol. 324, nr. 4, decembrie 1986, pp. 446-449, Bibcode : 1986 Nat . 324..446B , DOI : 10.1038 / 324446a0 .

[2] Susanne Pfalzner și Paul Gibbon, Metode de copac cu multe corpuri în fizică , Cambridge Univ Press , 1996, pp. 2 -3, ISBN 978-0-521-49564-6 .

[3] T. Hamada și colab. , Un nou algoritm paralel cu mai multe plimbări pentru codul de arbore Barnes-Hut de pe GPU - spre simulare rentabilă, de înaltă performanță a corpului N , în Comp. Sci. Res. Dev . Vol. 24, n. 1-2, 2009, pp. 21–31, DOI : 10.1007 / s00450-009-0089-1 .

[1]

[2]

[3],