permanent.h File Reference

The PERMANENT of a matrix, exactly, by four algorithms. More...

#include <algorithm>
#include <cmath>
#include <cstddef>
#include <vector>
#include "line/num/number.h"
#include "line/util/error.h"
#include "line/util/matrix.h"

Include dependency graph for permanent.h:

Go to the source code of this file.

Namespaces
namespace	line
namespace	line::perm

Enumerations
enum class	line::perm::PermMethod { line::perm::Multiplicity = 0 , line::perm::Ryser , line::perm::RyserGray , line::perm::Naive }
	Which algorithm permanent should use. More...

Functions
template<class T>
T	line::perm::permanent_multiplicity (const Matrix< T > &m)
	Inclusion-exclusion over the DISTINCT columns.
template<class T>
T	line::perm::permanent_ryser (const Matrix< T > &m)
	Ryser's formula over explicit column subsets: O(2^n n^2).
template<class T>
T	line::perm::permanent_ryser_gray (const Matrix< T > &m)
	Ryser's formula in GRAY-CODE order: O(2^n n).
template<class T>
T	line::perm::permanent_naive (const Matrix< T > &m)
	Every permutation: n!
template<class T>
T	line::perm::permanent (const Matrix< T > &m, PermMethod method=PermMethod::Multiplicity)
	The permanent, by the chosen method.
template<class T>
Matrix< T >	line::perm::snap_to_lattice (const Matrix< T > &m, double tolerance=0.001)
	Round a matrix's entries onto a coarse lattice so repeated columns are found.

Detailed Description

The PERMANENT of a matrix, exactly, by four algorithms.

Port of python/line_solver/api/perm/exact.py. PYTHON-ONLY: no MATLAB or JAR twin, so native Python is the reference.

WHY A QUEUEING LIBRARY WANTS PERMANENTS. The normalizing constant of a closed multiclass network with distinguishable jobs is a permanent of the demand matrix with COLUMN MULTIPLICITIES given by the class populations – see api/pfqn/pfqn_lcfsqn_nc.h, which already relies on that identity. The permanent looks like a determinant with every sign made positive, and that single change removes the multilinear cancellation Gaussian elimination lives on, which is why there is no polynomial algorithm and why four of them are carried here rather than one.

THE FOUR, and when each is the right choice:

• MULTIPLICITY: inclusion-exclusion over the DISTINCT columns, weighted by binomial coefficients. Its cost is set by the number of distinct columns, not by n, so on the matrices this library actually forms – a station's demand repeated once per job of a class – it is the only tractable one. This is the default for exactly that reason.
• RYSER: the textbook 2^n subset sum, O(2^n n^2). No structure exploited, and the one to compare the others against.
• RYSER-GRAY: the same sum walked in GRAY-CODE order, so consecutive subsets differ in one column and the row sums update in O(n) instead of O(n^2). Same value, one factor of n cheaper.
• NAIVE: every permutation, n!. Unusable past about ten, and kept because it is the definition – it is what the others are verified against.

ALL FOUR RETURN THE SAME NUMBER, and the tests assert exactly that on random matrices. A permanent has no cheap independent check, so agreement between an O(n!) definition and an O(2^n) formula IS the verification.

ARITHMETIC: field. Ryser's alternating sum cancels heavily, so on a large matrix the exact instantiation is not a luxury.

Definition in file permanent.h.