perm_approx.h File Reference

APPROXIMATE permanents: the Sinkhorn heuristic, the Bethe estimate and the saddle-point expansion. More...

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

Include dependency graph for perm_approx.h:

Go to the source code of this file.

Classes
struct	line::perm::PermSpmResult
	Outcome of the saddle-point expansion: the estimate and what produced it. More...

Namespaces
namespace	line
namespace	line::perm

Functions
void	line::perm::require_full_support (const Matrix< double > &m, const char *who)
	Sinkhorn scaling toward double stochasticity.
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)
double	line::perm::perm_heur (const Matrix< double > &m, double tolerance=1e-10, std::size_t max_iterations=1000)
	The Sinkhorn heuristic.
double	line::perm::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	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)
	Saddle-point (SPM) approximation of the permanent.
double	line::perm::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	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)
	The saddle-point estimate with column l of a repeated mult[l] times.

Detailed Description

APPROXIMATE permanents: the Sinkhorn heuristic, the Bethe estimate and the saddle-point expansion.

Port of python/line_solver/api/perm/approx.py, itself a twin of MATLAB's perm_heur.m and of jline.lib.perm.BethePermanent.

WHY APPROXIMATE AT ALL. The exact algorithms in permanent.h cost 2^n or n!, and the multiplicity method only escapes that when columns repeat. On a dense matrix with distinct columns neither is usable past about thirty, and these two are what remain.

THE THREE ARE NOT INTERCHANGEABLE, and a caller has to know which guarantee it is getting:

• perm_heur is a HEURISTIC with no error bound in either direction. It Sinkhorn-scales the matrix toward double stochasticity, averages a mean-field van der Waerden estimate with a Gurvits capacity bound on the scaled matrix, and undoes the scaling. The average of a lower bound and a mean-field estimate is neither.
• perm_bethe is a LOWER BOUND on a STRICTLY POSITIVE matrix, which is a real guarantee and the reason to prefer it when one is needed. It runs sum-product message passing on the square root of the matrix to a fixed point and exponentiates the Bethe free energy there.
• perm_spm is the saddle-point (Laplace) expansion of the coefficient integral, the HOMOGENEOUS variant of cache_spm. It is exact in the limit of large column multiplicities and, at unit multiplicities, overestimates by a factor near (e/sqrt(2 pi))^n with a tight spread across matrices. No bound in either direction, but far closer than the bare capacity it corrects, and it is the one of the three that takes repeated columns.

ALL REQUIRE A STRICTLY POSITIVE MATRIX and refuse otherwise, by name and with the offending position. Two separate reasons:

• a NEGATIVE entry: Sinkhorn scaling diverges rather than failing, and the Bethe bound is simply not a bound off the nonnegative orthant;
• a ZERO entry: the matrix has no full support. Both routines used to floor a zero to a small eps first, and that substitution is NOT INVERTIBLE. Every permutation takes one entry per row, so the floored matrix has permanent n! eps times the permanent of the rest against a true permanent that may be 0; n! outruns eps by n = 18, and the order of the replicated demand matrix in pfqn_jointmarg is sum(N). The floored answers were also simply wrong: on a 3x3 of ones with two zeroed entries, whose permanent is 3, perm_bethe returned 2748880111.1018 – the lower-bound property gone by nine orders of magnitude – and perm_heur returned the van der Waerden bound of the Sinkhorn limit of the FLOORED matrix.

Positivity is sufficient but not necessary. The sharp precondition of the Sinkhorn scaling is TOTAL SUPPORT: every positive entry lies on a positive permutation. A matrix with a strictly positive permanent can still fail it – [[J3, 0], [J3, J3]] has permanent 36 and no total support, and the scaling then stalls on its tolerance instead of converging. Positivity is the test used because it is O(n^2). Use the exact engine for a matrix with zeros.

ARITHMETIC: double. All are iterative floating-point schemes.

Definition in file perm_approx.h.