Classes
class	AdaPartSampler
	Adaptive partitioning (AdaPart) sampler for the permanent. More...
class	HuberLawSampler
	Huber-Law acceptance-rejection sampler for the permanent. More...
struct	PermSpmResult
	Outcome of the saddle-point expansion: the estimate and what produced it. More...

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

Functions
void	require_full_support (const Matrix< double > &m, const char *who)
	Sinkhorn scaling toward double stochasticity.
void	sinkhorn_scaling (const Matrix< double > &in, Matrix< double > B, std::vector< double > r, std::vector< double > *c, double tolerance=1e-10, std::size_t max_iterations=1000)
double	perm_heur (const Matrix< double > &m, double tolerance=1e-10, std::size_t max_iterations=1000)
	The Sinkhorn heuristic.
double	perm_bethe (const Matrix< double > &m, double epsilon=0.001, std::size_t max_iteration=200000)
	The Bethe permanent, by sum-product message passing.
PermSpmResult	perm_spm_expand (const Matrix< double > &a, const std::vector< std::size_t > &mult, double tolerance=1e-11, std::size_t max_iterations=10000)
	Saddle-point (SPM) approximation of the permanent.
double	perm_spm (const Matrix< double > &a, double tolerance=1e-11, std::size_t max_iterations=10000)
	The saddle-point estimate of the permanent of a square strictly positive matrix.
double	perm_spm (const Matrix< double > &a, const std::vector< std::size_t > &mult, double tolerance=1e-11, std::size_t max_iterations=10000)
	The saddle-point estimate with column l of a repeated mult[l] times.
double	perm_adapart (const Matrix< double > &m, std::uint64_t seed=0)
	AdaPart estimate of the permanent, with the reference defaults.
double	perm_huberlaw (const Matrix< double > &m, std::uint64_t seed=0)
	Huber-Law estimate of the permanent, with the reference defaults.
template<class T>
T	permanent_multiplicity (const Matrix< T > &m)
	Inclusion-exclusion over the DISTINCT columns.
template<class T>
T	permanent_ryser (const Matrix< T > &m)
	Ryser's formula over explicit column subsets: O(2^n n^2).
template<class T>
T	permanent_ryser_gray (const Matrix< T > &m)
	Ryser's formula in GRAY-CODE order: O(2^n n).
template<class T>
T	permanent_naive (const Matrix< T > &m)
	Every permutation: n!
template<class T>
T	permanent (const Matrix< T > &m, PermMethod method=PermMethod::Multiplicity)
	The permanent, by the chosen method.
template<class T>
Matrix< T >	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.

Enumeration Type Documentation

◆ PermMethod

enum class line::perm::PermMethod

strong

Which algorithm permanent should use.

Enumerator
Multiplicity
Ryser
RyserGray
Naive

Definition at line 61 of file permanent.h.

Function Documentation

◆ perm_adapart()

double line::perm::perm_adapart	(	const Matrix< double > &	m,
		std::uint64_t	seed = 0 )

inline

AdaPart estimate of the permanent, with the reference defaults.

Twin of MATLAB perm_adapart.m and of python perm/sampling.py.

Definition at line 762 of file perm_sampling.h.

References line::perm::AdaPartSampler::Classic, perm_adapart(), line::Matrix< T >::rows(), and line::perm::AdaPartSampler::solve().

Referenced by perm_adapart(), and line::pfqn::pfqn_jointmarg().

◆ perm_bethe()

double line::perm::perm_bethe	(	const Matrix< double > &	m,
		double	epsilon = 0.001,
		std::size_t	max_iteration = 200000 )

inline

The Bethe permanent, by sum-product message passing.

A LOWER BOUND of the permanent for a nonnegative matrix. Two message families – right-going r and left-going l – are iterated to a fixed point on the SQUARE ROOT of the matrix, and the Bethe free energy there is exponentiated.

