1
$\begingroup$

I'm trying to find an efficient algorithm/technique to calculate, or approximate, the permanent of a matrix. After reading some literature, it seems nothing exists faster than Ryser's algorithm in the general case. Unfortunately this is too slow for my purposes at $O(2^{n-1}n)$.

My matrix has a lot of duplicate columns, and so I was wondering if there was a way to use that structure to improve the efficiency of the calculation, or make an approximation. My matrix looks a bit like this:

$$ A = \begin{bmatrix} A^2 & A^2 & A & A & A & 1 & 1 & 1 & 1\\ B^2 & B^2 & B & B & B & 1 & 1 & 1 & 1\\ C^2 & C^2 & C & C & C & 1 & 1 & 1 & 1\\ D^2 & D^2 & D & D & D & 1 & 1 & 1 & 1\\ E^2 & E^2 & E & E & E & 1 & 1 & 1 & 1\\ F^2 & F^2 & F & F & F & 1 & 1 & 1 & 1\\ G^2 & G^2 & G & G & G & 1 & 1 & 1 & 1\\ H^2 & H^2 & H & H & H & 1 & 1 & 1 & 1\\ J^2 & J^2 & J & J & J & 1 & 1 & 1 & 1\\ \end{bmatrix} $$

Any ideas? Or alternatively a proof that the computation cannot be made more efficient would be very useful.

$\endgroup$
5
  • $\begingroup$ Can you describe a bit how the above shape generalizes to the n by n case? Perhaps it has at most k distinct columns of degree at most d? $\endgroup$ – Pat Devlin Jun 18 '20 at 13:38
  • $\begingroup$ The actual matrices have at most F distinct columns and have size W. F is around 1000 and W is around 20000 or more, the maximum exponent of a column is around 1000. But I might be able to break the problem down so that there are only 3 distinct columns, just like above, but the matrix is about 1000 columns long. So there will be a few hundred of the columns with elements squared, a few hundred to the power of 1 and a few hundred to the power of zero i.e. 1. $\endgroup$ – chasmani Jun 18 '20 at 13:48
  • $\begingroup$ If you expand an $n\times n$ permanent by the first row, then you will get a sum of $n$ $(n-1)\times (n-1)$ permanents. In your example, this reduces to a linear combination of three $8\times 8$ permanents. You can then iterate. This will save some time, but maybe not enough for you. $\endgroup$ – Richard Stanley Jun 18 '20 at 14:21
  • $\begingroup$ Yes, the idea of @RichardStanley gives you something like order $F^n$ time to compute an $n \times n$ matrix having $F$ distinct columns. $\endgroup$ – Pat Devlin Jun 18 '20 at 14:36
  • 1
    $\begingroup$ In the paper "Two Algorithmic Results for the Traveling Salesman Problem" by A. Barvinok, an $n^{O(r)}$ time algorithm is given for computing the permanent of an $n \times n$ rank $r$ matrix (Thm. 3.3). In particular, this gives a polynomial time algorithm in the case when you only have 3 distinct columns. $\endgroup$ – Kevin Jun 18 '20 at 14:54
3
$\begingroup$

Aha! Here we go.

Just use Ryser's formula exactly as is, but be clever not to redo work you've already done. If it's an $n \times n$ matrix with $F$ distinct columns, you'll be able to compute its permanent in time roughly $F n^{1+F}$ ish (which would be great if you can get $F$ down).

More details:

Recall Ryser's formula is

$$\text{perm}(A) = (-1)^n \sum_{S \subseteq [n]} (-1)^{|S|} \prod_{i=1} ^{n} \sum_{j \in S} a_{i,j}.$$

The problem is that if we don't do anything clever, then there are too many terms of this sum. But! In our case, many of these terms are equal. The thing we're adding up depends on $S$, but it actually just depends on how many columns of each type are in $S$. [If this is already clear, then don't bother reading the rest]

Let's say that the distinct columns of $A$ are $\vec{x}^{(1)}, \vec{x}^{(2)}, \ldots , \vec{x}^{(F)}$ and that $\vec{x}^{(j)}$ appears $f_j$ times. Then the above sum is equal to

$$\text{perm}(A) = (-1)^n \sum_{(s_1, s_2, \ldots, s_F)}(-1)^{s_1 + s_2 + \cdots + s_F} \prod_{j=1} ^{F} {f_j \choose s_j} \prod_{i=1} ^{n} \sum_{k = 1} ^{F} s_k \vec{x}^{(k)} _{i},$$

where the sum is taken over all non-negative vectors [summing to at most $n$, where each coordinate $s_i$ is at most $f_i$]. A crude bound is that there are at most $\mathcal{O}(n^F)$ such terms, giving this a running time of at most like $\mathcal{O}(n^{F+1} F)$ or whatever.

Of course, this doesn't use anything about what the columns look like (and the above sum might be easier to compute than just adding up each term). But it's a start.


(Added as per suggestion) Working out $F=3$ Suppose we are in the optimistic case that the matrix has $n$ columns but only $3$ distinct columns. Let's call these columns $\vec{x}, \vec{y}$, and $\vec{z}$, and suppose each appears $f_x, f_y,$ and $f_z$ times (respectively). [So we have $f_x + f_y + f_z = n$]

Then we have

$$\text{perm}(A) = (-1)^n \sum_{(a, b, c)}(-1)^{a+b+c} {f_x \choose a} {f_y \choose b} {f_z \choose c} \prod_{i=1} ^{n} (a \vec{x}_{i} + b \vec{y}_i + c \vec{z}_i),$$

where the sum is taken over all triples $(a,b,c)$ summing to at most $n$.

Said slightly differently, for a vector $\vec{u} \in \mathbb{R}^n$, let $V(\vec{u}) = u_1 u_2 \cdots u_n$ be the product of its coordinates. [So $V(\vec{u})$ is the (signed) volume of the axis-parallel box with one corner at the origin and an antipodal corner at $\vec{u}$] Then the above formula is just $$\text{perm}(A) = (-1)^n \sum_{(a, b, c)}(-1)^{a+b+c} {f_x \choose a} {f_y \choose b} {f_z \choose c} V(a \vec{x} + b \vec{y} + c \vec{z}),$$ which looks a little nicer to me and feels more geometric. [I'm then tempted to write this linear combination as a product of a matrix and the vector $(a,b,c)$, but let's not]

(If you'd like me to sketch some code or work out an example or something, lemme know)

$\endgroup$
1
  • 1
    $\begingroup$ For the above example, the sum is pretty clear: take all possible five letter subsets of the first eight letters, for each pick all subsets of size two to square, and note that this can be done in twelve ways for each monomial. Then multiply by 24. The result is 288 times a certain monic symmetric function in all the letters. The original poster might appreciate a specialization of your solution worked out for three types. If columns within a type differ, replace twelve by a certain breakdown. Gerhard "Working On Permanent Mental Arithmetic" Paseman, 2020.06.18. $\endgroup$ – Gerhard Paseman Jun 18 '20 at 16:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.