Tell me more ×
Computational Science Stack Exchange is a question and answer site for scientists using computers to solve scientific problems. It's 100% free, no registration required.
up vote 3 down vote favorite

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.

share|improve this question
Since the matrix permanent is a sum, it seems very easy to go parallel. You can write a simple MPI, Openmp, or CUDA programs. – Hui Zhang Jun 18 '12 at 7:01
Would you care to post an example? The 0-1 matrix permanent problem is interesting to me, and there are some symmetry tricks to try. – hardmath Jul 27 '12 at 15:13

2 Answers

up vote 4 down vote accepted

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.

share|improve this answer
In particular, there's an approximation algorithm for non-negative entries (as in the 0-1 case), but it has been proven that even 0-1 is exponentially hard. – Aron Ahmadia Jun 18 '12 at 10:13
In that case I'm afraid you'll have to use symmetries and knowledge about the matrix to reduce the number of permutations you actually consider from $10^{89}$ to something around $10^{10}-10^{12}$. (I don't think that's impossible, but I can't help quipping that that might be one of the more awesome speed-ups of any algorithm ever ;-) – Wolfgang Bangerth Jun 18 '12 at 10:51
The page on computing the permanent says that using a Gray code will reduce the complexity by a factor of O(n). Since you have a matrix of order 64, you can store it in a 64 64-bit integers, and use bit tricks to count and sum up 1 bits. – Victor Liu Jun 18 '12 at 20:49
up vote 3 down vote

Computing prmanents is an NP-hard problem (for a sharper version of this, see http://en.wikipedia.org/wiki/Permanent_is_sharp-P-complete), hence (unless P=NP) there are no fast general algorithms. This explains why you run out of resources.

What do you need the permanents for? Perhaps one can reformulate the underlying problem to use computationally more amenable stuff rather than permanents!

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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