Tez No	İndirme	Tez Künye	Durumu
83716	Bu tezin, veri tabanı üzerinden yayınlanma izni bulunmamaktadır. Yayınlanma izni olmayan tezlerin basılı kopyalarına Üniversite kütüphaneniz aracılığıyla (TÜBESS üzerinden) erişebilirsiniz.	Hypergraph models for sparse matrix partitioning and reordering / Seyrek matris bölümleme ve yeniden-düzenleme için hiperçizge modelleri Yazar:ÜMİT VEYSEL ÇATALYÜREK Danışman: DOÇ. DR. CEVDET AYKANAT Yer Bilgisi: İhsan Doğramacı Bilkent Üniversitesi / Mühendislik ve Fen Bilimleri Enstitüsü / Bilgisayar Yazılımı Ana Bilim Dalı Konu:Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control Dizin:Grafikler = Graphics ; Matrisler = Matrices ; Yük dengeleme = Load balancing	Onaylandı Doktora İngilizce 1999 133 s.
ÖZET SEYREK MATRİS BÖLÜMLEME VE YENİDEN-DÜZENLEME İÇİN HİPERÇİZGE MODELLERİ Ümit V. Çatalyürek Bilgisayar ve Enformatik Mühendisliği, Doktora Tez Yöneticisi: Doç. Dr. Cevdet Aykanat Kasım, 1999 Çizgeler, koşut seyrek-matris vektör çarpımında (SpMxV) seyrek matrislerin ayrıştırılması ve az doluluk faktorizasyonu için kullanılan seyrek matrislerin yeniden düzenlenmesini içeren çeşitli bilimsel uygulamalarda seyrek matris lerin gösterimi için yaygın olarak kullanılmaktadır. Ancak seyrek matris lerin standart çizge-bölümlemeye dayalı tek-boyutlu ayrıştırılması koşut Sp MxV işlemi için gerekli iletişim hacmini yansıtamamaktadır. Çizge modelinin tek-boyutlu ayrıştırmadaki bu önemli eksikliğine karşılık benzer bir eksiği ol mayan iki bilişimsel hiperçizge modeli sunuyoruz. Önerdiğimiz modeller tek- boyutlu ayrıştırma problemim iyi bilinen hiperçizge bölümleme problemine in dirgemektedir. Literatürde koşut SpMxV hesaplamaları için iletişim gereksin imini doğrudan azaltan iki-boyutlu ayrıştırma yöntemi yoktur. İletişim hacmi gereksinimini azaltmak için seyrek matrislerin iki-boyutlu ayrıştırmasını sağlayan üç yeni hiperçizge modeli tanıtıyoruz. Bunlardan ilki koşut SpMxV işlemindeki seyrek matrislerin fine-grain iki-boyutlu ayrıştırması için önerildi. İki-boyutlu ayrıştırmada kullanılan ikinci hiperçizge modeli seyrek matrislerin çentikli-benzeri ayrıştırmalarının üretilmesi için önerildi. Literatürde dama tahtası tabanlı ayrıştırmaya dayanan koşut matris vektör çarpımı algoritmaları yaygınca bu lunmaktadır. Bununla birlikte bu çalışmalarda sadece yük dengeleme prob lemine işaret edilmiştir. Biz bu çalışmada iki-boyutlu ayrıştırmanın üçüncü modeli olarak dama tahtası tabanlı ayrıştırmada işlemciler arası yük dengesini korurken iletişim hacmini de azaltmayı hedefleyen yeni bir hiperçizge mod eli öneriyoruz. Önerdiğimiz model ayrıştırma problemini çoklu-kısıt hiperçizge bölümleme problemine indirgemektedir. Çoklu-kısıt bölümleme fikri çizge bölümleme alanında yakın zamanda popüler olmuştur. Biz de dama tahtası bölümleme problemini çözmek için bu çoklu-kısıt bölümleme fikrini hiperçizge parçalama yöntemine uyguladık. Düğüm ayırıcıları ile çizge bölümleme yöntemi vı
ABSTRACT HYPERGRAPH MODELS FOR SPARSE MATRIX PARTITIONING AND REORDERING Ümit V. Çatalyürek Ph.D. in Computer Engineering and Information Science Supervisor: Assoc. Prof. Cevdet Aykanat November, 1999 Graphs have been widely used to represent sparse matrices for various scientific applications including one-dimensional (ID) decomposition of sparse matrices for parallel sparse-matrix vector multiplication (SpMxV) and sparse matrix re ordering for low fill factorization. The standard graph-partitioning based ID de composition of sparse matrices does not reflect the actual communication volume requirement for parallel SpMxV. We propose two computational hypergraph mod els which avoid this crucial deficiency of the graph model on ID decomposition. The proposed models reduce the ID decomposition problem to the well-known hypergraph partitioning problem. In the literature, there is a lack of 2D decom position heuristic which directly minimizes the communication requirements for parallel SpMxV computations. Three novel hypergraph models are introduced for 2D decomposition of sparse matrices for minimizing the communication vol ume requirement. The first hypergraph model is proposed for fine-grain 2D de composition of the sparse matrices for parallel SpMxV. The second hypergraph model for 2D decomposition is proposed to produce jagged-like decomposition of the sparse matrix. The checkerboard decomposition based parallel matrix-vector multiplication algorithms are widely encountered in the literature. However, only the load balancing problem is addressed in those works. Here, we propose a new hypergraph model which aims the minimization of communication volume while maintaining the load balance among the processors for checkerboard decomposi tion, as the third model for 2D decomposition. The proposed model reduces the decomposition problem to the multi-constraint hypergraph partitioning problem. The notion of multi-constraint partitioning has recently become popular in graph partitioning. We applied the multi-constraint partitioning to the hypergraph par titioning problem for solving checkerboard partitioning. Graph partitioning by vertex separator (GPVS) is widely used for nested dissection based low fill or dering of sparse matrices for direct solution of linear systems. In this work, we IValso show that the GPVS problem can be formulated as hypergraph partition ing. We exploit this finding to develop a novel hypergraph partitioning-based nested dissection ordering. The recently proposed successful multilevel frame work is exploited to develop a multilevel hypergraph partitioning tool PaToH for the experimental verification of our proposed hypergraph models. Experimental results on a wide range of realistic sparse test matrices confirm the validity of the proposed hypergraph models. In terms of communication volume, the pro posed hypergraph models produce 30% and 59% better decompositions than the graph model in ID and 2D decompositions of sparse matrices for parallel SpMxV computations, respectively. The proposed hypergraph partitioning-based nested dissection produces 25% to 45% better orderings than the widely used multiple mimimum degree ordering in the ordering of various test matrices arising from different applications. Keywords: Sparse matrices, parallel matrix-vector multiplication, parallel pro cessing, matrix decomposition, computational graph model, graph partitioning, computational hypergraph model, hypergraph partitioning, fill reducing ordering, nested dissection.