I need to compute the Matrix Permanents of several $64 \times 64$, zero-one matrices. I have tried using the built in functions in both Sage and Maple, but both programs return out of memory errors. I have also tried several MatLab implementations, but they tend to run very slowly, on the order of days or weeks. I am wondering whether anyone has any suggestions (functions, programs, methods) of how I might compute these matrix permanents. I have access to Sage, Maple, and MatLab, and I also do a fair amount of work in Python. The matrices themselves have between 16-24 ones per row/column in the densest case and 6-8 ones per row/column in the sparsest case.
Computing Permanents of $64 \times 64$ Matrices
linear algebra;matrices
The wikipedia article you link to has several references to computing the permanent for unweighted graphs, which is exactly what you have in your case. It might be worthwhile exploring these directions.In general, looking at the definition of the permanent, the difficulty is that there are many permutations for 64 indices -- 64! in fact, quite an unwieldy number, about $10^{89}$. If we ignore this fact for a moment, computing the weight of each permutation is probably difficult for Matlab/Sage/Maple/... if you store the matrix as floating point numbers, but it should be reasonably straightforward if you wrote such a code in C/C++ and store the 0/1 entries as booleans. You then only need to compute the product of each weight as long as the factor is 'true', and terminate the computation if you hit a 'false', continuing with the next permutation. This is akin to a branch and bound algorithm. But that doesn't get you around the problem that there are so many permutations. The only approaches I can see working for this are (i) use symmetries in and other knowledge about your matrices to reduce the number of interesting permutations to a more manageable size, and (ii) following up on the connection to graphs, in particular that the permanent of a 0/1 matrix equals the number of cycle covers. I'm not a graph expert but there may be specialized algorithms for computing cycle covers.