N-Cisim ve Parçacık-Ağ Yöntemleri
Birçok parçacık arasındaki karşılıklı kütleçekimsel veya elektrostatik kuvvetlerin basitçe hesaplanması, parçacık sayısının karesi kadar maliyetlidir. Hızlı N-cisim ve parçacık-ağ yöntemleri bu maliyeti neredeyse doğrusal seviyeye indirgeyerek galaksilerin ve plazmaların milyonlarca parçacıklı simülasyonlarını mümkün kılmaktadır.
Tanım
N-cisim ve parçacık-ağ yöntemleri, birçok etkileşen parçacık arasındaki uzun menzilli kuvvetleri, uzak parçacıkları gruplandırarak veya alanı bir ızgara üzerinde çözerek karesel zamandan daha kısa sürede yaklaşık olarak hesaplayan algoritmalardır.
Kapsam
Bu konu, uzun menzilli parçacık etkileşimleri için ölçeklenebilir algoritmaları kapsamaktadır: Barnes-Hut gibi hiyerarşik ağaç kodları, hızlı çok kutuplu yöntem (fast multipole method) ve ızgara tabanlı parçacık-ağ ile parçacık-parçacık parçacık-ağ şemaları. Ayrıca, doğruluk-maliyet dengelerini ve bu yöntemlerin büyük kütleçekimsel ve elektrostatik simülasyonlardaki rolünü ele almaktadır.
Temel sorular
- İkili uzun menzilli kuvvetlerin doğrudan toplanması neden aşırı derecede maliyetlidir?
- Ağaç kodları, kuvvet hesaplama maliyetini azaltmak için uzak parçacıkları nasıl gruplandırmaktadır?
- Hızlı çok kutuplu yöntem (fast multipole method), kontrollü hata ile neredeyse doğrusal ölçeklendirmeyi nasıl sağlamaktadır?
- Parçacık-ağ yöntemleri, uzun menzilli kuvvetleri ele almak için alanı bir ızgara üzerinde nasıl çözmektedir?
Temel kuramlar
- Hiyerarşik ağaç kodları
- Barnes-Hut algoritması, uzak parçacıkları, kolektif kuvvetleri kütle merkezleri tarafından yaklaşık olarak hesaplanan hücreler halinde gruplandırmaktadır. Bu sayede kuvvet değerlendirme maliyeti kareselden N log N mertebesine düşürülmektedir.
- Hızlı çok kutuplu yöntem (Fast multipole method)
- Hızlı çok kutuplu yöntem (fast multipole method), parçacık gruplarını kesilmiş çok kutuplu açılımlarla temsil etmekte ve bunları hiyerarşik olarak çevirmektedir. Bu sayede titizlikle kontrol edilebilir bir doğrulukla neredeyse doğrusal ölçeklendirme sağlanmaktadır.
- Parçacık-ağ yöntemleri
- Parçacık-ağ ve parçacık-parçacık parçacık-ağ şemaları, yükleri veya kütleleri bir ızgara üzerine enterpolasyonla yerleştirmekte, alanı hızlı Fourier dönüşümleriyle çözmekte ve kısa menzilli düzeltmeler eklemektedir. Bu sayede uzun menzilli etkileşimler verimli bir şekilde ele alınmaktadır.
Klinik önem
Bu yöntemler, yapı oluşumunun kozmolojik ve galaktik N-cisim simülasyonlarına, plazma simülasyonlarına ve büyük moleküler sistemlerin uzun menzilli elektrostatiklerine yön vermektedir. Ayrıca, hızlı çok kutuplu yöntem (fast multipole method) yirminci yüzyılın en önemli algoritmalarından biri olarak kabul edilmektedir.
Tarihçe
Parçacık-ağ yöntemleri 1980'lerde Hockney ve Eastwood tarafından sistemleştirilmiştir. 1986 Barnes-Hut ağaç kodu ve Greengard ile Rokhlin'in 1987 hızlı çok kutuplu yöntemi (fast multipole method), N-cisim simülasyonunu dönüştürerek, bunu takiben büyük kozmolojik ve moleküler simülasyonları mümkün kılmıştır.
Öne çıkan isimler
- Josh Barnes
- Piet Hut
- Leslie Greengard
- Vladimir Rokhlin
İlgili konular
Temel eserler
- barneshut1986
- greengard1987
Sıkça sorulan sorular
- Neden her ikili kuvvet doğrudan hesaplanmamaktadır?
- Doğrudan toplama maliyetleri, parçacık sayısının karesi olarak artmaktadır; bu nedenle parçacık sayısını iki katına çıkarmak iş yükünü dört katına çıkarmaktadır. Bu durum, kozmolojik ve büyük moleküler simülasyonlardaki milyonlarca veya milyarlarca parçacık için imkansız hale gelmektedir. Hızlı yöntemler bu maliyeti neredeyse doğrusal bir seviyeye indirgemektedir.
- Ağaç ve çok kutuplu yöntemler hatalarını nasıl kontrol etmektedir?
- Uzak parçacık gruplarının etkisini yaklaşık olarak hesaplamaktadırlar ve bu yaklaşım, daha fazla çok kutuplu terim eklenerek veya daha katı bir açılma kriteri kullanılarak iyileştirilmektedir. Bu sayede doğruluk, hız ile kontrollü bir şekilde takas edilebilmektedir.