cache_xi_fp.h File Reference

Lagrange multipliers of a multi-list cache by fixed-point 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_fp.h:

Go to the source code of this file.

Classes
struct	line::cache::CacheXiFpResult< T >
	Return value of cache_xi_fp, mirroring [xi,pi0,pij,it]. More...

Namespaces
namespace	line
namespace	line::cache

Functions
template<class T>
CacheXiFpResult< T >	line::cache::cache_xi_fp (const Matrix< T > &gamma, const std::vector< int > &m)
	Lagrange multipliers of a multi-list cache by fixed-point iteration.

Detailed Description

Lagrange multipliers of a multi-list cache by fixed-point iteration.

Templated port of matlab/src/api/cache/cache_xi_fp.m, cross-checked against jar/src/main/java/jline/api/cache/Cache_xi_fp.java.

The asymptotic (large-cache) form of the list occupancy distribution is

pij(k,l) = gamma(k,l) xi(l) / (1 + sum_s gamma(k,s) xi(s)), pi0(k) = 1 - sum_l pij(k,l),

and the multipliers xi are fixed by the capacity constraints, which in this decoupled form read xi(l) = m(l) / sum_k pi0(k) gamma(k,l). Alternating the two updates from pi0 = 1/(h+1) is the iteration below; it stops when the relative change of pi0 falls under 1e-14 in the 1-norm.

ARITHMETIC: every update is a field operation, but the iteration is stopped by a tolerance and the fixed point is not reached in finitely many exact steps, so the algorithm is inexact by nature. It is gated on transcendental arithmetic rather than offered at exact arithmetic, where a "1e-14" cutoff would be a rounding-free computation of a rounded answer.

REFERENCE DEFECT (both codebases): the optional initial-xi argument is inert. MATLAB writes xi=zeros(1,h); before testing nargin<3, discarding the caller's vector, and in any case the first statement of the loop recomputes xi from pi0, so no initial xi can influence the result. The JAR has the same structure. The argument is therefore not offered here.

Definition in file cache_xi_fp.h.