THE DENOMINATOR EXCLUDES THE DIAGONAL, NOT THE ENTRY ITSELF. A textbook sum-product message from (i,j) omits column j of row i; this scheme omits the DIAGONAL element of the row instead, so one denominator serves the whole row and the numerator carries s(i,j). The two agree on a symmetric matrix and disagree otherwise – measured on a 4x4 dense instance, 386.3 for the textbook form against the reference's 325.7, both below the exact 1092 and so both bounds, but only one of them the reference's. Transcribed as written.

Parameters

epsilon	squared message change below which the iteration stops
max_iteration	cap on the message passing

Definition at line 276 of file perm_approx.h.

References perm_bethe(), require_full_support(), and line::Matrix< T >::rows().

Referenced by perm_bethe(), and line::pfqn::pfqn_jointmarg().

◆ perm_heur()

double line::perm::perm_heur	(	const Matrix< double > &	m,
		double	tolerance = 1e-10,
		std::size_t	max_iterations = 1000 )

inline

The Sinkhorn heuristic.

NO error bound in either direction – see the header.

A zero entry used to be nudged to 1e-15 before scaling. That is not invertible – it changes the permanent by n!*eps – so a non-positive entry is now REFUSED by require_full_support instead.

Definition at line 223 of file perm_approx.h.

References perm_heur(), require_full_support(), line::Matrix< T >::rows(), and sinkhorn_scaling().

Referenced by perm_heur(), and line::pfqn::pfqn_jointmarg().

◆ perm_huberlaw()

double line::perm::perm_huberlaw	(	const Matrix< double > &	m,
		std::uint64_t	seed = 0 )

inline

Huber-Law estimate of the permanent, with the reference defaults.

Twin of MATLAB perm_huberlaw.m and of python perm/sampling.py.

Definition at line 773 of file perm_sampling.h.

References line::perm::HuberLawSampler::Classic, perm_huberlaw(), line::Matrix< T >::rows(), and line::perm::HuberLawSampler::solve().

Referenced by perm_huberlaw(), and line::pfqn::pfqn_jointmarg().

◆ perm_spm() [1/2]

double line::perm::perm_spm	(	const Matrix< double > &	a,
		const std::vector< std::size_t > &	mult,
		double	tolerance = 1e-11,
		std::size_t	max_iterations = 10000 )

inline

The saddle-point estimate with column l of a repeated mult[l] times.

Definition at line 550 of file perm_approx.h.

References perm_spm(), perm_spm_expand(), and line::perm::PermSpmResult::value.

◆ perm_spm() [2/2]

double line::perm::perm_spm	(	const Matrix< double > &	a,
		double	tolerance = 1e-11,
		std::size_t	max_iterations = 10000 )

inline

The saddle-point estimate of the permanent of a square strictly positive matrix.

Definition at line 544 of file perm_approx.h.

References perm_spm(), perm_spm_expand(), and line::perm::PermSpmResult::value.

Referenced by perm_spm(), perm_spm(), and line::pfqn::pfqn_jointmarg().

◆ perm_spm_expand()

PermSpmResult line::perm::perm_spm_expand	(	const Matrix< double > &	a,
		const std::vector< std::size_t > &	mult,
		double	tolerance = 1e-11,
		std::size_t	max_iterations = 10000 )

inline

Saddle-point (SPM) approximation of the permanent.

THE HOMOGENEOUS CACHE_SPM.

Approximates the permanent of the matrix built from the n x h matrix a by repeating column l exactly mult[l] times, so sum(mult) must equal n; an empty mult means all ones, which requires a square matrix.

cache_spm and this routine evaluate the SAME Cauchy integral by Laplace's method and differ only in the generating function whose coefficient they extract:

cache_spm E(m) = prod_l m_l! [prod_l z_l^m_l] prod_k (1 + sum_l g_kl z_l) perm_spm P = prod_l m_l! [prod_l z_l^m_l] prod_k ( sum_l a_kl z_l)

The cache factor carries a "+1" because an item may stay out of the cache, so what it extracts is a RECTANGULAR permanent over n items and sum(m) < n slots. Dropping the "+1" forces every row to be matched, which is exactly the permanent and requires sum(m) == n – the one case cache_spm cannot serve, since at n == sum(m) its multipliers diverge and it falls back on cache_erec. Here the integrand is homogeneous and the saddle point is interior in the h-1 directions that survive.

