Parallel algorithms for computing sparse matrix permanents

Official URL: https://dx.doi.org/10.3906/ELK-1904-135

The permanent is an important characteristic of a matrix and it has been used in many applications. Unfortunately, it is a hard to compute and hard to approximate the immanant. For dense/full matrices, the fastest exact algorithm, Ryser, has O(2n−1n) complexity. In this work, a parallel algorithm, SkipPer, is proposed to exploit the sparsity within the input matrix as much as possible. SkipPer restructures the matrix to reduce the overall work, skips the unnecessary steps, and employs a coarse-grain, shared-memory parallelization with dynamic scheduling. The experiments show that SkipPer increases the performance of exact permanent computation up to 140× compared to the naive version for general matrices. Furthermore, thanks to the coarse-grain parallelization, 14–15× speedup on average is obtained with τ = 16 threads over sequential SkipPer. Overall, by exploiting the sparsity and parallelism, the speedup is 2000× for some of the matrices used in the experimental setting. The proposed techniques in this paper can be used to significantly improve the performance of exact permanent computation by simply replacing Ryser with SkipPer, especially when the matrix is highly sparse.