Algoritmo di Barnes-Hut
[[File:2D Quad-Tree partitioning of 100 bodies.png|thumb|upright=1.4|border|Una simulazione a 100-corpi con l'albero di Barnes–Hut rappresentato visualmente dai riquadri blu.]]

L{{'}}'''algoritmo di Barnes–Hut''', proposto da Josh Barnes e Piet Hut<ref>{{Cita pubblicazione |autore1=J. Barnes  |autore2=P. Hut|titolo=A hierarchical O(''N''&nbsp;log&nbsp;''N'') force-calculation algorithm |rivista=Nature |volume=324 |numero=4 |mese=dicembre|anno=1986 |pp=446-449 |doi=10.1038/324446a0|bibcode = 1986Natur.324..446B }}</ref>, è un [[algoritmo di approssimazione]] per eseguire la simulazione a [[Problema degli n-corpi|''n''-corpi]]. È noto per avere [[Teoria della complessità|complessità]] <math>O(n\log n)</math>, al contrario del metodo esaustivo che ha ordine <math>O(n^2)</math>.<ref>{{Cita libro|cognome1=Pfalzner|nome1=Susanne|cognome2=Gibbon|nome2=Paul|titolo=Many-body tree methods in physics|url=https://archive.org/details/manybodytreemeth00pfal_902|anno=1996|editore=[[Cambridge University Press|Cambridge Univ. Press]]|isbn=978-0-521-49564-6|pp=[https://archive.org/details/manybodytreemeth00pfal_902/page/n9 2]-3}}</ref>

Lo spazio della simulazione è di solito diviso in celle cubiche attraverso un ''octree'' (nello spazio tridimensionale), in modo che solo le [[punto materiale|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,<ref>{{Cita pubblicazione|autore=T. Hamada|etal=si|titolo=A novel multiple-walk parallel algorithm for the Barnes-Hut treecode on GPUs – towards cost effective, high performance N-body simulation|rivista=Comp. Sci. Res. Dev|anno=2009|volume=24|numero=1-2|pp=21–31|doi=10.1007/s00450-009-0089-1}}</ref>
come DEGIMA.

== Algoritmo ==
=== L'albero di Barnes–Hut ===
In una simulazione a ''n''-corpi, l'algoritmo di Barnes–Hut suddivide [[algoritmo ricorsivo|ricorsivamente]] gli <math>n</math> corpi in gruppi e li memorizza in un octree (o un [[albero quadramentale|quad-tree]] in due dimensioni). Ogni nodo dell'[[albero (informatica)|albero]] rappresenta una regione dello spazio tridimensionale.
La radice rappresenta l'intero spazio, e i suoi otto figli indicano gli otto [[Ottante (geometria)|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==
<gallery>
File:Barnes_hut_partikel.png|Distribuzione di particelle simile a due galassie vicine.
File:Barnes_hut_tree.png|Albero di Barnes–Hut completo. (Non sono stati disegnati i nodi che non contengono delle particelle)
File:Barnes_hut_used_nodes.png|Nodi dell'albero di Barnes–Hut utilizzato per calcolare la forza su una particella posta nell'origine.
File:Galaxy collision.ogv |Simulazione a ''n''-corpi basata sull'algoritmo di Barnes–Hut.
</gallery>

=== 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 <math>s/d</math>, dove <math>s</math> è la larghezza dell'ottante rappresentato dal nodo interno, e <math>d</math> è la distanza tra il corpo e il centro di massa del nodo. Il nodo è abbastanza lontano se questo rapporto è minore di un valore soglia <math>\theta</math>. Il parametro <math>\theta</math> determina la precisione dell'algoritmo; valori maggiori di <math>\theta</math> aumentano la velocità della simulazione ma diminuiscono la sua precisione. Se <math>\theta=0</math>, 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.<syntaxhighlight lang="c" line="1" start="1">
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;
</syntaxhighlight>

==Note==
<references/>

==Bibliografia==
*{{Cita pubblicazione |rivista=New Astronomy |volume=1 |numero=2 |anno=1996 |mese=ottobre|pp=133-147 |titolo=A Parallel Tree Code |autore= J. Dubinski |arxiv=astro-ph/9603097v1 |doi=10.1016/S1384-1076(96)00009-7|bibcode = 1996NewA....1..133D }}
*{{Cita pubblicazione|doi=10.1016/S0010-4655(97)00102-1 |titolo=A parallel tree code for large ''N''-body simulation: dynamic load balance and data distribution on a CRAY T3D system |url=https://archive.org/details/sim_computer-physics-communications_1997-10_106_1-2/page/105 |autore1=U. Becciani|etal=si|rivista=Computer Physics Communications |volume=106 |numero=1-2 |mese=ottobre|anno= 1997 |pp=105-113|arxiv = physics/9709003 |bibcode = 1997CoPhC.106..105B }}
*{{Cita web |url=http://arborjs.org/docs/barnes-hut |titolo=The Barnes–Hut Algorithm |autore1=T. Ventimiglia |autore2=K. Wayne |accesso=27 marzo 2020}}

== Voci correlate ==
* [[Problema degli n-corpi]]
* [[Albero quadramentale|Quad-tree]]
* [[Fisica computazionale]]
* [[Metodo delle celle]]

==Collegamenti esterni==
* {{cita web|http://ifa.hawaii.edu/~barnes/software.html|Treecodes, J. Barnes}}
* {{cita web | 1 = http://www.cita.utoronto.ca/~dubinski/treecode/treecode.html | 2 = Parallel TreeCode | accesso = 22 maggio 2018 | dataarchivio = 2 aprile 2013 | urlarchivio = https://web.archive.org/web/20130402125257/http://www.cita.utoronto.ca/~dubinski/treecode/treecode.html | urlmorto = sì }}
* {{cita web | 1 = http://www.andrew.cmu.edu/user/sameera/demos/BNtree/HTML5/JavaScript | 2 = Example Graphical Barnes–Hut Simulation | accesso = 23 luglio 2020 | dataarchivio = 13 aprile 2014 | urlarchivio = https://web.archive.org/web/20140413142523/http://www.andrew.cmu.edu/user/sameera/demos/BNtree/HTML5/JavaScript | urlmorto = sì }}
* {{cita web|http://www.fz-juelich.de/ias/jsc/pepc|PEPC – The Pretty Efficient Parallel Coulomb solver}}, 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}}

[[Categoria:Gravitazione]]
[[Categoria:Fisica computazionale]]