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

hybrid algorithmsparse matrixapproximation algorithmparallel computationload balancingpermanentaccelerated ratio

Mathematics Subject Classification ID

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

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.

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
• Publication:4860190
• scientific article; zbMATH DE number 1263199

Cites work

• scientific article; zbMATH DE number 3747179 (Why is no real title available?)
• scientific article; zbMATH DE number 3049708 (Why is no real title available?)
• A Method for Finding Permanents of 0, 1 Matrices
• A hybrid algorithm for computing permanents of sparse 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
• 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)