A load balancing strategy for parallel computation of sparse permanents. (Q2864488)

Suppose \(A = (a_{ij})\) is an \(n \times n\) matrix. The permanent of \(A\) is defined as \(\operatorname{Perm}(A) = \sum _{\sigma \in S_n}\prod _{i=1}^na_{i\sigma (i)}\). This matrix function not only attracts attention from mathematicians but also from chemists and computer scientists for some applications in solving problems in chemistry and computer science. The best classical algorithms for precise evaluation of the permanent of a matrix is Ryser's algorithm and its improvement by \textit{A. Nijenhuis} and \textit{H. S. Wilf} in [Combinatorial algorithms for computers and calculators. 2nd ed. New York etc.: Academic Press (1978; Zbl 0476.68047)]. A sparse matrix is a matrix with few nonzero entries. A hybrid algorithm is the best efficient algorithm for the structure properties of very sparse matrices [\textit{H. Liang} and \textit{F. S. Bai}, ``A partially structure-preserving algorithm for the permanents of adjacency matrices of fullerenes'', Comput. Phys. Commun. 163, No. 2, 79--84 (2004)].NEWLINENEWLINEIn the paper under review, a statistical analysis of the computation time of computing the permanent is presented. The authors prove that the permanent value has strong correlation to its computation time with the hybrid algorithm and present an improved load balancing strategy based on an approximation algorithm. Some numerical results are also given.