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](http://www.mathworks.com/matlabcentral/fileexchange/36224-matrix-permanent-using-ryser-algorithm/content/permanentRyser.m) 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?



Computing a large permanent
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](http://arxiv.org/abs/1108.0065)" for suggestions.


