An efficient tree decomposition method for permanents and mixed discriminants
Published in Linear Algebra and its Applications, 2016
Recommended citation: Diego Cifuentes, Pablo Parrilo (2016). "An efficient tree decomposition method for permanents and mixed discriminants." Linear Algebra and its Applications. 493:45-81. http://dx.doi.org/10.1016/j.laa.2015.12.004
We present an efficient algorithm to compute permanents, mixed discriminants and hyperdeterminants of structured matrices and multidimensional arrays. We describe the sparsity structure of an array in terms of a graph, and we assume that its treewidth ω is small. Our algorithm requires O(n 2^ω) operations to compute permanents, and O(n^2 + n 3^ω) for mixed discriminants and hyperdeterminants. Mixed volume computation remains NP-hard for bounded treewidth.
See also:
- My slides from SIAM Conference on Discrete Mathematics’ 16
- My Matlab code