File Exchange

image thumbnail

Matrix Permanent using Ryser Algorithm

version (1.54 KB) by Luke Winslow
Matrix permanent calculated using the fast Ryser Algorithm.

1 Download

Updated 17 Apr 2012

View License

Uses the Ryser Formula to calculate the permanent of a matrix. It is O((n^2)(2^n)) which is much faster than the naive algorithm O(n!n). The determinate of a matrix is defined as the analog of determinant where the signs of
each term in summation was removed.

Comments and Ratings (5)

For an empty matrix, I believe that the permanent is equal to one, which coincides with the determinant of an empty matrix.

So an if statement is needed, for example:

if isempty(A)
y=1; %the permanent of an empty matrix is one.
%% insert original permanent code using the Ryser formula

serious troubles with accuracy!!!

Brian Butler

I've found that Ryser's algorithm has numerical accuracy issues in floating point due to the large-valued products (of row sums). They are often much, much larger than the final result, drastically increasing the chances intermediate rounding. Try the following test. Compute permanentRyser(ones(15,15)) - factorial(15). It should be zero.

I am proposing a Ryser absolute +/-accuracy estimate of approximately accu = prod(sum(A,2)) *10 /2^53, for non-negative matrices.

Brian Butler

Nicely done. I sped it up by x4 using Gray coding. See my version here:

MATLAB Release Compatibility
Created with R2011a
Compatible with any release
Platform Compatibility
Windows macOS Linux
Tags Add Tags