Barnes-Hut simülasyonu - Barnes–Hut simulation

Barnes – Hut ağacı ile görsel olarak mavi kutular olarak 100 gövdeli bir simülasyon.

Barnes-Hut simülasyonu (Josh Barnes adını almıştır ve Piet Hut ) bir yaklaşım algoritması gerçekleştirmek için n- vücut simülasyonu. Sahip olduğu için dikkate değer sipariş Ö(n günlükn) doğrudan toplamlı bir algoritmaya kıyasla O (n2).[1]

Simülasyon hacmi genellikle bir sekiz (üç boyutlu bir uzayda), böylece yalnızca parçacıklar yakındaki hücrelerin ayrı ayrı muamele edilmesi gerekir ve uzak hücrelerdeki parçacıklar, hücrenin merkezinde bulunan tek bir büyük parçacık olarak işlenebilir. kütle merkezi (veya düşük mertebe olarak çok kutuplu genişletme ). Bu, hesaplanması gereken parçacık çifti etkileşimlerinin sayısını önemli ölçüde azaltabilir.

En talepkarlardan bazıları yüksek performanslı bilgi işlem projeler yapar hesaplamalı astrofizik Barnes – Hut ağaç kodu algoritmasını kullanarak, örneğin DEGIMA.[2][kaynak belirtilmeli ]

Algoritma

Barnes-Hut ağacı

Üç boyutlu olarak n- vücut simülasyonu Barnes – Hut algoritması tekrarlı böler n gövdeleri gruplara ayırarak sekiz (veya a dört ağaç 2D simülasyonda). Her biri düğüm bu ağaçta üç boyutlu uzayın bir bölgesini temsil eder. En üstteki düğüm tüm alanı temsil eder ve sekiz çocuğu, sekiz oktanlar alanın. Her bir alt bölüm 0 veya 1 gövde içerene kadar boşluk yinelemeli olarak oktanlara bölünür (bazı bölgeler tüm oktanlarında gövdelere sahip değildir). Oktree'de iki tür düğüm vardır: dahili ve harici düğümler. Harici bir düğümün alt öğesi yoktur ve ya boştur ya da tek bir gövdeyi temsil eder. Her dahili düğüm, altındaki gövde grubunu temsil eder ve kütle merkezi ve tüm çocuk bedenlerinin toplam kütlesi.

  • İki komşu galaksiyi andıran parçacık dağılımı.

  • Barnes-Hut ağacını tamamlayın. (Parçacık içermeyen düğümler çizilmez)

  • Barnes-Hut ağacının düğümleri, başlangıç ​​noktasında bir parçacığa etki eden kuvveti hesaplamak için kullanılır.

  • n-Barnes – Hut algoritmasına dayalı vücut simülasyonu.

Bir vücuda etki eden kuvveti hesaplamak

Hesaplamak için net kuvvet belirli bir gövdede, ağacın düğümleri kökten başlayarak geçilir. Bir iç düğümün kütle merkezi gövdeden yeterince uzaksa, ağacın o bölümünde bulunan gövdeler, konumu ve kütlesi sırasıyla iç düğümün kütle merkezi ve toplam kütlesi olan tek bir parçacık olarak kabul edilir. İç düğüm vücuda yeterince yakınsa, süreç her bir çocuğu için tekrarlanır.

Bir düğümün bir gövdeden yeterince uzakta olup olmadığı, bölüme bağlıdır , nerede s dahili düğüm tarafından temsil edilen bölgenin genişliğidir ve d vücut ile düğümün kütle merkezi arasındaki mesafedir. Bu oran bir eşik değerinden daha küçük olduğunda düğüm yeterince uzakta θ. Parametre θ simülasyonun doğruluğunu belirler; daha büyük değerler θ simülasyonun hızını arttırır ancak doğruluğunu azaltır. Eğer θ = 0, hiçbir dahili düğüm tek bir gövde olarak değerlendirilmez ve algoritma, doğrudan toplamlı bir algoritmaya dönüşür.

Ayrıca bakınız

Referanslar ve kaynaklar

Referanslar
  1. ^ Pfalzner, Susanne; Gibbon, Paul (1996). Fizikte çok gövdeli ağaç yöntemleri. Cambridge [u.a.]: Cambridge Üniv. Basın. pp.2, 3. ISBN  978-0-521-49564-6.
  2. ^ T. Hamada; et al. (2009). "GPU'larda Barnes-Hut ağaç kodu için - uygun maliyetli, yüksek performanslı N-gövde simülasyonuna doğru yeni bir çok adımda paralel algoritma". Comp. Sci. Res. Dev. 24 (1–2): 21–31. doi:10.1007 / s00450-009-0089-1. S2CID  31071570.
Kaynaklar

Dış bağlantılar