File Exchange

image thumbnail

Permanent of (0,1) Matrix using Kallman in CMEX

version 1.2 (26.8 KB) by Brian Butler
Computes the permanent of a (0,1) matrix.


Updated 16 Oct 2020

View Version History

View License

Computes the permanent of a (0,1) matrix. This implementation is in CMEX (C language for MATLAB) and is often faster than my implementation in CMEX of the Laplace expansion algorithm for matrix order, n >= 6. The latter uses recursion and has an optimization for sparse matrices. This contribution, "permKallman", is an implementation of Ralph Kallman's algorithm (1982) which applies only to (0,1) matrices. The matrices do not have to be square; in this implementation, the m-by-n input matrix is required to satisfy m <= n <= 64. Usage of this algorithm is advantageous when the matrix is sparse. In limited testing on sparse square (0,1) matrices, we found our Nijenhuis-Wilf implementation to be faster when the column weight was greater than 4 and Kallman's algorithm to be faster when the column weight was less than 4. When m > 27 and the column weight was 3, this algorithm was 1000x (or more) faster than Nijenhuis-Wilf. (See the speed testing results provided in PDF format.)
All internal calculations are always carried out using uint64 values, exactly. There are no approximations and no rounding, internally. However, there is no overflow detection on the uint64 calculations! The final result is returned in the class specified and overflow and rounding warnings are provided only at this final step.

---Tested Using---
MATLAB 2015b on Windows7 using MinGW-w64 64-bit compiler (gcc 4.9.2; This compiler package is the default add-on for MATLAB 2015b.)
MATLAB 2008b on Windows7 using Microsoft Visual C++ 2008 Express Edition SP1
Failed to compile using Lcc-win32 2.4.1 (This compiler is included with MATLAB 2009a.)

Cite As

Brian Butler (2020). Permanent of (0,1) Matrix using Kallman in CMEX (, MATLAB Central File Exchange. Retrieved .

Comments and Ratings (5)

Michal Kvasnicka

Thanks for latest update ...

Michal Kvasnicka

On R2020b I have the following problem:

mex -O permKallman.c
Building with 'gcc'.
/data/kva//Matlab_code/permKallman.c: In function ‘mexFunction’:
/data/kva//Matlab_code/permKallman.c:428:13: warning: implicit declaration of function ‘stricmp’; did you mean ‘strncmp’? [-Wimplicit-function-declaration]
428 | if (stricmp(buf,"double")==0) outclass=mxDOUBLE_CLASS;
| ^~~~~~~
| strncmp

Error using mex
/usr/bin/ld: /tmp/mex_91330082099403_42557/permKallman.o: in function `mexFunction':
permKallman.c:(.text+0x9cb): undefined reference to `stricmp'
/usr/bin/ld: permKallman.c:(.text+0x9e4): undefined reference to `stricmp'
/usr/bin/ld: permKallman.c:(.text+0xb9a): undefined reference to `stricmp'
/usr/bin/ld: permKallman.c:(.text+0xc0d): undefined reference to `stricmp'
/usr/bin/ld: permKallman.c:(.text+0xc8d): undefined reference to `stricmp'
collect2: error: ld returned 1 exit status

Michal Kvasnicka

Michal Kvasnicka

Michal Kvasnicka

Nice and clean!!!

MATLAB Release Compatibility
Created with R2016a
Compatible with any release
Platform Compatibility
Windows macOS Linux

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!