An efficient tree decomposition method for permanents and mixed discriminants

DOI10.1016/J.LAA.2015.12.004MaRDI QIDQ905704zbMATH OpenOpenAlexFDO

Authors Diego Cifuentes, Pablo A. Parrilo

Publication date 28 January 2016

Published in Linear Algebra and its Applications (Search for Journal in Brave)

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

zbMATH Keywords

treewidthpermanenthyperdeterminantmixed discriminantstructured array

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Determinants, permanents, traces, other special matrix functions (15A15)

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 $omega$, is small. Our algorithm requires $O(n{2}^{o}mega)$ arithmetic operations to compute permanents, and $O(n^2+n{3}^{o}mega)$ for mixed discriminants and hyperdeterminants. We finally show that mixed volume computation continues to be hard under bounded treewidth assumptions.

Recommendations

• Efficient computation of the permanent of a sparse matrix
• Computing mixed discriminants, mixed volumes, and permanents
• An extended tree-width notion for directed graphs related to the computation of permanents
• An extended tree-width notion for directed graphs related to the computation of permanents
• Computing the permanent of (some) complex matrices

Cites work

• scientific article; zbMATH DE number 3182201 (Why is no real title available?)
• scientific article; zbMATH DE number 236540 (Why is no real title available?)
• scientific article; zbMATH DE number 3326387 (Why is no real title available?)
• A linear time algorithm for finding tree-decompositions of small treewidth
• A partial k-arboretum of graphs with bounded treewidth
• A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries.
• An extended tree-width notion for directed graphs related to the computation of permanents
• Belief propagation and loop calculus for the permanent of a non-negative matrix
• Bounded treewidth and space-efficient linear algebra
• Complexity of Finding Embeddings in a k-Tree
• Computing mixed discriminants, mixed volumes, and permanents
• Computing the partition function for perfect matchings in a hypergraph
• Convex combinatorial optimization
• Dimer problem in statistical mechanics-an exact result
• Dynamic Programming on Tree Decompositions Using Generalised Fast Subset Convolution
• Efficiently computing the permanent and Hafnian of some banded Toeplitz matrices
• Fourier meets M\"{o}bius: fast subset convolution
• Hankel hyperdeterminants and Selberg integrals
• Introduction to algorithms.
• Mathematical Foundations of Computer Science 2005
• Mixed discriminants of positive semidefinite matrices
• Most tensor problems are NP-hard
• New algorithms for linear \(k\)-matroid intersection and matroid \(k\)-parity problems
• On The Complexity of Computing Mixed Volumes
• On the Expressive Power of Planar Perfect Matching and Permanents of Bounded Treewidth Matrices
• On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic
• On the permanent of certain (0,1) Toeplitz matrices
• Permanental compounds and permanents of (0,1)-circulants
• Permanents of d-dimensional matrices
• The Bethe Permanent of a Nonnegative Matrix
• The Computational Complexity of Immanants
• The complexity of computing the permanent
• Two Algorithmic Results for the Traveling Salesman Problem

Cited in

(12)

• Chordal networks of polynomial ideals
• The permanent functions of tensors
• Efficient computation of permanents, with applications to boson sampling and random matrices
• An extended tree-width notion for directed graphs related to the computation of permanents
• An extended tree-width notion for directed graphs related to the computation of permanents
• On partly and nearly decomposable tensors
• Approximating permanents and hafnians
• Stability and complexity of mixed discriminants
• On the permanents of circulant and degenerate Schur matrices
• Tensor slice rank and Cayley's first hyperdeterminant
• On the parameterized intractability of determinant maximization
• Permanents of multidimensional matrices: properties and applications

This page was built for publication: An efficient tree decomposition method for permanents and mixed discriminants

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