cache_rmf_lna.h File Reference

Stationary covariance of a RANDOM(m) cache occupancy, under the LNA. More...

#include <algorithm>
#include <cmath>
#include <cstddef>
#include <limits>
#include <vector>
#include "line/api/cache/cache_miss_rmf.h"
#include "line/util/eig.h"
#include "line/util/error.h"
#include "line/util/matrix.h"
#include "line/util/sylvester.h"

Include dependency graph for cache_rmf_lna.h:

Go to the source code of this file.

Namespaces
namespace	line
namespace	line::cache

Functions
Matrix< double >	line::cache::cache_rmf_lna (const std::vector< double > &x, const std::vector< double > &p, const std::vector< double > &m, std::size_t n, std::size_t h, std::size_t dim)
	Stationary covariance of a RANDOM(m) cache occupancy, under the LNA.

Detailed Description

Stationary covariance of a RANDOM(m) cache occupancy, under the LNA.

Port of cache_rmf_lna in python/line_solver/api/cache/rmf.py, itself a twin of the MATLAB local rmf_lna_covariance. It solves the Lyapunov equation

F'(x) W + W F'(x)' + Q(x) = 0

with exactly the jacobian and noise_matrix that cache_miss_rmf.h already uses for the 1/N mean correction, so the mean and the covariance linearise about the IDENTICAL drift. Reusing those two rather than restating them is deliberate: the reference's rmf_jacobian is documented there as NOT being the derivative of rmf_drift at every entry, and a second transcription would silently pick the other one.

THE SUBSPACE IS THE POINT, AND THE REASON THE SOLVE IS POSSIBLE AT ALL. The Jacobian is singular twice over, because a RANDOM(m) cache conserves two things: every item is in exactly one list (sum_k x[i,k] = 1) and every list holds exactly its capacity (sum_i x[i,k] = m[k]). Every jump is a SWAP, (e_i - e_j) tensor (e_{k+1} - e_k), so the fluctuation lives on the tensor product of the zero-sum ITEM space with the zero-sum LIST space – the double-centred subspace, of dimension (n-1) * h. Restricting to an orthonormal basis of it is EXACT, not a regularization, and it is what makes the covariance of a deterministic total come out as zero rather than as whatever a pseudo-inverse would have produced.

A fixed point that is not exponentially stable ON THAT SUBSPACE has no stationary covariance, and is refused rather than answered.

ARITHMETIC: double. The eigenvalue test and the Lyapunov solve are both floating point.

Definition in file cache_rmf_lna.h.