qbd_r.h File Reference

Quasi-birth-death processes: the rate matrix R, the fundamental matrix G, the caudal characteristic, and the stationary distribution. More...

#include <cstddef>
#include <vector>
#include "line/num/number.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 qbd_r.h:

Go to the source code of this file.

Classes
struct	line::mam::QbdFundMat< T >
	G and R together, as returned by qbd_fundmat. More...

Namespaces
namespace	line
namespace	line::mam

Functions
template<class T>
T	line::mam::qbd_R_residual (const Matrix< T > &B, const Matrix< T > &L, const Matrix< T > &F, const Matrix< T > &R)
	Residual of the defining equation of R, ||F + R L + R^2 B||_inf.
template<class T>
T	line::mam::qbd_G_residual (const Matrix< T > &B, const Matrix< T > &L, const Matrix< T > &F, const Matrix< T > &G)
	Residual of the defining equation of G, ||B + L G + F G^2||_inf.
template<class T>
Matrix< T >	line::mam::qbd_R (const Matrix< T > &B, const Matrix< T > &L, const Matrix< T > &F, unsigned iter_max, const T &tol)
	R by successive substitutions (qbd_R.m): iterate R <- -(F + R^2 B) L^-1.
template<class T>
Matrix< T >	line::mam::qbd_R (const Matrix< T > &B, const Matrix< T > &L, const Matrix< T > &F)
	qbd_R with the MATLAB defaults, 100000 iterations and tolerance 1e-12.
template<class T>
Matrix< T >	line::mam::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).
template<class T>
Matrix< T >	line::mam::qbd_R_logred (const Matrix< T > &B, const Matrix< T > &L, const Matrix< T > &F)
	qbd_R_logred with the MATLAB defaults, 100000 iterations and tolerance 1e-12.
template<class T>
QbdFundMat< T >	line::mam::qbd_fundmat (const Matrix< T > &B, const Matrix< T > &L, const Matrix< T > &F, unsigned iter_max, const T &tol)
	G and R by cyclic reduction (qbd_fundmat.m, the Bini-Meini logarithmic reduction on the raw level blocks).
template<class T>
QbdFundMat< T >	line::mam::qbd_fundmat (const Matrix< T > &B, const Matrix< T > &L, const Matrix< T > &F)
	qbd_fundmat with the MATLAB defaults, 50 iterations and tolerance 1e-14.
template<class T>
T	line::mam::qbd_caudal (const Matrix< T > &R, unsigned iter_max, const T &tol)
	Caudal characteristic eta = sp(R), the decay rate of the queue-length tail.
template<class T>
T	line::mam::qbd_caudal (const Matrix< T > &R)
	qbd_caudal with 10000 iterations and tolerance 1e-14.
template<class T>
Matrix< T >	line::mam::qbd_pi (const Matrix< T > &B, const Matrix< T > &Lbar, const Matrix< T > &R, std::size_t max_levels, const T &mass_tol)
	Stationary distribution of a QBD given R (QBD_pi.m, continuous-time branch, default boundary).
template<class T>
Matrix< T >	line::mam::qbd_pi (const Matrix< T > &B, const Matrix< T > &Lbar, const Matrix< T > &R)
	qbd_pi with the MATLAB-side defaults, 20000 levels and mass tolerance 1e-10.

Detailed Description

Quasi-birth-death processes: the rate matrix R, the fundamental matrix G, the caudal characteristic, and the stationary distribution.

Templated port of matlab/src/api/mam/qbd_R.m, qbd_R_logred.m, qbd_fundmat.m, and of the boundary solve of matlab/lib/thirdparty/smcsolver/QBD_pi.m and the caudal characteristic of QBD_Caudal.m. Cross-checked against jar/src/main/java/jline/api/mam/Qbd_R.java and Qbd_R_logred.java.

Block convention, level-independent QBD in continuous time:

Q = | Lbar  F     0     0    ... |
    | B     L     F     0    ... |
    | 0     B     L     F    ... |
    | ...                        |

with B the backward (downward) block, L the local block and F the forward (upward) block. R is the minimal non-negative solution of

F + R L + R^2 B = 0,

which is the equation A0 + R A1 + R^2 A2 = 0 with A0 = F, A1 = L, A2 = B. G is the minimal non-negative solution of B + L G + F G^2 = 0.

ARITHMETIC. Three routines here compute R or G by a fixed-point iteration driven to a tolerance – successive substitution, logarithmic reduction and cyclic reduction – and one (qbd_caudal) brackets a spectral radius. None of them terminates in a finite number of field operations, so the value they return is an approximation no matter how the arithmetic is carried out; running them at exact rational arithmetic would produce a rational number with a denominator doubling at every cyclic-reduction step and still not the exact R. They are therefore gated on num_traits<T>::has_transcendental, which admits double and Real<D> and rejects Rational at compile time.

Everything downstream of R is a finite rational computation and is left un-gated: qbd_R_residual, qbd_pi (a null-vector solve plus a geometric tail) and the moment formulas in qbd_mapmap1.h all instantiate at Rational. That split is the point of the port – given R to whatever accuracy, the boundary probabilities and the queue-length moments carry no additional error.

Definition in file qbd_r.h.