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.

2 Downloads

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!!!

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.

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