Package jline.lib.perm

Class SaddlePointPermanent

java.lang.Object
jline.lib.perm.PermSolver
jline.lib.perm.SaddlePointPermanent
public class SaddlePointPermanent extends PermSolver
Saddle-point (SPM) approximation of the permanent of a positive matrix. Twin of MATLAB perm_spm.m and of the native Python SaddlePointPermanent. This is the HOMOGENEOUS variant of cache_spm: both 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 the coefficient 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. That is the one case cache_spm cannot serve: 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,
that is, 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 scaling; doubly stochastic when m is all ones). There phi = sum_k log S_k - sum_l m_l log xi_l is the log of the Gurvits capacity, an upper bound on the log permanent. 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, since all cofactors of a Laplacian are equal, and 
   log P = sum_l log(m_l!) - (h-1)/2 log(2 pi) + phi - 1/2 log det(H_red).
ACCURACY. 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. BethePermanent is a genuine lower bound.

  • Constructor Details

    • SaddlePointPermanent

      public SaddlePointPermanent(Matrix matrix, int[] m, double tolerance, int maxIterations, boolean solve)
      Constructor with all parameters.
      Parameters:
      matrix - n x h strictly positive matrix
      m - column multiplicities, non-negative and summing to n; null means all ones, which requires a square matrix
      tolerance - margin on the column sums at which the scaling stops
      maxIterations - maximum number of scaling sweeps
      solve - whether to run solve() after construction
      Throws:
      IllegalArgumentException - if the matrix is negative or not strictly positive, or the multiplicities do not sum to the row count

    • SaddlePointPermanent

      public SaddlePointPermanent(Matrix matrix, int[] m, boolean solve)
      Multiplicities and defaults for tolerance (1e-11) and maxIterations (10000).

    • SaddlePointPermanent

      public SaddlePointPermanent(Matrix matrix, boolean solve)
      Unit multiplicities, which requires a square matrix.

    • SaddlePointPermanent

      public SaddlePointPermanent(Matrix matrix)
      Unit multiplicities, not solved on construction.

  • Method Details

    • getLogValue

      public double getLogValue()
      Logarithm of the estimate, correct even when the estimate overflows.

    • getLogCapacity

      public double getLogCapacity()
      Log Gurvits capacity at the saddle point, an upper bound on the log permanent.

    • getXi

      public double[] getXi()
      Saddle point, unit geometric mean, zero on a column of multiplicity zero.

    • compute

      public void compute()
      Description copied from class: PermSolver
      Compute the permanent or approximation for the given matrix. This method must be implemented by all concrete solver classes. The result should be stored in the value field.
      Specified by:
      compute in class PermSolver