Algoritmo di Barnes-Hut

L'algoritmo di Barnes–Hut, proposto da Josh Barnes e Piet Hut^[1], è un algoritmo di approssimazione per eseguire la simulazione a n-corpi. È noto per avere complessità $O(n\log n)$ , al contrario del metodo esaustivo che ha ordine $O(n^{2})$ .^[2]

Lo spazio della simulazione è di solito diviso in celle cubiche attraverso un octree (nello spazio tridimensionale), in modo che solo le particelle dalle celle vicine vengono trattate individualmente, mentre quelle distanti possono essere considerate come una grande particella situata nel centro di massa della cella (o come un troncamento dello sviluppo in multipoli). In questo modo si riduce drammaticamente il numero di interazioni tra le coppie di particelle che si devono calcolare.

Alcuni dei progetti ad alte prestazioni che richiedono un grosso sforzo computazionale utilizzano l'algoritmo ad albero di Barnes-Hut nell'astrofisica computazionale,^[3] come DEGIMA.

Algoritmo

L'albero di Barnes–Hut

In una simulazione a n-corpi, l'algoritmo di Barnes–Hut suddivide ricorsivamente gli $n$ corpi in gruppi e li memorizza in un octree (o un quad-tree in due dimensioni). Ogni nodo dell'albero rappresenta una regione dello spazio tridimensionale. La radice rappresenta l'intero spazio, e i suoi otto figli indicano gli otto ottanti del volume. Lo spazio è diviso ricorsivamente in ottanti finché ogni suddivisione non contiene al massimo un corpo (qualche regione non possiede alcun corpo in nessuno dei suoi ottanti). Ci sono due tipi di nodi nell'octree: i nodi interni e le foglie. Le foglie non hanno figli e rappresentano un singolo corpo oppure sono vuoti. Ogni nodo interno invece descrivono il gruppo di corpi al di sotto di esso, memorizzando il centro di massa e la massa totale di tutti i suoi corpi figli.

Galleria d'immagini

Distribuzione di particelle simile a due galassie vicine.
Albero di Barnes–Hut completo. (Non sono stati disegnati i nodi che non contengono delle particelle)
Nodi dell'albero di Barnes–Hut utilizzato per calcolare la forza su una particella posta nell'origine.
Simulazione a n-corpi basata sull'algoritmo di Barnes–Hut.

Calcolare la forza agente su un corpo

Per calcolare la forza risultante su di un particolare corpo, si visitano i nodi dell'albero, partendo dalla radice. Se il centro di massa di un nodo interno è abbastanza lontano dal corpo, tutte le particelle contenute in quella parte dell'albero vengono trattate come una sola, la cui posizione e massa sono rispettivamente il centro di massa e la massa totale del nodo. Se invece il nodo interno è sufficientemente vicino, si ripete il processo su ognuno dei suoi figli.

Se un nodo è o non è abbastanza lontano da un corpo dipende dal quoziente $s/d$ , dove $s$ è la larghezza dell'ottante rappresentato dal nodo interno, e $d$ è la distanza tra il corpo e il centro di massa del nodo. Il nodo è abbastanza lontano se questo rapporto è minore di un valore soglia $\theta$ . Il parametro $\theta$ determina la precisione dell'algoritmo; valori maggiori di $\theta$ aumentano la velocità della simulazione ma diminuiscono la sua precisione. Se $\theta =0$ , nessun nodo interno viene trattato come una particella unica e l'algoritmo degenera nel metodo esaustivo di somma diretta.

Implementazione

C

Struttura albero scritta su C utilizzando i costrutti typedef e struct.

typedef struct barnes {
    //coordinate del nodo
    double x, y;
    //massa del nodo
    double massa;
    //puntatori ai sottoalberi
    struct barnes * NW, *NE, *SE, *SW;
} barnes_t;

Note

^ J. Barnes e P. Hut, A hierarchical O(N log N) force-calculation algorithm, in Nature, vol. 324, n. 4, dicembre 1986, pp. 446-449, Bibcode:1986Natur.324..446B, DOI:10.1038/324446a0.
^ Susanne Pfalzner e Paul Gibbon, Many-body tree methods in physics, Cambridge Univ. Press, 1996, pp. 2-3, ISBN 978-0-521-49564-6.
^ T. Hamada et al., A novel multiple-walk parallel algorithm for the Barnes-Hut treecode on GPUs – towards cost effective, high performance N-body simulation, in Comp. Sci. Res. Dev, vol. 24, n. 1-2, 2009, pp. 21–31, DOI:10.1007/s00450-009-0089-1.

Bibliografia

J. Dubinski, A Parallel Tree Code, in New Astronomy, vol. 1, n. 2, ottobre 1996, pp. 133-147, Bibcode:1996NewA....1..133D, DOI:10.1016/S1384-1076(96)00009-7, arXiv:astro-ph/9603097v1.
U. Becciani et al., A parallel tree code for large N-body simulation: dynamic load balance and data distribution on a CRAY T3D system, in Computer Physics Communications, vol. 106, n. 1-2, ottobre 1997, pp. 105-113, Bibcode:1997CoPhC.106..105B, DOI:10.1016/S0010-4655(97)00102-1, arXiv:physics/9709003.
T. Ventimiglia e K. Wayne, The Barnes–Hut Algorithm, su arborjs.org. URL consultato il 27 marzo 2020.

Voci correlate

Collegamenti esterni

Treecodes, J. Barnes, su ifa.hawaii.edu.
Parallel TreeCode, su cita.utoronto.ca. URL consultato il 22 maggio 2018 (archiviato dall'url originale il 2 aprile 2013).
Example Graphical Barnes–Hut Simulation, su andrew.cmu.edu. URL consultato il 23 luglio 2020 (archiviato dall'url originale il 13 aprile 2014).
PEPC – The Pretty Efficient Parallel Coulomb solver, su fz-juelich.de., un codice open-source in parallelo che utilizza un albero di Barnes–Hut con nuclei d'interazioni modificabili per una moltitudine di applicazioni

Portale Fisica: accedi alle voci di Wikipedia che trattano di fisica

[1] J. Barnes e P. Hut, A hierarchical O(N log N) force-calculation algorithm, in Nature, vol. 324, n. 4, dicembre 1986, pp. 446-449, Bibcode:1986Natur.324..446B, DOI:10.1038/324446a0.

[2] Susanne Pfalzner e Paul Gibbon, Many-body tree methods in physics, Cambridge Univ. Press, 1996, pp. 2-3, ISBN 978-0-521-49564-6.

[3] T. Hamada et al., A novel multiple-walk parallel algorithm for the Barnes-Hut treecode on GPUs – towards cost effective, high performance N-body simulation, in Comp. Sci. Res. Dev, vol. 24, n. 1-2, 2009, pp. 21–31, DOI:10.1007/s00450-009-0089-1.

[1]

[2]

[3]