Random path method with pivoting for computing permanents of matrices

DOI10.1016/J.AMC.2006.07.070MaRDI QIDQ870138zbMATH OpenOpenAlexFDO

Authors Heng Liang, Lin-Song Shi, Fengshan Bai, Xiaoyan Liu

Publication date 12 March 2007

Published in Applied Mathematics and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.amc.2006.07.070

zbMATH Keywords

numerical examplesunbiased estimatorMonte Carlo methodpermanentrandom path methodRasmussen method

Mathematics Subject Classification ID

Monte Carlo methods (65C05) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Determinants, permanents, traces, other special matrix functions (15A15) Numerical computation of determinants (65F40)

Recommendations

• A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries.
• The method of random determinants for estimating the permanent
• FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
• An analysis of Monte Carlo algorithm for estimating the permanent
• Computing sparse permanents faster

Cites work

• scientific article; zbMATH DE number 3182201 (Why is no real title available?)
• scientific article; zbMATH DE number 3748431 (Why is no real title available?)
• scientific article; zbMATH DE number 3747179 (Why is no real title available?)
• scientific article; zbMATH DE number 819814 (Why is no real title available?)
• A Monte-Carlo Algorithm for Estimating the Permanent
• A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries
• An analysis of Monte Carlo algorithm for estimating the permanent
• An upper bound for the permanent of \((0,1)\)-matrices.
• Approximating the Permanent
• Approximating the number of monomer-dimer coverings of a lattice.
• Approximating the permanent: A simple approach
• Clifford algebras and approximating the permanent
• Combinatorial matrix theory
• Matching theory
• Permanents
• Random generation of combinatorial structures from a uniform distribution
• Systems of distinct representatives. II
• The complexity of computing the permanent

Cited in

(6)

• Path methods for strong shift equivalence of positive matrices
• A hybrid algorithm for multi-homogeneous Bézout number
• Efficient computation of permanents, with applications to boson sampling and random matrices
• Computation of matrix permanent with automatic differentiation
• scientific article; zbMATH DE number 4082843 (Why is no real title available?)
• Flexible manufacturing system selection using a combinatorial mathematics-based decision-making method

This page was built for publication: Random path method with pivoting for computing permanents of matrices

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