cache_rmf_lna.h

Go to the documentation of this file.

/*
 * Copyright (c) 2012-2026, QORE Lab, Imperial College London
 * All rights reserved.
 */
#ifndef LINE_API_CACHE_CACHE_RMF_LNA_H
#define LINE_API_CACHE_CACHE_RMF_LNA_H
 
/**
 * @file
 * @ingroup api_cache
 * 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.
 */
 
#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"
 
namespace line {
namespace cache {
 
/**
 * @brief Stationary covariance of a RANDOM(m) cache occupancy, under the LNA.
 *
 * The computation lives in `rmf_detail::lna_covariance` (cache_miss_rmf.h),
 * where `cache_miss_rmf` also reads it for its `Wcov` output; this entry point
 * keeps the standalone name.
 *
 * @param x   the fluid fixed point, flattened item-major (`i + k*n`)
 * @param p   per-item popularities
 * @param m   per-list capacities
 * @param n   number of items
 * @param h   number of cache lists
 * @return    (dim x dim) stationary covariance, symmetric
 */
inline Matrix<double> 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) {
    return rmf_detail::lna_covariance(x, p, m, n, h, dim);
}
 
}  // namespace cache
}  // namespace line
 
#endif  // LINE_API_CACHE_CACHE_RMF_LNA_H