2

Task

I want to calculate the permanent P of a NxN matrix for N up to 100. I can make use of the fact that the matrix features only M=4 (or slightly more) different rows and cols. The matrix might look like

A1 ... A1 B1 ... B1 C1 ... C1 D1 ... D1   |
...                                       | r1 identical rows
A1 ... A1 B1 ... B1 C1 ... C1 D1 ... D1   | 
A2 ... A2 B2 ... B2 C2 ... C2 D2 ... D2   
...                                       
A2 ... A2 B2 ... B2 C2 ... C2 D2 ... D2
A3 ... A3 B3 ... B2 C2 ... C2 D2 ... D2
...
A3 ... A3 B3 ... B3 C3 ... C3 D3 ... D3
A4 ... A4 B4 ... B4 C4 ... C4 D4 ... D4
...
A4 ... A4 B4 ... B4 C4 ... C4 D4 ... D4
---------
c1 identical cols

and c and r are the multiplicities of cols and rows. All values in the matrix are laying between 0 and 1 and are encoded as double precision floating-point numbers.

Algorithm

I tried to use the Ryser formula to calculate the permanent. For the formula, one needs to first calculate the sum of each row and multiply all the row sums. For the matrix above this yields

 S0 = (c1 * A1 + c2 * B1 + c3 * C1 + c4 * D1)^r1 * ... 
    * (c1 * A4 + c2 * B4 + c3 * C4 + c4 * D4)^r4

As a next step the same is done with col 1 deleted

 S1 = ((c1-1) * A1 + c2 * B1 + c3 * C1 + c4 * D1)^r1 * ... 
    * ((c1-1) * A4 + c2 * B4 + c3 * C4 + c4 * D4)^r4

and this number is subtracted from S0.

The algorithm continues with all possible ways to delete single and group of cols and the products of the row sums of the remaining matrix are added (even number of cols deleted) and subtracted (odd number of cols deleted). The task can be solved relative efficiently if one makes use of the identical cols (for example the result S1 will pop up exactly c1 times).

Problem

Even if the final result is small the values of the intermediate results S0, S1, ... can reach values up to N^N. A double can hold this number but the absolute precision for such big numbers is below or on the order of the expected overall result. The expected result P is on the order of c1!*c2!*c3!*c4! (actually I am interested in P/(c1!*c2!*c3!*c4!) which should lay between 0 and 1).

I tried to arrange the additions and subtractions of the values S in a way that the sums of the intermediate results are around 0. This helps in the sense that I can avoid intermediate results that are exceeding N^N, but this improves things only a little bit. I also thought about using logarithms for the intermediate results to keep the absolute numbers down - but the relative accuracy of the encoded numbers will be still bounded by the encoding as floating point number and I think I will run into the same problem. If possible, I want to avoid the usage of data types that are implementing a variable-precision arithmetic for performance reasons (currently I am using matlab).

2
  • I have never worked with permanents before, but this is essentially a sum of products, correct? Have you tried accumulating the products with Kahan summation?
    – njuffa
    Aug 30, 2017 at 16:24
  • @njuffa Thank you for the suggestion. I tried to use the summation algorithm by Knuth to decrease the rounding errors during summation (for Matlab there is a nice package XSum [1] on file exchange). Unfortunately this did not improve the accuracy. I suspect the main problem is that the products S are already lacking the accuracy. [1] de.mathworks.com/matlabcentral/fileexchange/26800-xsum
    – hbar
    Aug 31, 2017 at 9:09

0

Your Answer

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

Browse other questions tagged or ask your own question.