Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Is there a practical way to compute the permanent of a large ($91 \times 91$) $(0,1)$ matrix?

I have tried to use the matlab function written by Luke Winslow which works great for smaller matrices but it's not getting anywhere with this size.

UPDT: I am thinking of the incidence matrix of an order 9 projective plane. Does that help?

share|improve this question
    
Is there any symmetry or reduction that you can exploit? (An obvious example would be that it has a block submatrix all with the same entry.) Gerhard "Ask Me About Binary Matrices" Paseman, 2013.04.28 –  Gerhard Paseman Apr 28 '13 at 20:10
    
have you tried Brian Butler's code? sites.google.com/site/brianbutlerengineer/home/research (scroll to bottom of page) –  Carlo Beenakker Apr 28 '13 at 20:35
2  
My first guess would be that no, unless the matrix has some properties that will help (for instance, if it's an adjacency matrix of a planar graph): in general, computing permanents is a hard problem (sf. en.wikipedia.org/wiki/Permanent_is_sharp-P-complete ) –  Victor Kleptsyn Apr 28 '13 at 20:47
    
Do you need the exact value or would an approximation suffice? –  quid Apr 28 '13 at 20:58
1  
If the matrix is extremely sparse it could be possible. It is much bigger than problems usually solvable. –  Brendan McKay Apr 29 '13 at 2:39
show 5 more comments

2 Answers 2

up vote 6 down vote accepted

The answer is unfortunately probably no, but there are a few things you could try.

There are algorithms that run in time polynomial in the value of the permanent, meaning that the permanent can be computed quickly if its value is small, but that is not going to help you for the incidence matrix of a 9x9 projective plane, whose permanent will be huge. I think getting the exact value in your example will be hopeless unless you can exploit the geometric structure to dramatically reduce the size of the computation.

If you only want an approximation, then there's a little bit more hope. Famously, Jerrum, Sinclair and Vigoda exhibited a fully polynomial randomized approximation scheme. This was a fantastic theoretical achievement, but in practice the algorithm is not all that fast (having high exponents and multiplicative constants) and is not at all trivial to implement.

Your best bet may be to look at recent work on using belief propagation to approximate the permanent. I am not up to speed on the latest developments but I would start by contacting the authors of "Approximating the Permanent with Fractional Belief Propagation" for suggestions.

share|improve this answer
    
Timothy, when you write that there are algorithms that run in time polynomial in the value of the permanent, I assume you mean for nonnegative matrices only! For general matrices, I believe even deciding whether the permanent is (say) 0 or 1 is #P-hard under nondeterministic reductions. –  Scott Aaronson Apr 29 '13 at 21:32
    
Scott, yes, I was assuming 0-1 matrices (or more generally nonnegative matrices) throughout; perhaps I should have been more explicit. The Jerrum-Sinclair-Vigoda result is also for nonnegative matrices only. –  Timothy Chow Apr 30 '13 at 2:10
    
A general estimation method that I think would work here starts by defining any backtrack program that counts the matchings in this bipartite graph. Then estimate the number of nodes at the right level of the search tree by using Knuth's method that involves tracing random paths. This gives an unbiased estimator, though it can be hard to get a reliable estimate of the precision. –  Brendan McKay Apr 30 '13 at 11:09
1  
Yes, I've seen that happen too, but I've also had some successes. One thing that I've found to help a lot is to collapse some number of lower levels in the tree into one level (so when you get to that level you perform an exhaustive search). That takes care of the situation where most paths die out just before the end. Another modification that should help here would be to define the tree to exclude all useless branches (using a flow algorithm for example) so that no paths die out at all. It will be much slower but also much less skewed I think. –  Brendan McKay Apr 30 '13 at 16:09
1  
(Ran out of characters) There is another method where you act like you are generating the whole search tree, but toss a coin at each node to decide whether or not to make its children. The bias of the coin, perhaps different at each level, is adjusted in advance so that what remains is not too large but still has a fair number of leaves. I've made some spot-on predictions using this method, but I've never seen it analyzed. I don't think it is equivalent to Knuth's method. –  Brendan McKay Apr 30 '13 at 16:15
show 1 more comment

The general problem is very hard (#P-complete in complexity terms). A quick web search found this article that might be helpful:

share|improve this answer
    
A WSEAS conference proceedings? That does not necessarily mean the paper is a load of rubbish, but one should exercise a great deal of caution. –  Emil Jeřábek Apr 29 '13 at 11:44
add comment

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.