METHOD. With z_l = xi_l exp(i th_l) the saddle point in xi solves

sum_k a_kl xi_l / (sum_j a_kj xi_j) = m_l, l = 1..h,

so p_kl = a_kl xi_l / s_k with s = a*xi is the diagonal scaling of a to row sums 1 and column sums m (Sinkhorn; doubly stochastic when m is all ones). There phi = sum_k log s_k - sum_l m_l log xi_l is the log Gurvits capacity. The Gaussian correction uses H = diag(m) - p'p, a weighted graph Laplacian on the columns: H*ones = 0, which is the invariance of the integrand under th -> th + c*ones that homogeneity creates. That direction is a full period rather than a Gaussian, so it contributes 2*pi and leaves an (h-1) dimensional Laplace integral; any principal (h-1) submatrix serves, because all cofactors of a Laplacian are equal. The estimate is

log P = sum_l log(m_l!) - (h-1)/2 log(2 pi) + phi - 1/2 log det(H_red).

ACCURACY, AND WHAT IT IS NOT. Exact for h == 1, where the permanent is n! prod_k a(k,0). It is a genuine asymptotic expansion as min(m) grows with h fixed, the ratio to the exact permanent falling from 1.11 at m = (2,2,2) to 1.02 at m = (3,3). At m = ones the dimension of the integral grows with the expansion parameter and the leading term keeps a systematic BIAS: on the n x n matrix of ones it returns (2 pi)^(-(n-1)/2) n^(n+1/2) against the exact n!, a ratio tending to (e/sqrt(2 pi))^n = 1.084^n, and random positive matrices track that closely (1.31 at n = 4, 1.87 at n = 8). So at m = ones it OVERESTIMATES, with a spread across matrices far tighter than the bias itself, and it is NOT a bound in either direction; perm_bethe is the routine to use when a bound is needed.

REQUIRES A STRICTLY POSITIVE MATRIX, for the reasons the header states: the scaling is what needs it, and flooring a zero is not invertible. Positivity also makes the column graph complete, hence H_red positive definite.

Definition at line 410 of file perm_approx.h.

References line::Matrix< T >::cols(), line::InputError::InputError(), line::perm::PermSpmResult::log_capacity, line::perm::PermSpmResult::log_value, perm_spm_expand(), require_full_support(), line::Matrix< T >::rows(), line::perm::PermSpmResult::value, and line::perm::PermSpmResult::xi.

Referenced by perm_spm(), perm_spm(), and perm_spm_expand().

◆ permanent()

template<class T>

T line::perm::permanent	(	const Matrix< T > &	m,
		PermMethod	method = PermMethod::Multiplicity )

The permanent, by the chosen method.

The default exploits repeated columns, which is the case this library generates: a class of N jobs contributes N identical columns.

Definition at line 246 of file permanent.h.

References line::InputError::InputError(), Multiplicity, Naive, permanent(), permanent_multiplicity(), permanent_naive(), permanent_ryser(), permanent_ryser_gray(), Ryser, and RyserGray.

Referenced by permanent().

◆ permanent_multiplicity()

template<class T>

T line::perm::permanent_multiplicity ( const Matrix< T > & m )

Inclusion-exclusion over the DISTINCT columns.

With R distinct columns of multiplicities m_1..m_R the sum runs over the box 0 <= f_k <= m_k rather than over 2^n subsets, so a matrix whose columns repeat – which is what a class population produces – costs prod (m_k + 1) terms instead of 2^(sum m_k).

Definition at line 126 of file permanent.h.

References line::Matrix< T >::cols(), line::InputError::InputError(), permanent_multiplicity(), and line::Matrix< T >::rows().

Referenced by permanent(), and permanent_multiplicity().

◆ permanent_naive()

template<class T>

T line::perm::permanent_naive ( const Matrix< T > & m )

Every permutation: n!

. The definition, and what the rest are checked against.

Definition at line 222 of file permanent.h.

