Hiyerarşik N-cisim algoritmalarının performans karşılaştırılması ve veri yapılarının incelenmesi

Abstract

Barnes-Hut ve Hızlı çok-kutup (Fast Multipole Method), N-cisim problemine etkin bir çözüm getiren metotlardır. Her iki metod da cisimleri hiyerarşik olarak gruplayan ağaç yapılan (üç boyutta sekizli ağaç gibi) kullanmakta ve cisim-cisim etkileşimi yerine cisim-grup veya grup-grup etkileşimleri kullanarak hızlı çözümler sunmaktadırlar. Fakat sekizli ağacın yüksekliği ve düğüm sayısı cisimlerin dağılımlarına bağlıdır. Cisimlerin dağılımları düzenli olduğunda O(logN) yüksekliğinde ve 0(N) düğüm sayısına sahip ağaç elde edilir fakat düzensiz dağılımlar için ağacm yüksekliği ve düğüm sayısı için bir üst limit vermek mümkün değildir. Her iki algoritmanın çalışma zamanı da ağacın yüksekliğinin ve düğüm sayısının bir fonksiyonu olduğundan algoritmaların çalışma süresi cisimlerin dağılımına bağlıdır. Bu algoritmaları dağılımdan bağımsız hale getirmek için sıkıştırılmış sekizli ağaç (compressed octree) veri yapısı önerilmiştir. Sıkıştırılmış sekizli ağacın yüksekliği ve düğüm sayısı hem düzenli dağılım hem de düzensiz dağılımlar için 0(N)'dir. Sıkıştırılmış ağaç yapısının kullanımının düzensiz dağılımlar için performans artışı sağladığı teorik olarak gösterilmiştir. Bu çalışmada sekizli ağaç yapısı ve sıkıştırılmış sekizli ağaç yapılan kullanılarak Barnes-Hut ve Hızlı çok-kutup algoritmalan gerçeklenmiştir. Her iki veri yapısı kullanılarak algoritmalann performanslan, çalışma zamanları, doğruluk oranlan gibi konularda karşılaştınlmalar yapılmış ve teorik sonuçlann pratik etkileri gözlemlenmiştir. Karşılaştırmalann doğru sonuçlan vermesi açısından her iki algoritma da aynı ana çatı altında gerçeklenmiştir. Bu ana çatı cisimler ile ilgili bilgileri ve ağaç yapılannı içermektedir. Algoritmalann genel işleyişindeki benzerlikler böyle bir ana çatı oluşturmayı kolaylaştırmaktadır. Algoritmalann gerçeklenmesinde yerçekimsel kuvvetler kullanılmıştır. Fakat hazırlanan yazılım başka kuvvet çeşitleri içinde genellenebilecek bir yapıdadır.Barnes-Hut and Fast Multipole Method use hierarchical clustering of the bodies and effectively solve the N-body problem. Both algorithms use hierarchical tree structures (such as octree for 3D) for clustering and provide fast solutions by employing particle-cluster or cluster-cluster interactions instead of particle-particle interactions. The height and the number of nodes of the tree structure used depend on the distribution of bodies. Using octree data structure for uniform distribution the height of the tree and the number of nodes are bounded by O(logN) and 0(N) respectively but for a non-uniform distribution it's hard to give such bounds. So, the running times of algorithms not only depend upon the number of bodies in the problem but also depend upon the distribution. To rectify this problem, the utilization of compressed hyperoctrees is proposed. For a compressed hyperoctree, the height of the tree and the number of nodes are bounded by 0(N) for all distributions. Especially for non-uniform distributions, it has been theoretically proved that compressed hyperoctrees provide better performance. In this thesis, we implement the Barnes-Hut and Fast Multipole Method algorithms using both octree and compressed octree data structures. We evaluate the performance of both algorithms with respect to the running time and accuracy. We examine the practical effects of the theoretical results. For an accurate comparison we implement both algorithms with a general framework. In this framework, we store the data about the particles and tree data structure. Similarities between the operations performed by each algorithm make it easier to implement such a framework. We use the gravitational problem while implementing the algorithms but the adaptation of our implementations for various force calculations can be obtained easily.