ctmc_gth.h File Reference

Grassmann-Taksar-Heyman (GTH) elimination for the stationary vector, and the limit matrix J = lim expm(Q t) of any finite chain built on it. More...

#include <algorithm>
#include <cmath>
#include <cstddef>
#include <string>
#include <vector>
#include "line/api/mc/stronglyconncomp.h"
#include "line/num/number.h"
#include "line/util/error.h"
#include "line/util/lu.h"
#include "line/util/matrix.h"

Include dependency graph for ctmc_gth.h:

Go to the source code of this file.

Classes
struct	line::mc::GthResult< T >

Namespaces
namespace	line
	Conservation laws of a layered queueing network, enumerated from its structure.
namespace	line::mc

Functions
template<class T>
GthResult< T >	line::mc::ctmc_gth_flag (const Matrix< T > &Q)
	Stationary vector of a CTMC by GTH elimination, with a flag.
template<class T>
std::vector< T >	line::mc::ctmc_gth (const Matrix< T > &Q)
	Stationary vector by GTH; throws InputError on several closed classes.
template<class T>
std::vector< T >	line::mc::dtmc_gth (const Matrix< T > &P)
	Stationary vector of a DTMC by GTH; self-loops are not read.
template<class T>
Matrix< T >	line::mc::ctmc_cesaro (const Matrix< T > &Q)
	Limit matrix J = lim expm(Q t) of any finite CTMC (Agaev-Chebotarev 2000).
template<class T>
Matrix< T >	line::mc::dtmc_cesaro (const Matrix< T > &P)
	Cesaro limit of P^k for any finite DTMC; equals ctmc_cesaro(P - I).

Detailed Description

Grassmann-Taksar-Heyman (GTH) elimination for the stationary vector, and the limit matrix J = lim expm(Q t) of any finite chain built on it.

Templated port of matlab/src/api/mc/ctmc_gth.m, dtmc_gth.m, ctmc_cesaro.m, dtmc_cesaro.m and private/gth_irreducible.m; JAR twins jline.api.mc.Ctmc_gth and Ctmc_cesaro, Python twin line_solver.api.mc.gth.

GTH censors the states from last to first, a_ij += a_ik a_kj / s_k with the pivot s_k = sum_{j<k} a_kj taken from the off-diagonal rates, never from the diagonal, and back-substitutes x_k = sum_{i<k} x_i a_ik / s_k. There is no subtraction, so every probability keeps small RELATIVE error, also on stiff and nearly completely decomposable chains. Only the off-diagonal entries are read, so dtmc_gth(P) = ctmc_gth(P) and periodic chains are fine. GTH uses only +, * and /, so the exact instantiation returns the exact rational vector. (Grassmann, Taksar, Heyman, Oper. Res. 33(5):1107-1116, 1985.)

ctmc_cesaro gives every closed class C_k its GTH vector pi_k and every transient state i the row J(i, C_k) = H(i,k) pi_k, with H = (-Q_TT)^{-1} Q_{T,C} 1 the absorption probabilities. J is the matrix of maximum out-forests of the transition digraph (Agaev and Chebotarev, Autom. Remote Control 61(9):1424-1450, 2000): stochastic, idempotent, Q J = J Q = 0, and for a DTMC the Cesaro limit of P^k whatever the periodicity.

Definition in file ctmc_gth.h.