Ray (WKB) asymptotic expansion of the cost-capped cache normalizing constant. More...

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

Include dependency graph for cache_spm_size.h:

Classes
struct	line::cache::CacheSpmSizeResult< T >
	Outcome of the expansion. More...

Namespaces
namespace	line
namespace	line::cache

Enumerations
enum class	line::cache::CacheCostMode { line::cache::AtMost , line::cache::Exact }
	Whether the caps bound the cost from above (matching cache_erec) or resolve it exactly. More...

Functions
template<class T>
CacheSpmSizeResult< T >	line::cache::cache_spm_size (const Matrix< T > &gamma, const std::vector< int > &m, const std::vector< int > &sigma, const std::vector< int > &k, CacheCostMode mode=CacheCostMode::AtMost)
	Ray (WKB) asymptotic expansion of the cost-capped cache normalizing constant.

Detailed Description

Ray (WKB) asymptotic expansion of the cost-capped cache normalizing constant.

Templated port of matlab/src/api/cache/cache_spm_size.m, cross-checked against jar/src/main/java/jline/api/cache/Cache_spm_size.java and python/line_solver/api/cache/spm_size.py.

Approximates what cache_erec(gamma, m, sigma, k) computes exactly, in the SAME normalization, so the two are interchangeable. This is the item-size extension of retrieval_rayint, which carries the size-free expansion; call that one when there are no storage costs.

Writing E = prod_j m_j! * H, the size-free recursion

E(m,n) = E(m,n-1) + sum_j gamma_{n,j} m_j E(m-1_j,n-1), E(0,0)=1

relaxes to H ~ exp(phi/eps) with n = y/eps, m_j = x_j/eps, whose eikonal e^{phi_y} = 1 + sum_j gamma_j(y) e^{-phi_j} carries the ray constants xi_j = e^{-phi_j}. With per-item storage costs sigma_i and per-list cost caps k_j the recursion gains the cost coordinate,

E(m,k) = E_i(m,k) + sum_j m_j gamma_ij E_i(m-1_j, k-sigma_i 1_j),

so the shift 1_j becomes e_j(y) = (1_j, s(y) 1_j) in the enlarged space X = (x,kappa) and the eikonal picks up the size tilt

e^{phi_y} = 1 + sum_j gamma_j(y) e^{-phi_{x_j} - s(y) phi_{kappa_j}},

with the second family of ray constants zeta_j = e^{-phi_{kappa_j}}. The rays integrate to the discrete saddle point of the product generating function

sum_{m,k} H(m,k) prod_j z_j^{m_j} w_j^{k_j} = prod_i ( 1 + sum_j gamma_ij z_j w_j^{sigma_i} ),

namely, with D_i = 1 + sum_j gamma_ij xi_j zeta_j^{sigma_i} and Psi = sum_i log D_i,

m_j = sum_i gamma_ij xi_j zeta_j^{sigma_i} / D_i, k_j = sum_i sigma_i gamma_ij xi_j zeta_j^{sigma_i} / D_i, log H(m,k) ~ Psi - sum_j m_j log xi_j - sum_j k_j log zeta_j

(d/2) log(2 pi) - (1/2) log det grad^2 Psi,

where d is the number of saddle coordinates and, with pi_ij = gamma_ij xi_j zeta_j^{sigma_i} / D_i and Q^i_{jl} = delta_{jl} pi_ij - pi_ij pi_il,

grad^2 Psi = sum_i [1; sigma_i] [1; sigma_i]' (x) Q^i .

Setting zeta_j = 1 recovers the size-free expansion exactly.

CAPS ARE CUMULATIVE. cache_erec sums over the states of cost AT MOST k_j, so this function does the same by default (CacheCostMode::AtMost). The shadow price eta_j = log zeta_j <= 0 obeys complementary slackness: a list whose unconstrained mean cost already meets its cap is SLACK, keeps zeta_j = 1, and drops out of the saddle, which then degenerates continuously to the size-free expansion; a list whose cap BINDS sits at eta_j < 0, and the states below the boundary decay geometrically with ratio zeta_j, contributing the amplitude factor 1/(1-zeta_j). CacheCostMode::Exact gives instead the constant resolving the cost exactly at k_j, the raw Laplace formula above with no such factor.

SIZE DIVERSITY IS REQUIRED. The Hessian integrand [1;sigma_i][1;sigma_i]' (x) Q^i has rank h, not 2h, so grad^2 Psi is nonsingular only if the sizes actually vary. This is not an artefact: with a single item size the cost of list j is sigma*m_j identically and the cap carries no information. That case is detected and answered exactly rather than passed to a singular saddle. If the sizes share a common divisor the cost lives on a sublattice; the sizes and caps are divided through by their gcd, which is an exact reduction and removes the corresponding lattice factor.

OCCUPANCY. The result's pij is the saddle occupancy pi_il = gamma_il xi_l zeta_l^{sigma_i} / D_i and k_mean its per-list cost. These are EXACT-COST quantities: the saddle conditions are sum_i pi_ij = m_j and sum_i sigma_i pi_ij = k_j, so k_mean equals the cap exactly on every binding list. Under cumulative caps the true mean cost is strictly below the cap; use cache_cost and cache_prob_erec for that.

ACCURACY. The expansion is O(1/n) at fixed occupancy. With a well-separated cap the observed error in log E is around 1e-2 at n = 200 and halves at each doubling of n. It degrades as a binding zeta_j approaches 1, i.e. in the transition between the binding and slack regimes, where the geometric resummation 1/(1-zeta_j) is no longer sharp; the result's zeta and binding report where the saddle sits, and relerr_est is the size-free O(1/n) baseline that does NOT cover that transition.

ARITHMETIC: the expansion is a Laplace approximation built out of logs, exps and a square root, so it is meaningless at exact arithmetic and is gated on has_transcendental. It is also an APPROXIMATION whatever the arithmetic – widening the type sharpens the saddle solve, never the O(1/n) model error. Use cache_erec when the exact constant is wanted.

Definition in file cache_spm_size.h.

Classes

Namespaces

Enumerations

Functions

Detailed Description