Computing matrix permanents and counting perfect matchings on GPUS

Warning The system is temporarily closed to updates for reporting purpose.

Yağlıoğlu, Berk (2021) Computing matrix permanents and counting perfect matchings on GPUS. [Thesis]

[thumbnail of 10364196.pdf] PDF
10364196.pdf

Download (752kB)

Abstract

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×n matrix’s permanent value has a time complexity of O(2n−1n). 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.
Item Type: Thesis
Uncontrolled Keywords: permanent, perfect matching. -- bipartite graph. -- High Performance Computing. -- #P-complete. -- permanent. -- mükemmel eşleme. -- iki parçalı çizge. -- GPU. -- Yüksek Basarımlı Hesaplama. -- #P-tam.
Subjects: T Technology > TK Electrical engineering. Electronics Nuclear engineering > TK7800-8360 Electronics > TK7885-7895 Computer engineering. Computer hardware
Divisions: Faculty of Engineering and Natural Sciences > Academic programs > Computer Science & Eng.
Faculty of Engineering and Natural Sciences
Depositing User: IC-Cataloging
Date Deposited: 18 Oct 2021 15:35
Last Modified: 26 Apr 2022 10:38
URI: https://research.sabanciuniv.edu/id/eprint/42490

Actions (login required)

View Item
View Item