A load balancing strategy for parallel computation of sparse permanents.

DOI10.1002/NLA.1844MaRDI QIDQ2864488zbMATH OpenOpenAlexFDO

Authors Lei Wang, Heng Liang, Fengshan Bai, Yan Huo

Publication date 6 December 2013

Published in Numerical Linear Algebra with Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1112.6072

zbMATH Keywords

accelerated ratioapproximation algorithmhybrid algorithmload balancingparallel computationpermanentsparse matrix

Mathematics Subject Classification ID

Determinants, permanents, traces, other special matrix functions (15A15) Numerical computation of determinants (65F40) Computational methods for sparse matrices (65F50) Parallel numerical computation (65Y05)

Abstract: The research in parallel machine scheduling in combinatorial optimization suggests that the desirable parallel efficiency could be achieved when the jobs are sorted in the non-increasing order of processing times. In this paper, we find that the time spending for computing the permanent of a sparse matrix by hybrid algorithm is strongly correlated to its permanent value. A strategy is introduced to improve a parallel algorithm for sparse permanent. Methods for approximating permanents, which have been studied extensively, are used to approximate the permanent values of sub-matrices to decide the processing order of jobs. This gives an improved load balancing method. Numerical results show that the parallel efficiency is improved remarkably for the permanents of fullerene graphs, which are of great interests in nanoscience.

Review text

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.

Recommendations

• Revisiting randomized parallel load balancing algorithms
• Revisiting Randomized Parallel Load Balancing Algorithms
• Towards scalable parallel numerical algorithms and dynamic load balancing strategies
• Tight bounds for parallel randomized load balancing
• scientific article; zbMATH DE number 967422
• Tight bounds for parallel randomized load balancing, extended abstract
• scientific article; zbMATH DE number 833701
• scientific article; zbMATH DE number 1263199

Cites work

• A hybrid algorithm for computing permanents of sparse matrices
• A Method for Finding Permanents of 0, 1 Matrices
• A partially structure-preserving algorithm for the permanents of adjacency matrices of fullerenes
• A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries.
• An analysis of Monte Carlo algorithm for estimating the permanent
• An efficient algorithm for computing permanental polynomials of graphs
• Approximating the Permanent
• Approximating the permanent of graphs with large factors
• Bounds for Certain Multiprocessing Anomalies
• Bounds on Multiprocessing Timing Anomalies
• Calculation of the permanent of a sparse positive matrix
• Clifford algebras and approximating the permanent
• scientific article; zbMATH DE number 3747179 (Why is no real title available?)
• scientific article; zbMATH DE number 3049708 (Why is no real title available?)
• The permanent of 0-1 matrices and Kallman's algorithm

Cited in

(1)

• A hybrid algorithm for computing permanents of sparse matrices

Describes a project that uses

Uses Software

• SparseMatrix

This page was built for publication: A load balancing strategy for parallel computation of sparse permanents.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2864488)