Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6416156 | Linear Algebra and its Applications | 2016 | 37 Pages |
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 OË(n2Ï) arithmetic operations to compute permanents, and OË(n2+n3Ï) for mixed discriminants and hyperdeterminants. We finally show that mixed volume computation continues to be hard under bounded treewidth assumptions.
Related Topics
Physical Sciences and Engineering
Mathematics
Algebra and Number Theory
Authors
Diego Cifuentes, Pablo A. Parrilo,