An efficient tree decomposition method for permanents and mixed discriminants

Introduction

The permanent of a $n\times n$ matrix $M$ is defined as

where the sum is over all permutations $\pi$ of the numbers $1,\ldots,n$. Computing the permanent is $\#\rm{P}$-hard [Valiant1979], which means that it is unlikely that it can be done efficiently for arbitrary matrices. As a consequence, research on this problem tends to fall into two categories: algorithms to approximate the permanent, and exact algorithms that assume some structure of the matrix. This paper lies in the second category. We further study related problems in structured higher dimensional arrays, such as mixed discriminants, hyperdeterminants and mixed volumes.

The permanent of a matrix can be generalized in several ways. In particular, given a list of $n$ matrices of size $n\times n$, its mixed discriminant generalizes both the permanent and the determinant [Gurvits2005, Bapat1989]. Our algorithm for the permanent extends in a natural way to compute the mixed discriminant. The natural structure to represent the sparsity pattern in this case is a tripartite (i.e., $3$-colorable) graph. The running time of the resulting algorithm is $\widetilde{O}(n^{2}+n\,3^{\omega})$, where $\omega$ is the treewidth of such graph. In particular, this algorithm can compute the determinant of a matrix in the same time.

More generally, our methods extend to generalized determinants/permanents on tensors. A special case of interest is the multidimensional permanent [Avgustinovich2010, Dow1987, Tichy2015]. Another interesting case is the first Cayley hyperdeterminant, also known as Pascal determinant, which is the simplest generalization of the determinant to higher dimensions [Cayley1846, Luque2003, Barvinok1995]. Note that unlike the determinant, the hyperdeterminant is $\#\rm{P}$-hard, in particular because it contains mixed discriminants as a special case [Gurvits2005, Hillar2013].

The diagram of Figure 1 summarizes the scope of the paper. It presents the main problems we consider, illustrating the relationships among them. Concretely, an arrow from $A$ to $B$ indicates that $B$ is a special instance of $A$. It also divides the problems according to its difficulty, with and without bounded treewidth assumptions. In this paper we start from the simplest problems, i.e., permanents and determinants of matrices, moving upwards in the diagram.

The document is structured as follows. In Section 2 we review the concept of treewidth and tree decompositions. We also present three graph abstractions of a sparse matrix. Among these graphs is the bipartite graph $G$ described above, and a projection $G^{X}$ onto the column set. In Section we present a decomposition method, Algorithm , that computes the permanent based on the graph $G^{X}$. We first use graph $G^{X}$ because the decomposition algorithm is easier to explain in this case. In Section we extend this method to work with the bipartite graph $G$, as shown in Algorithm . We provide a Matlab implementation of this algorithm. In Section we discuss the case of mixed discriminants, presenting a decomposition method for it. We also treat the case of generalized determinants/permanents on tensors. Finally, in Section we discuss the case of mixed volumes of zonotopes.

The best known to date method for exactly computing the permanent of a general matrix was given by Ryser and its complexity is $O(n\,2^{n})$ [Ryser1963]. There are two main research trends on permanent computation: approximation algorithms and exact algorithms for structured matrices. We briefly discuss related work in both of them. Tree decomposition algorithms, which belong to the second group, will be presented afterwards.

We first mention some work on approximation schemes. For arbitrary matrices, Gurvits gave a randomized polynomial time approximation, with error proportional to the operator norm [Gurvits2005]. For nonnegative matrices there is a vast literature, see e.g., [Vontobel2013] and the references therein. Most remarkably, Jerrum et al. gave a fully polynomial randomized approximation scheme (FPRAS) [Jerrum2004]. Recent work studies approximation schemes based on belief propagation, also for nonnegative matrices [Vontobel2013, Watanabe2010].