References line::Matrix< T >::cols(), line::InputError::InputError(), permanent_naive(), and line::Matrix< T >::rows().

Referenced by permanent(), and permanent_naive().

◆ permanent_ryser()

template<class T>

T line::perm::permanent_ryser ( const Matrix< T > & m )

Ryser's formula over explicit column subsets: O(2^n n^2).

Definition at line 156 of file permanent.h.

References line::Matrix< T >::cols(), line::InputError::InputError(), permanent_ryser(), and line::Matrix< T >::rows().

Referenced by permanent(), and permanent_ryser().

◆ permanent_ryser_gray()

template<class T>

T line::perm::permanent_ryser_gray ( const Matrix< T > & m )

Ryser's formula in GRAY-CODE order: O(2^n n).

Consecutive subsets differ in exactly one column, so the row sums are updated rather than recomputed. That is where the factor of n goes.

Definition at line 187 of file permanent.h.

References line::Matrix< T >::cols(), line::InputError::InputError(), permanent_ryser_gray(), and line::Matrix< T >::rows().

Referenced by permanent(), and permanent_ryser_gray().

◆ require_full_support()

void line::perm::require_full_support	(	const Matrix< double > &	m,
		const char *	who )

inline

Sinkhorn scaling toward double stochasticity.

Returns the scaled matrix and the two diagonal scalings, since undoing them is what turns an estimate on the scaled matrix back into one on the original. Refuse a matrix the permanent approximations cannot take.

The approximations rest, directly or through the Sinkhorn scaling they share, on a strictly positive matrix. A zero used to be floored to a small eps first, and that substitution is not invertible: a matrix with an identically zero row has permanent 0 while the floored matrix has permanent n! eps times the permanent of the rest, which is O(1) by n = 18. Positivity is sufficient but not necessary – the sharp precondition is TOTAL SUPPORT, which a matrix with a positive permanent can still fail – but it is O(n^2) and is the contract this header already states.

Definition at line 161 of file perm_approx.h.

References line::Matrix< T >::cols(), line::InputError::InputError(), require_full_support(), and line::Matrix< T >::rows().

Referenced by perm_bethe(), perm_heur(), perm_spm_expand(), and require_full_support().

◆ sinkhorn_scaling()

void line::perm::sinkhorn_scaling	(	const Matrix< double > &	in,
		Matrix< double > *	B,
		std::vector< double > *	r,
		std::vector< double > *	c,
		double	tolerance = 1e-10,
		std::size_t	max_iterations = 1000 )

inline

Definition at line 174 of file perm_approx.h.

References line::InputError::InputError(), line::Matrix< T >::rows(), and sinkhorn_scaling().

Referenced by perm_heur(), and sinkhorn_scaling().

◆ snap_to_lattice()

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.

NOT the reference's preprocessing_ds, despite what this comment used to claim: that one is the Sinkhorn scaling to double stochasticity (python preprocessing_ds, JAR QueueingNetwork.preprocessingDS) and returns a rescaling factor alongside the matrix. This is an unrelated operation that merely shared the name. The multiplicity algorithm keys on EXACT column equality, so two demands that differ in the last bits are two distinct columns and the saving is lost; snapping to a tolerance recovers it. This is a deliberate perturbation of the input, not a numerical tidy-up, so it is a separate call rather than something permanent does silently.

Definition at line 270 of file permanent.h.

References line::Matrix< T >::cols(), line::InputError::InputError(), line::Matrix< T >::rows(), and snap_to_lattice().

Referenced by snap_to_lattice().

Classes

Enumerations

Functions

Enumeration Type Documentation

◆ PermMethod

Function Documentation

◆ perm_adapart()

◆ perm_bethe()

◆ perm_heur()

◆ perm_huberlaw()

◆ perm_spm() [1/2]

◆ perm_spm() [2/2]

◆ perm_spm_expand()

◆ permanent()

◆ permanent_multiplicity()

◆ permanent_naive()

◆ permanent_ryser()

◆ permanent_ryser_gray()

◆ require_full_support()

◆ sinkhorn_scaling()

◆ snap_to_lattice()