A load balancing strategy for parallel computation of sparse permanents.

DOI10.1002/NLA.1844zbMATH Open1289.65119arXiv1112.6072OpenAlexW2962941190MaRDI QIDQ2864488FDOQ2864488

Heng Liang, Yan Huo, Fengshan Bai, Lei Wang

Publication date: 6 December 2013

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

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.

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

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

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)

Cites Work

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

Cited In (1)

• A hybrid algorithm for computing permanents of sparse matrices

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)