An efficient tree decomposition method for permanents and mixed discriminants
arXiv:1507.03046 · doi:10.1016/j.laa.2015.12.004
Abstract
We present an efficient algorithm to compute permanents, mixed discriminants and hyperdeterminants of structured matrices and multidimensional arrays (tensors). We describe the sparsity structure of an array in terms of a graph, and we assume that its treewidth, denoted as , is small. Our algorithm requires arithmetic operations to compute permanents, and for mixed discriminants and hyperdeterminants. We finally show that mixed volume computation continues to be hard under bounded treewidth assumptions.
arXiv comment32 pages, 4 figures
References in corpus (6)
- Sampling of partially distinguishable bosons and the relation to the multidimensional permanent
- The Bethe Permanent of a Non-Negative Matrix
- Hankel hyperdeterminants and Selberg integrals
- Unifying two Graph Decompositions with Modular Decomposition
- Belief Propagation and Loop Calculus for the Permanent of a Non-Negative Matrix
- Efficient Computation of the Permanent of Block Factorizable Matrices
Cited by in corpus (10)
- Classical simulation of boson sampling based on graph structure
- Quantum computational supremacy in the sampling of bosonic random walkers on a one-dimensional lattice
- Efficient computation of permanents, with applications to boson sampling and random matrices
- Chordal networks of polynomial ideals
- Monitoring-induced Entanglement Entropy and Sampling Complexity
- Exact recursive calculation of circulant permanents: A band of different diagonals inside a uniform matrix
- On the Parameterized Intractability of Determinant Maximization
- Approximating outcome probabilities of linear optical circuits
- A duality at the heart of Gaussian boson sampling
- On the Complexity of Toric Ideals