As for exact algorithms for structured matrices, different types of structure have been explored in the literature. Fisher, Kasteleyn and Temperley gave a polynomial time algorithm for matrices whose associated bipartite graph is planar [Kasteleyn1967, Temperley1961]. Barvinok showed that the permanent is tractable when the rank is bounded [Barvinok1996]. The case of $0/1$ circulant matrices has also been considered [Minc1987], as well as sparse $0/1$ Toeplitz matrices [Codenotti1997]. Schwartz showed a $O(\log(n)2^{6w})$ algorithm for certain band, Toeplitz matrices, where $w$ is the bandwidth [Schwartz2009]. Temme and Wocjan showed a $O(n\,2^{3w^{2}})$ algorithm for a special type of band matrices [Temme2012]. Note that for arbitrary band matrices our algorithm is $\widetilde{O}(n\,2^{2w})$.

Permanents and treewidth

Tree decomposition methods for permanent computation have been considered. Courcelle et al. first showed that the permanent can be computed efficiently if the treewidth is bounded [Courcelle2001], although their methods, based on the Feferman-Vaught-Shelah Theorem, do not lead to an implementable algorithm. Later work of Flarup et al. gives a $O(n\,2^{O(\omega^{2})})$ algorithm [Flarup2007]. This algorithm is extended in [Meer2011] to a wider class of matrices. Note the strong dependency on the treewidth. Furthermore, the graph abstraction used in the above methods, which is not the bipartite graph $G$, has two inconvenient features: its treewidth can be significantly larger than the one of $G$ (see Example 2.1) and it is dependent on the specific order of the columns of the matrix (see Remark 2.2).

Closer to this paper is the work of van Rooij et al. [Rooij2009]. They gave a $\widetilde{O}(n\,2^{\omega})$ decomposition algorithm for counting perfect matchings in a graph. Counting perfect matchings is closely related to the permanent, and one could derive from their proof an analogous, but different, method for calculating the permanent. Our algorithm could be seen as a variant of such method that is easier to extend to the higher dimensional problems we consider.

Mixed discriminants, mixed volumes, tensors

The higher dimensional problems we study generalize the permanent of a matrix, and thus are $\#\rm{P}$-hard in general. As for the permanent, there are two natural relaxations: approximation algorithms and exact algorithms under special structure. Approximation algorithms have been considered for mixed discriminants [Barvinok1997, Gurvits2005], mixed volumes [Barvinok1997, Dyer1998] and multidimensional permanents [Barvinok2011]. As for exact algorithms under special structure, we are only aware of Gurvits’ tractability result for mixed discriminants and the 4-hyperdeterminant under some bounded rank assumptions [Gurvits2005].

To our knowledge this is the first paper that studies tree decomposition methods for mixed discriminants, mixed volumes and generalized determinants/permanents on tensors. Related to this is a recent log-space algorithm for computing determinants under bounded treewidth assumptions [Balaji2015]. Also related is the problem of partitioning a low treewidth graph into $k$-cliques, which is considered in [Rooij2009].

Tree decompositions and matrix graphs

In this section we review some basic facts regarding tree decompositions of a graph. We also present three graphs that can be associated to a sparse matrix.

The notions of treewidth and tree decompositions are fundamental in many areas of computer science and applied mathematics [Dechter2003, bodlaender2008combinatorial]. Intuitively, the treewidth of a graph $G$ is a measure of how close it is to a tree. A graph has treewidth 1 if and only if it is a forest, i.e., a disjoint union of trees. The smaller the treewidth, the closer the graph is to a tree, and the easier it is to solve certain problems on it. We note that a graph of treewidth $\omega$ has at most $n\omega$ edges, and thus treewidth imposes a sparsity constraint. We give the formal definition now.

Let $G$ be a graph with vertex set $X$. A tree decomposition of $G$ is a pair $(T,\chi)$, where $T$ is a rooted tree and $\chi:T\to\{0,1\}^{X}$ assigns some $\chi(t)\subseteq X$ to each node $t$ of $T$, that satisfies the following conditions.

The union of $\{\chi(t)\}_{t\in T}$ is the whole vertex set $X$.

For every edge $(x_{i},x_{j})$ of $G$, there exists some node $t$ of $T$ with $x_{i},x_{j}\in\chi(t)$.

