cache_xi_iter.h File Reference

Lagrange multipliers of a multi-list cache by the Gast-Van Houdt iteration. More...

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

Include dependency graph for cache_xi_iter.h:

Go to the source code of this file.

Namespaces
namespace	line
namespace	line::cache

Functions
template<class T>
std::vector< T >	line::cache::cache_xi_iter (const Matrix< T > &gamma, const std::vector< int > &m)
	Lagrange multipliers of a multi-list cache by the Gast-Van Houdt iteration.

Detailed Description

Lagrange multipliers of a multi-list cache by the Gast-Van Houdt iteration.

Templated port of matlab/src/api/cache/cache_xi_iter.m, cross-checked against jar/src/main/java/jline/api/cache/Cache_xi_iter.java (and its verbatim duplicate Cache_xi_bvh.java).

Writing pp(0,k) = 1 and pp(l,k) = gamma(k,l-1), the stationary occupancy of list l under the asymptotic independence approximation is

F_l(z_l) = sum_k z_l pp(l,k) / (n z_l pp(l,k) + a_l(k)), a_l(k) = n sum_{s != l} z_s pp(s,k),

which is increasing in z_l, so the capacity constraint F_l(z_l) = m(l)/n has a unique root. The outer loop is a Gauss-Seidel sweep over the lists, each inner solve a bracketed bisection (the bracket [0,1] when the unit point already overshoots, otherwise doubled from 1 until it does), refined by a fixed 50 halvings. Convergence of the sweep is declared when the multipliers move by less than 1e-12 relative.

ARITHMETIC: only field operations, but the answer is defined by two nested tolerances – a fixed 50-step bisection and a 1e-12 sweep test – so it is inexact by construction and is gated on transcendental arithmetic. Note in particular that the 50 halvings cap the achievable accuracy at about 1e-15 of the bracket regardless of the precision of T.

REFERENCE DEFECT (MATLAB): the third argument is declared as tmax and is assigned Inf when absent, but is never read in the body, so it has no effect. cache_spm passes its own xi0 warm start into that slot, meaning the warm start silently does nothing. The argument is not offered here.

Definition in file cache_xi_iter.h.