Efficient computation of the permanent of a sparse matrix

DOI10.1080/00207160108805061MaRDI QIDQ2740952zbMATH OpenOpenAlexFDO

Authors Ahmad Al-Kurdi, R. C. Mittal

Publication date 10 March 2002

Published in International Journal of Computer Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1080/00207160108805061

zbMATH Keywords

\((0,1)\)-matricesnumerical examplespermanentsparse matrixtree theory

Mathematics Subject Classification ID

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

Review text

An efficient method is described for computing the permanent of \((0,1)\)-matrices. The method is based on tree theory, and is more efficient than other methods known from the literature. Numerical examples illustrate the methodology.

Recommendations

• Calculation of the permanent of a sparse positive matrix
• A hybrid algorithm for computing permanents of sparse matrices
• Computing the permanent of (some) complex matrices
• Computing permanents via determinants for some classes of sparse matrices
• The permanent of 0-1 matrices and Kallman's algorithm

Cites work

• A note on the permanent value problem
• A permanent formula with many zero-valued terms
• scientific article; zbMATH DE number 3182201 (Why is no real title available?)
• scientific article; zbMATH DE number 3358495 (Why is no real title available?)
• The complexity of computing the permanent

Cited in

(11)

• How fast can one compute the permanent of circulant matrices?
• The permanent of 0-1 matrices and Kallman's algorithm
• Efficient vectors for simple perturbed consistent matrices
• A hybrid algorithm for computing permanents of sparse matrices
• A permanent formula with many zero-valued terms
• scientific article; zbMATH DE number 5929618 (Why is no real title available?)
• The Design and Use of Algorithms for Permuting Large Entries to the Diagonal of Sparse Matrices
• Improved algorithms for permanent and permanently polynomial of sparse graph
• Calculation of the permanent of a sparse positive matrix
• An efficient tree decomposition method for permanents and mixed discriminants
• Efficiently computing the permanent and Hafnian of some banded Toeplitz matrices

This page was built for publication: Efficient computation of the permanent of a sparse matrix

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