BarnesHutalgoritmen

Barnes–Hut-algoritmen, uppkallad efter Joshua Barnes och Peter Hut, är en effektiv metod för N-kropps-simuleringar som används för att beräkna gravitationskrafterna mellan många partiklar. Den bygger på en hierarkisk uppdelning av rymden; i två dimensioner används ett quadtree och i tre dimensioner ett octree. Genom att approximera avlägsna grupper av partiklar med deras sammanlagda massa och masscentrum minskar beräkningskostnaden jämfört med en exakt O(N^2)-beräkning.

Processen består av två faser: byggande av trädet och beräkning av krafter. Under byggandet delas rymden upp tills varje blad innehåller högst en partikel. Varje nod lagrar dess totala massa, masscentrum och storlek. För varje partikel traverseras trädet enligt öppningskriteriet θ. Om s/d ≤ θ, där s är nodens storlek och d avståndet till partikeln, används nodens masscentrum som källa; annars traverseras noden vidare till dess undernoder.

Resultatet är vanligtvis en tidskomplexitet på cirka O(N log N) per tidssteg, vilket är betydligt bättre än O(N^2). Noggrannheten beror på θ: mindre θ ger noggrannare resultat men kräver fler beräkningar.

Historik och användning: Barnes–Hut-algoritmen publicerades 1986 av Barnes och Hut i Journal of Computational Physics. Den används i astrofysik för kosmologiska simuleringar samt i plasmaphysik och molekylära simuleringar med långräckviddiga krafter. Det finns parallella och högpresterande implementationer samt varianter för både 2D och 3D. En vanlig tilläggsversion inkluderar softening för att undvika singulariteter vid mycket nära partiklar.