Matrix permanent

This research relates to computing the permanent of an n-by-n matrix, especially a sparse one. First we share the definition of the matrix permanent.

1. Using the definition of permanent (above) there are n! permutations to compute, each requires (n-1) multiplies and one accumulate.

2. Ryser (1963) gave an algorithm with O(n^2 2^n) or O(n 2^n) operations to compute the permanent. This is the best known algorithm to-date for the general problem. (A. Nijenhuis and H.S. Wilf published a significant optimization of Ryser's algorithm in 1978)

3. Valiant (1979) showed the problem was #P-complete.

4. Mittal and Al-Kurdi (2001) gave an algorithm to compute the permanent of a sparse matrix. I have crudely implemented their Algorithm #2 in the interpreted MATLAB programming language. It was kinda slow, as expected for being interpretive, but its computation time scaled as O(1.43^n) (for n=3 to n=27) for random sparse matrices of column weight 3. That was interesting. It think it is a fair bit of work to code this algorithm so that it can be compiled and run faster --- I haven't done it, but I have some strategies in mind.

5. Using recursive co-factor expansion is another way to compute the permanent. It has some benefits with sparse matrices if you simply check that the cofactor will have non-zero weight before bothering to compute it. I find experimentally that its computation time grows as O(1.59^n) (for n=5 to n=35) for random sparse matrices of column weight 3. This simple algorithm written in the C-language is 300x faster than the interpreted Mittal algorithm (at n=10). I have included the source code for this at the bottom of the page.

So, given the range of matrix order that I'm interested in, it was an easy choice for me to select the compiled recursive algorithm. However, you can see that this algorithm does not have the absolute best scaling, so there is clearly a point where it would be interesting to invest more time in implementing Mittal's algorithm.

2015 update... I have made three permanent algorithm implementations available on The MathWorks/MATLAB Central file exchange. They are written in the C language in way that MATLAB can directly integrate their functionality, known as CMEX. They are the fastest implementations that I have for permanents:

• Matrix Permanent using Recursion (described above)

• Matrix Permanent using Nijenhuis-Wilf

• Permanent of (0,1) Matrix using Kallman

The final one is an implementation of Ralph Kallman's algorithm (1982) which applies only to (0,1) matrices. It allows the input matrix to be m-by-n with m <= n <= 64.

The subject of numerical precision is addressed in several of these packages and the file exchange comments. For example, for large non-negative matrices, it seems that Nijenhuis-Wilf is more precise than Ryser.