File Exchange Matrix Permanent using Ryser Algorithm

version 1.0.0.0 (1.54 KB) by Luke Winslow

Luke Winslow (view profile)

Matrix permanent calculated using the fast Ryser Algorithm.

Updated 17 Apr 2012

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.

H. Paul Keeler

H. Paul Keeler (view profile)

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

Michal Kvasnicka

Michal Kvasnicka (view profile)

serious troubles with accuracy!!!

Lina García

Brian Butler

Brian Butler (view profile)

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

Brian Butler (view profile)

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