Computing matrix permanents and counting perfect matchings on GPUs
Birden fazla GPU üzerinde permanent değerinin hesaplanması ve mükemmel eşlemelerin sayılması
- Tez No: 680367
- Danışmanlar: DR. ÖĞR. ÜYESİ KAMER KAYA
- 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: 2021
- Dil: İngilizce
- Üniversite: Sabancı Üniversitesi
- Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Bilimleri ve Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 75
Özet
Permanent aynı determinant gibi matrislerin karakterlerini anlamaya yarayan önemli bir sayısal değerdir ve bir çok pratik uygulaması mevcuttur. Örneğin, çizgeler ve seyrek matrisler yapısal olarak birbirine benzediğinden aynı veriyi göstermek üzere kullanılabilirler ve 1 ve 0'lardan oluşan bir simetrik matrisin permanent değeri, o matrise karşılık gelen iki parçalı çizgenin mükemmel eşleme sayısına eşittir. İki parçalı çizgenin mükemmel eşleme sayısı, o çizgenin noktaları arasındaki ilişkisi adına önemli bir bilgidir. Permanent değerini hesaplama #P-tam bir problemdir. Bu yüzden polinom zamanda çalışan bir algoritma bulunmamaktadır. Literatürdeki en hızlı algoritmanın karmaşıklığı O(2^(n-1) * n)'dır. Problem bu yapısı gereği n>40 gibi küçük denilebilecek matrislerin için bile permanentin hesaplanması oldukça yavaştır. Literatürde permanent değerini bilgisayar veya süper bilgisayar ile paralel olarak hesaplamak adına çalışmalar mevcuttur. Bu tezde hem dolu hem seyrek matrisler için birden çok çekirdeki CPU'lar ve birden çok GPU'da çalışan paralel algoritmalar tasarlanıp geliştirilmiştir. Ayrıca dolu ve seyrek matrisler için permanent değerini yakınsayan paralel algoritmalar geliştirilmiştir.
Özet (Çeviri)
Permanent -just like determinant-, is an important numeric value in order to understand matrix characteristics and multiple applications of permanent exist. For example, because graphs and sparse matrices are structurally similar to each other, they can be used to show the representation of the same data. The Permanent value of a symmetric matrix that is consisted of 1s and 0, is equal to the perfect matching number of the corresponding bipartite graph which is an important information of relationship among bipartite graph's vertices. Calculating exact value of matrix permanent is a #P-complete problem. For that reason, there is not an algorithm that works in polynomial time. The fastest algorithm that calculates an n times n matrix's permanent value has a time complexity of O(2^(n-1) * n). This nature of the problem makes the calculation of even considerable smaller matrices like n>40 very slow. In literature, there exist studies that focuses on computing the exact permanent value in parallel with a computer or a supercomputer. In this thesis, parallel algorithms are designed and implemented that can calculate the exact permanent value of dense and sparse matrices efficiently on multicore CPUs and multiple GPUs. Furthermore, algorithms are developed to approximate the permanent value of a given dense or sparse matrix in parallel.
Benzer Tezler
- Reliability and computing techniques for nano switching arrays
Nano anahtarlamalı dizinler için güvenilirlik ve hesaplama teknikleri
ONUR TUNALI
Yüksek Lisans
İngilizce
2015
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiNanobilim ve Nanomühendislik Ana Bilim Dalı
YRD. DOÇ. DR. MUSTAFA ALTUN
- Ramsar alanlarının uzaktan algılama yöntemleri ile zamansal analizi - meke maarı örneği
Temporal analysis of ramsar sites via remote sensing techniques - a case study of meke maar
NUR YAĞMUR
Yüksek Lisans
Türkçe
2018
Jeodezi ve Fotogrametriİstanbul Teknik ÜniversitesiGeomatik Mühendisliği Ana Bilim Dalı
PROF. DR. NEBİYE MUSAOĞLU
- Durum geçiş matrisi yöntemi ile yüksek gerilim hava iletim hatlarının güvenilirlik değerlendirilmesi
Reliability evaluation of high voltage overhead transmissionlines by the state transitional matrix method
ERTAN YANIKOĞLU
Doktora
Türkçe
1989
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiPROF.DR. Ö. VURAL AYGEN
- Üç fazlı sincap kafesli asenkron motorun ansys ve flux2d hazır paket programları ile performansının incelenmesi
Başlık çevirisi yok
HARUN AÇIKGÖZ
Yüksek Lisans
Türkçe
1998
Elektrik ve Elektronik Mühendisliğiİstanbul Teknik ÜniversitesiElektrik Bilim Dalı
PROF. DR. NURDAN GÜZELBEYOĞLU
- Bir matkap için kullanıcı arayüz yazılımı
A User interface for a drilling system
CÜNEYT SABIRCAN
Yüksek Lisans
Türkçe
1992
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiPROF. DR. EŞREF ADALI