Hiyerarşik N-cisim algoritmalarının performans karşılaştırılması ve veri yapılarının incelenmesi
Comparison of hierarchical N-body algorithms and evaluation of data structures
- Tez No: 150217
- Danışmanlar: Y.DOÇ.DR. ERDOĞAN SEVİLGEN
- Tez Türü: Yüksek Lisans
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Belirtilmemiş.
- Yıl: 2004
- Dil: Türkçe
- Üniversite: Gebze Yüksek Teknoloji Enstitüsü
- Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 74
Özet
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.
Özet (Çeviri)
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.
Benzer Tezler
- Extending constrainded hierarchical layout for drawing UML activity diagrams
Bütünleşik modelleme pili aktivite diyagramlarını çizebilmek için kısıtlanmış hiyerarşik yerleşim planının geliştirilmesi
HACI MEHMET YÜKSEL
Yüksek Lisans
İngilizce
2002
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent ÜniversitesiYRD. DOÇ. DR. UĞUR DOĞRUSÖZ
- Semi-analytical calculations of the secular evolution of 4-body systems
4-cisim sistemlerinin uzun vadeli deviniminin yarı analitikhesaplamaları
FULYA KIROĞLU
Yüksek Lisans
İngilizce
2019
Fizik ve Fizik MühendisliğiOrta Doğu Teknik ÜniversitesiFizik Ana Bilim Dalı
DOÇ. DR. MEHMET ATAKAN GÜRKAN
- Farklı öğretim kademesindeki öğrencilerin dörtgenlere ilişkin bilgi düzeyleri ve kavram yanılgılarının incelenmesi
Investigation of the students' knowledge levels and misconceptions about quadrilaterals in the different education levels
KEMAL ÖZKAN
- Nükleer maddenin yüksek sıcaklıklardaki transport özellikleri
Başlık çevirisi yok
ASLAN İLİK
Yüksek Lisans
Türkçe
1990
Fizik ve Fizik MühendisliğiSelçuk ÜniversitesiFizik Ana Bilim Dalı
Y.DOÇ.DR. RIZA OĞUL
- İnce hiperelastik plakların asimptotik teorisi
An asymptotic theory of thin hyperelastic plates
HÜSNÜ ATA ERBAY