Calculation of the permanent of a sparse positive matrix

DOI10.1016/S0010-4655(02)00683-5zbMath1196.15010OpenAlexW2068110173MaRDI QIDQ709358

Harald Forbert, Dominik Marx

Publication date: 18 October 2010

Published in: Computer Physics Communications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0010-4655(02)00683-5

Mathematics Subject Classification ID

Computational methods for sparse matrices (65F50) Determinants, permanents, traces, other special matrix functions (15A15) Positive matrices and their generalizations; cones of matrices (15B48) Complexity and performance of numerical algorithms (65Y20)

Related Items (9)

Expressing Polynomials as the Permanent of low rank Square Matrices ⋮ A hybrid algorithm for computing permanents of sparse matrices ⋮ Limit theorems for random permanents with exchangeable structure ⋮ A partially structure-preserving algorithm for the permanents of adjacency matrices of fullerenes ⋮ An efficient algorithm for computing permanental polynomials of graphs ⋮ Some results on certain generalized circulant matrices ⋮ Flexible manufacturing system selection using a combinatorial mathematics-based decision-making method ⋮ Fast Computation by Block Permanents of Cumulative Distribution Functions of Order Statistics from Several Populations ⋮ A load balancing strategy for parallel computation of sparse permanents

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A permanent formula with many zero-valued terms
• The complexity of computing the permanent
• Computing mixed discriminants, mixed volumes, and permanents
• An upper bound for the permanent of a nonnegative matrix
• Methods for scaling to doubly stochastic form
• A mildly exponential approximation algorithm for the permanent
• Approximating the Permanent
• A Method for Finding Permanents of 0, 1 Matrices
• A Monte-Carlo Algorithm for Estimating the Permanent
• A Relationship Between Arbitrary Positive Matrices and Doubly Stochastic Matrices
• A deterministic strongly polynomial algorithm for matrix scaling and approximate permanents
• A permanent algorithm with \(\text{exp}[\Omega(n^{1/3}/2\text{ln}n)\) expected speedup for \(0-1\) matrices]

This page was built for publication: Calculation of the permanent of a sparse positive matrix