3
$\begingroup$

I need to compute the permanent of a 10*100 matrix. All the entries are either 0 or 1.

All I know is that I can compute the permanent of all 10*10 submatrices and then sum it to get the desired answer. But this involves 100C10=10^13 operations which is too much in my case.

Is there a better algorithm for this task?

Improve this question
$\endgroup$
12
  • $\begingroup$ Are you sure it is 10*100 matrix? What is the meaning of "100C10". I do not know this notation. Do you have any interesting recurrence relation on computing permanents? $\endgroup$ – babou Aug 9 '14 at 9:31
  • $\begingroup$ 100C10= 100!/(10!*90!)....for a nn matrix I can compute the permanent in O(2^nn^2) time...but problem here is it is a rectangular matrix $\endgroup$ – user3724568 Aug 9 '14 at 9:33
  • 1
    $\begingroup$ Thanks for the combination notation, I knew 2 others, not this one (good idea, actually). Your wikipedia link says a lot of things about permanent. Did you read it? It say for example that the matrix is square. It also says other things about complexity. Anything special about the elements of your matrics? ... are they simply real numbers? $\endgroup$ – babou Aug 9 '14 at 9:43
  • $\begingroup$ yes, I read it actually....only specialty is its a 0-1 matrix... $\endgroup$ – user3724568 Aug 9 '14 at 9:53
  • 1
    $\begingroup$ I don't know a better algorithm, but I do know that calculating the permanent of a 0-1 matrix is a classic #P-complete problem (en.wikipedia.org/wiki/Permanent_is_sharp-P-complete)... so you may need to look into numerical/approximation methods for problems in #P. $\endgroup$ – cristoper Aug 12 '14 at 3:35

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.