An efficient tree decomposition method for permanents and mixed discriminants

DOI10.1016/J.LAA.2015.12.004zbMATH Open1329.15020arXiv1507.03046OpenAlexW1755161631MaRDI QIDQ905704FDOQ905704

Authors: Diego Cifuentes, Pablo A. Parrilo 

Publication date: 28 January 2016

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

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.

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

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

zbMATH Keywords

treewidthpermanenthyperdeterminantmixed discriminantstructured array

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (12)

• 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
• On the parameterized intractability of determinant maximization
• Tensor slice rank and Cayley's first hyperdeterminant
• Chordal networks of polynomial ideals
• 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)