etaqa.h File Reference

ETAQA: the aggregated stationary vector and the queue-length moments of an M/G/1-type and of a GI/M/1-type Markov chain. More...

#include <algorithm>
#include <cmath>
#include <cstddef>
#include <string>
#include <vector>
#include "line/lib/smc/mg1.h"
#include "line/util/eig.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 etaqa.h:

Go to the source code of this file.

Namespaces
namespace	line
namespace	line::smc

Functions
Matrix< double >	line::smc::mg1_g_etaqa (const Matrix< double > &A)
	G of an M/G/1-type chain, uniformized first.
std::vector< double >	line::smc::mg1_pi_etaqa (const Matrix< double > &Bin, const Matrix< double > &Ain, const Matrix< double > &G, const Matrix< double > &C0in=Matrix< double >())
	Aggregated stationary vector [pi0, pi1, pi2+pi3+...] of an M/G/1-type chain.
double	line::smc::mg1_qlen_etaqa (const Matrix< double > &Bin, const Matrix< double > &Ain, const std::vector< double > &pi, std::size_t n, const Matrix< double > &C0in=Matrix< double >())
	n-th moment of the level (the queue length) of an M/G/1-type chain from the ETAQA aggregates.
Matrix< double >	line::smc::gim1_r_etaqa (const Matrix< double > &A)
	R of a GI/M/1-type chain, uniformized first.
std::vector< double >	line::smc::gim1_pi_etaqa (const Matrix< double > &Bin, const Matrix< double > &Ain, const Matrix< double > &R, const Matrix< double > &B0in=Matrix< double >())
	Aggregated stationary vector [pi0, pi1, pi2+pi3+...] of a GI/M/1-type chain.
double	line::smc::gim1_qlen_etaqa (const Matrix< double > &Bin, const Matrix< double > &Ain, const Matrix< double > &R, const std::vector< double > &pi, std::size_t n, const Matrix< double > &B0in=Matrix< double >())
	n-th moment of the level of a GI/M/1-type chain from the ETAQA aggregates.

Detailed Description

ETAQA: the aggregated stationary vector and the queue-length moments of an M/G/1-type and of a GI/M/1-type Markov chain.

Port of MAMSolver's MG1_G_ETAQA.m, MG1_pi_ETAQA.m, MG1_qlen_ETAQA.m, GIM1_R_ETAQA.m, GIM1_pi_ETAQA.m and GIM1_qlen_ETAQA.m (matlab/lib/thirdparty/MAMSolver).

WHAT ETAQA IS. A structured infinite chain has a stationary vector pi = (pi_0, pi_1, pi_2, ...) with one block per level. Matrix-geometric methods compute every block; ETAQA instead solves a FINITE linear system for exactly three aggregates – pi_0, pi_1 and pi* = sum_{j>=2} pi_j – by replacing the infinitely many balance equations for levels 2 and above by their sum. The aggregate system is (mb + 2m) x (mb + 2m) and is EXACT: no level is truncated and no tail is fitted, which is what separates ETAQA from a level-truncated direct solve. Riska and Smirni, Perform. Eval. 54(2), 2003.

The moments come the same way. ..._qlen_ETAQA never forms pi_j either: it propagates the vectors r^(k) = sum_{j>=2} j^k pi_j through a recurrence whose left-hand side is one fixed m x m system, so the n-th moment costs n solves of the same size regardless of how heavy the tail is.

WHY THE LAST COLUMN IS ALWAYS DROPPED. The aggregate balance equations are linearly dependent, exactly as the balance equations of any generator are, so the system is rank deficient by one and the normalization e^T pi = 1 supplies the missing equation. The M/G/1 side finds WHICH column to drop with a rank test (a redundant one exists but is not always the last), the GI/M/1 side simply drops the final column. Both then prepend the column of ones.

DOUBLE ONLY: see the note in lib/smc/mg1.h. The rank test is an SVD and the fundamental matrices come from LAPACK-backed and FFT-backed iterations.

REFERENCE DEFECTS REPRODUCED VERBATIM, because these functions are the numerical reference for the JAR and Python ports and a silent repair here would be a divergence nobody could see:

1. MG1_G_ETAQA tests whether its input is a DTMC by setting a flag named isdicrete and reading one named isdiscrete, so the flag never changes and the continuous-to-discrete uniformization ALWAYS runs. For the generators LINE passes it that is the correct branch anyway; a genuine stochastic input would be divided by -min(diag(A1)), which is <= 0.
2. MG1_qlen_ETAQA builds F0j from block dega down to block 2 but indexes it from 1, so F0j(:,(j-1)*m+1:j*m) is the tail sum starting at j+1 and not at j. The moment is therefore the reference's moment, off-by-one index and all.
3. GIM1_qlen_ETAQA initializes leftr_part1 = A(3), a SCALAR read at linear index 3 of the stacked A rather than the third block, and MATLAB then broadcasts it over the m x m accumulator. The port reproduces both the value and the broadcast, including the case where the loop that would turn it into a matrix does not run and the scalar survives as a vector.

Definition in file etaqa.h.