Port of solver_ag.m: the RCAT (Reversed Compound Agent Theorem) analyzers, reached by methods 'inap', 'inapplus', 'inapinf' and 'exact'. More...

#include <algorithm>
#include <cmath>
#include <cstddef>
#include <limits>
#include <memory>
#include <string>
#include <utility>
#include <vector>
#include "line/api/mam/map_moment.h"
#include "line/api/mam/mmap_lambda.h"
#include "line/api/mam/qbd_r.h"
#include "line/api/mc/ctmc_solve.h"
#include "line/lang/distribution.h"
#include "line/lang/qn/network_struct.h"
#include "line/num/number.h"
#include "line/solvers/ag/ag_exec.h"
#include "line/solvers/ag/ag_types.h"
#include "line/solvers/mam/mam_types.h"
#include "line/util/error.h"
#include "line/util/linalg.h"
#include "line/util/lu.h"
#include "line/util/matrix.h"

Include dependency graph for solver_ag.h:

Classes
struct	line::ag::AgResult< T >
	What the RCAT analyzer returns beyond the metrics. More...

Namespaces
namespace	line
namespace	line::ag

Functions
bool	line::ag::rcat_supports_process (lang::ProcessType t)
	The process types the RCAT construction can give a phase dimension to.
template<class T>
AgResult< T >	line::ag::solver_ag (const qn::NetworkStruct< T > &L, const AgOptions &opt, std::size_t max_states=0)
	Port of solver_ag.m.
template<class T>
Matrix< T >	line::ag::kron (const Matrix< T > &A, const Matrix< T > &B)
	Kronecker product.
template<class T>
Matrix< T >	line::ag::krons (const Matrix< T > &A, const Matrix< T > &B)
	Kronecker sum, MATLAB's krons: kron(A, I_nb) + kron(I_na, B).
template<class T>
Matrix< T >	line::ag::qbd_R_logred (const Matrix< T > &B, const Matrix< T > &L, const Matrix< T > &F, unsigned iter_max, const T &tol)
	R by logarithmic reduction (qbd_R_logred.m).

Detailed Description

Port of solver_ag.m: the RCAT (Reversed Compound Agent Theorem) analyzers, reached by methods 'inap', 'inapplus', 'inapinf' and 'exact'.

THE METHOD. Each (station, class) pair that carries jobs becomes an isolated CTMC, and the pairs are coupled only through the REVERSED RATES x_l of the synchronizing actions. A component is a QBD whose LEVEL is the queue length and whose PHASE is the pair (arrival phase, service phase), laid out in the Kronecker order of qbd_mapmap1.h: an arrival moves the level up carrying kron(D1^a, I), a service completion moves it down carrying kron(I, D1^s), the busy levels evolve under krons(D0^a, D0^s) and level zero under kron(D0^a, I), because no server is running there. With exponential processes every block is 1 x 1 and the QBD collapses to the scalar birth-death chain this analyzer built before, entry for entry. A departure from one component is an active transition there and a passive one at the destination; RCAT says that if the reversed rate of every active label is state-independent, the joint chain has a product form whose factors are the isolated components solved with the passive rates set to those x_l. INAP is the fixed point that looks for such an x: solve the components, re-estimate each x_l from the resulting marginals, repeat.

THESE ARE APPROXIMATIONS, and the reference is explicit about it. The reversed rate is state-independent only for genuinely product-form models; on everything else INAP converges to an x that is merely a good average, and the marginals it returns are not the model's. The 'inapinf' variant reports the RCAT residual of Remark 2, max_l ||pi (x_l I - T_l)||, which is zero exactly when the product form is real, and it is exposed here as rcat_residual for the same reason: it is the only honest indication of how far off the answer is. Nothing in this header should be compared against an exact solver at a tolerance that pretends otherwise.

THE THREE VARIANTS differ only in how x_l is re-estimated and how the open components are solved: inap x_l = mean over the support of the state-wise reversed rate (pi A_l)_j / pi_j, which on a birth-death component is the entrywise mean of A_l(i,j) pi(i)/pi(j) term for term inapplus x_l = sum over the support of A_l(i,j) pi(i), the rate-conserving estimator, which INAP also switches to on any component that is not a birth-death chain (a catastrophe or batch removal reaches beyond the neighbouring LEVEL, and the mean-of-ratios estimator is meaningless there) and on any component with more than one phase per level, where the same failure appears inapinf x_l from the closed-form geometric tail, with each OPEN component solved on its infinite state space by the scalar QBD root instead of being truncated at maxStates (Marin, Rota Bulo and Balsamo, MASCOTS 2012)

TWO REFERENCE QUIRKS THAT LOOK LIKE BUGS AND ARE HARMLESS, both worth knowing before editing. First, compute_equilibrium subtracts unscaled row-sum diagonals while adding x(c)-scaled off-diagonal blocks, which is inconsistent; it does not matter because ctmc_makeinfgen discards the diagonal outright and rebuilds it from the row sums. Second, and for the same reason, the self-service term L(n,n) = mu * P(self) that build_local_rates writes on the DIAGONAL is discarded too, so self-routing at a station has no effect on the answer. Both are reproduced rather than corrected: correcting either would change every number this analyzer returns.

NOT PORTED, AND WHY. The reference's self-looping-class override reads sn.isslc, which NetworkStruct does not carry. MATLAB guards that block with isfield(sn,'isslc'), so a struct without the field skips it and the port takes the same path; a model that genuinely has self-looping classes would differ, and there is no way to detect one here without inventing the concept.

ARITHMETIC. The fixed point stops on a tolerance and the QBD root takes a square root, so the whole body is gated on transcendental arithmetic, as solver_mam_basic.h and solver_mam_ldqbd.h are.

Definition in file solver_ag.h.

Classes

Namespaces

Functions

Detailed Description