For every $x_{i}\in X$ the set $\{t:x_{i}\in\chi(t)\}$ forms a subtree of $T$.

The sets $\chi(t)$ are usually referred to as bags. The width $\omega$ of the decomposition is the size of the largest bag (minus one). The treewidth of $G$ is the minimum width among all possible tree decompositions.

Algorithms based on tree decompositions typically depend exponentially on the width of the decomposition, and polynomially on the number of nodes [bodlaender2008combinatorial]. Thus, given a graph $G$ it is desirable to obtain a tree decomposition of minimum width. However, finding the treewidth is NP-hard [Arnborg1987]. The treewidth of some simple graphs are known: for a tree is $1$, for a cycle graph is $2$, for the $n\times n$ grid graph is $n$, for the complete graph $K_{n}$ is $n-1$, for the complete bipartite graph $K_{n,n}$ is $n$. For general graphs, there are good heuristics and approximation algorithms [bodlaender2008combinatorial].

Tree decompositions are closely related to chordal graphs [Blair1993, Dechter2003]. Indeed, given a chordal graph $G$, we can construct a tree decomposition where the bags $\chi(t)$ correspond to its maximal cliques. We remark that there are at most $n$ maximal cliques in a chordal graph. In general, we can always assume that a tree decomposition has at most $n$ nodes.

The following is a simple property of tree decompositions.

Let $(T,\chi)$ be a tree decomposition of $G$. Then for any clique $Y$ of $G$ there is some node $t$ of $T$ with $Y\subseteq\chi(t)$.

For each vertex $y\in Y$, let $T_{y}$ denote the subtree of all bags containing $y$. Let $t_{y}\in T_{y}$ be the closest node to the root and let $d(t_{y})$ denote the distance from $t_{y}$ to the root. Observe that if $d(t_{y})\leq d(t_{y^{\prime}})$ then $t_{y^{\prime}}\in T_{y}$ (otherwise, $T_{y}\cap T_{y^{\prime}}=\emptyset$ and the edge $(y,y^{\prime})$ would not belong to any bag). Let $t\in\{t_{y}\}_{y\in Y}$ be the farthest away from the root, i.e., $d(t_{y})\leq d(t)$ for all $y\in Y$. It follows that $Y\subseteq\chi(t)$. ∎

2. Matrix graphs

The sparsity structure of a matrix, i.e., its pattern of nonzero entries, can be described in terms of a graph. We consider here three possible graph abstractions of such sparsity structure, and we compare their treewidths.

Let $M$ be a $n\times n$ matrix. We will index the rows with a set $A=\{a_{1},\ldots,a_{n}\}$ and the columns with a set $X=\{x_{1},\ldots,x_{n}\}$. We use subindices to index the coordinates of $M$, i.e., $M_{a,x}$ denotes the entry in the $a$-th row and $x$-th column. Similarly, let $M_{a}$ be the $a$-th row of $M$. We now present two (undirected) graphs that are usually associated to a sparse matrix.

Let $M$ be a $n\times n$ matrix, let $A$ denote its set of rows, and let $X$ denote its set of columns. The bipartite graph of $M$, denoted as $G(M)$, has vertices $A\cup X$, and there is an edge $(a,x)$ if $M_{a,x}$ is nonzero.

(Symmetrized graph) Let $M$ be a $n\times n$ matrix, let $A$ denote its set of rows, and let $X$ denote its set of columns. The symmetrized graph of $M$, denoted as $G^{s}(M)$, has vertices $1,\ldots,n$ and has an edge $(i,j)$ if $M_{a_{i},x_{j}}\neq 0$ or $M_{a_{j},x_{i}}\neq 0$.

Note that $G^{s}(M)$ is the adjacency graph of the symmetric matrix $M+M^{T}$, assuming no terms cancel out.

Note that the permanent of a matrix is invariant under independent row and column permutations. The bipartite graph $G$ preserves this invariance. On the other hand, the symmetrized graph $G^{s}$ is only invariant under simultaneous row and column permutations.