File Exchange

image thumbnail

Matrix Permanent using Ryser Algorithm

version 1.0.0.0 (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.
else
%% insert original permanent code using the Ryser formula
end

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: http://www.mathworks.com/matlabcentral/fileexchange/52739-matrix-permanent-using-fast-ryser-algorithm

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