A recursive graph bipartitioning algorithm by vertex separators with fixed vertices for permuting sparse matrices into block diagonal form with overlap
Seyrek matrislerin örtüşen blok köşegen biçime düzenlenmesi için düğüm ayıracı ve sabit düğümleri kullanan özyineli bir çizge bölümleme algoritması
- Tez No: 287385
- Danışmanlar: PROF. DR. CEVDET AYKANAT
- 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: 2011
- Dil: İngilizce
- Üniversite: İhsan Doğramacı Bilkent Üniversitesi
- Enstitü: Mühendislik ve Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Mühendisliği Bölümü
- Bilim Dalı: Belirtilmemiş.
- Sayfa Sayısı: 57
Özet
Seyrek doğrusal denklem sistemlerinin ön hazırlık kullanılarak cözümü çizge bölümleme araçları kullanılarak etkili ve verimli bir biçimde koşut hesaplamasına uygun hale getirilebilir. Bu tez çalışmasında, çarpımsal schwarz ön hazırlayıcısının koşut hesaplanmasında kullanılmak üzere bir seyrek matrisin örtüşen blok köşegen biçimine yeniden düzenlenmesi problemi incelenmektedir. Ardışık köşegen blokları örtüşen blok köşegen matrislere örtüşen blok köşegen matrisler denir. Bu yeniden düzenleme probleminin çizge kuramı kullanılarak ifade edilebilmesi için Düğüm Ayıracı ile Çizge Bölümleme (DAÇB) probleminin kısıtlı bir çeşidi olan sıralı DAÇB (sDAÇB) problemi tanıtılmaktadır. sDAÇB probleminde amaç iki ardışık düğüm bölümünün sadece bir düğüm ayıracı ile bağlanabildiği sıralı bir düğüm bölümlemesi bulmaktır.Varolan çizge bölümleme araçları sDAÇB problemini çözememektedirler. Bu nedenle, bu tez çalışmasında, düğüm ayıraçlarını ve yeni bir düğüm sabitleme düzenini kullanan özyineli bir çizge bölümleme algoritması önerilmektedir. Bu algoritma ile sabit düğümleri destekleyen bir DAÇB aracı etkili ve verimli bir şekilde kullanılabilmektedir. Ayrıca, bir sDAÇB çözümünün uygulanabilirliği için yeterli ve gerekli koşul incelenerek önerilen yaklaşım kuramsal olarak doğrulanmıştır. Çeşitli matrisler üzerinde yapılan deneylerin sonuçları önerilen yaklaşımın geçerliliğini doğrulamaktadır.
Özet (Çeviri)
Solving sparse system of linear equations using preconditioners can be efficiently parallelized using graph partitioning tools. In this thesis, we investigate the problem of permuting a sparse matrix into a block diagonal form with overlap which is to be used in the parallelization of the multiplicative schwarz preconditioner. A matrix is said to be in block diagonal form with overlap if the diagonal blocks may overlap. In order to formulate this permutation problem as a graph-theoretical problem, we introducea restricted version of the graph partitioning by vertex separator problem (GPVS), where the objective is to find a vertex partition whose parts are only connected by a vertex separator. The modified problem, we refer as ordered GPVS problem (oGPVS), is restricted such that the parts should exhibit an ordered form where the consecutive parts can only be connected by a separator.The existing graph partitioning tools are unable to solve the oGPVS problem. Thus, we present a recursive graph bipartitioning algorithm by vertex separators together with a novel vertex fixation scheme so that a GPVS tool supporting fixed vertices can effectively and efficiently be utilized. We also theoretically verified the correctness of the proposed approach devising a necessary and sufficient condition to the feasibility of a oGPVS solution. Experimental results on a wide range of matrices confirm the validity of the proposed approach.
Benzer Tezler
- Hypergraph-based data partitioning
Hiperçizge tabanlı veri bölümleme
ENVER KAYAASLAN
Doktora
İngilizce
2013
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. CEVDET AYKANAT
- Recursive bipartitioning models for performance improvement in sparse matrix computations
Seyrek matris hesaplamalarında performans iyileşmesi için özyinelemeli ikiye bölümleme modelleri
SEHER ACER
Doktora
İngilizce
2017
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. CEVDET AYKANAT
- Reducing communication overhead in sparse matrix and tensor computations
Seyrek matris ve tensör hesaplamalarında iletişim yükünün azaltılması
MUSTAFA OZAN KARSAVURAN
Doktora
İngilizce
2020
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. CEVDET AYKANAT
- Path defined directed graph vector (pgraph) method for multibody dynamics
Çoklu gövde dinamiğine yönelik yol tanımlı ve yönlü grafik vektörü metodu
MUSA NURULLAH YAZAR
Doktora
İngilizce
2018
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİstanbul Teknik ÜniversitesiKontrol ve Otomasyon Mühendisliği Ana Bilim Dalı
DR. ÖĞR. ÜYESİ SIDDIK MURAT YEŞİLOĞLU
- Data distribution and performance optimization models for parallel data mining
Koşut veri madenciliği için veri dağıtımı ve başarım optimizasyon modelleri
ERAY ÖZKURAL
Doktora
İngilizce
2013
Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrolİhsan Doğramacı Bilkent ÜniversitesiBilgisayar Mühendisliği Ana Bilim Dalı
PROF. DR. CEVDET AYKANAT