title: Algoritmo di Barnes-Hut
text: # Algoritmo di Barnes-Hut
  
  L'algoritmo di Barnes–Hut, proposto da Josh Barnes e Piet Hut, è 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})$.
  
  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, 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.
  
  