Geri Dön

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

  1. Tez No: 150217
  2. Yazar: ALPASLAN BURAK İNNER
  3. Danışmanlar: Y.DOÇ.DR. ERDOĞAN SEVİLGEN
  4. Tez Türü: Yüksek Lisans
  5. Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
  6. Anahtar Kelimeler: Belirtilmemiş.
  7. Yıl: 2004
  8. Dil: Türkçe
  9. Üniversite: Gebze Yüksek Teknoloji Enstitüsü
  10. Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
  11. Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
  12. Bilim Dalı: Belirtilmemiş.
  13. 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

  1. 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

  2. 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

    İngilizce

    2019

    Fizik ve Fizik MühendisliğiOrta Doğu Teknik Üniversitesi

    Fizik Ana Bilim Dalı

    DOÇ. DR. MEHMET ATAKAN GÜRKAN

  3. 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

    Yüksek Lisans

    Türkçe

    Türkçe

    2019

    MatematikUşak Üniversitesi

    İlköğretim Ana Bilim Dalı

    PROF. DR. OSMAN BİRGİN

  4. Nükleer maddenin yüksek sıcaklıklardaki transport özellikleri

    Başlık çevirisi yok

    ASLAN İLİK

    Yüksek Lisans

    Türkçe

    Türkçe

    1990

    Fizik ve Fizik MühendisliğiSelçuk Üniversitesi

    Fizik Ana Bilim Dalı

    Y.DOÇ.DR. RIZA OĞUL

  5. İnce hiperelastik plakların asimptotik teorisi

    An asymptotic theory of thin hyperelastic plates

    HÜSNÜ ATA ERBAY

    Doktora

    Türkçe

    Türkçe

    1988

    Matematikİstanbul Teknik Üniversitesi

    PROF.DR. ERDOĞAN ŞUHUBİ