Computing matrix permanents and counting perfect matchings on GPUS

Official URL: https://risc01.sabanciuniv.edu/record=b2579346_(Table of contents)

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.