ldqbd_censor.h File Reference

Stationary distribution of a chain of connected LDQBDs by successive censoring. More...

#include <cstddef>
#include <map>
#include <string>
#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 ldqbd_censor.h:

Go to the source code of this file.

Classes
struct	line::mam::LdqbdCensorResult< T >
	Stationary distribution of a chain of connected LDQBDs. More...
struct	line::mam::ldqbd_censor_detail::Factor< T >
	Block-tridiagonal LU of M = -Q_kk: S on the diagonal, G below, U above. More...

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

Functions
template<class T>
T	line::mam::ldqbd_censor_detail::zero ()
template<class T>
double	line::mam::ldqbd_censor_detail::norm1 (const Matrix< T > &A)
template<class T>
Matrix< T >	line::mam::ldqbd_censor_detail::checked_inverse (const Matrix< T > &D, std::size_t level, std::size_t set)
	Inverse of a Schur complement, refusing a singular one.
template<class T>
Matrix< T >	line::mam::ldqbd_censor_detail::block (const Matrix< T > &M, std::size_t r0, std::size_t nr, std::size_t c0, std::size_t nc)
template<class T>
void	line::mam::ldqbd_censor_detail::check (const Matrix< T > &M, const std::vector< std::size_t > &P, std::size_t set)
	Throws LINE:unsupported:Structure if M is not block tridiagonal by level.
template<class T>
LdqbdCensorResult< T >	line::mam::ldqbd_censor (const Matrix< T > &Q, const std::vector< std::vector< std::size_t > > &phases, double tol=1e-10)
	Stationary distribution of a chain of connected LDQBDs (ldqbd_censor.m).

Detailed Description

Stationary distribution of a chain of connected LDQBDs by successive censoring.

Templated port of matlab/src/api/mam/ldqbd_censor.m, implementing the algorithm of N. Baer, A. Al Hanbali, R. J. Boucherie, J. C. W. van Ommeren, "A successive censoring algorithm for a system of connected LDQBD-processes", Annals of Operations Research 310:389-410, 2022.

The state space is split into S sets, each a level-dependent QBD on its own; set s has levels 1..L_s and level l of set s has phases[s][l] phases. States are ordered by (set, level, phase). Transitions between sets are arbitrary. Sets 1..S-1 are censored out in turn,

Q^{k+1}_{ij} = Q^k_{ij} + Q^k_{ik} (-Q^k_{kk})^{-1} Q^k_{kj},   i, j > k,

the last LDQBD is solved by level reduction (Gaver), and the vector is expanded back with pi_k = (sum_{i>k} pi_i Q^k_{ik}) (-Q^k_{kk})^{-1}. Each transient LDQBD is factored once by block-tridiagonal LU (block Thomas, S_l = D_l - W_l S_{l-1}^{-1} U_{l-1}); its inverse is never formed.

STRUCTURE. The method applies exactly when every censored diagonal block Q^k_{kk} is block tridiagonal by level. The update is a sum of nonnegative terms, so the numerical pattern equals the structural one and the check is made directly on Q^k_{kk}; a failure raises LINE:unsupported:Structure (another order of the sets may succeed, Remark 2 of the paper).

ARITHMETIC. The algorithm is finite (no tolerance, no iteration), so it instantiates at Rational and returns the exact stationary law. Exact T raises NumericError on an exactly singular Schur complement; inexact T also raises when the 1-norm reciprocal condition of a block is below machine epsilon, matching the MATLAB rcond test. The row-sum check is exact at Rational and relative (tol) otherwise.

Definition in file ldqbd_censor.h.