Computing the exponential of large block-triangular block-Toeplitz matrices encountered in fluid queues

DOI10.1016/J.LAA.2015.03.035MaRDI QIDQ281989zbMATH OpenOpenAlexFDO

Authors Guy Latouche, B. Meini, Dario A. Bini, S. Dendievel

Publication date 11 May 2016

Published in Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1502.07533

zbMATH Keywords

circulant matrixErlang approximationfluid queueMarkov generatormatrix exponentialToeplitz matrix

Mathematics Subject Classification ID

Matrix exponential and similar functions of matrices (15A16) Toeplitz, Cauchy, and related matrices (15B05) Computational methods in Markov chains (60J22) Numerical computation of matrix exponential and similar matrix functions (65F60)

Abstract: The Erlangian approximation of Markovian fluid queues leads to the problem of computing the matrix exponential of a subgenerator having a block-triangular, block-Toeplitz structure. To this end, we propose some algorithms which exploit the Toeplitz structure and the properties of generators. Such algorithms allow to compute the exponential of very large matrices, which would otherwise be untreatable with standard methods. We also prove interesting decay properties of the exponential of a generator having a block-triangular, block-Toeplitz structure.

Recommendations

• Exploiting the Toeplitz structure in certain queueing problems
• Fast computation of the matrix exponential for a Toeplitz matrix
• On the exponential of semi-infinite quasi-Toeplitz matrices
• A numerical study of large sparse matrix exponentials arising in Markov chains.
• Matrix structures in queuing models

Cites work

• Aggressively truncated Taylor series method for accurate computation of exponentials of essentially nonnegative matrices
• ALGORITHMS FOR RETURN PROBABILITIES FOR STOCHASTIC FLUID FLOWS
• Approximations for time-dependent distributions in Markovian fluid models
• Computing exponentials of essentially non-negative matrices entrywise to high relative accuracy
• Decay properties for functions of matrices over \(C^\ast\)-algebras
• Decay properties of spectral projectors with applications to electronic structure
• Derivatives of the matrix exponential and their computation
• Entrywise relative perturbation bounds for exponentials of essentially non-negative matrices
• Erlangian Approximations for Finite-Horizon Ruin Probabilities
• Erlangized Fluid Queues with Application To Uncontrolled Fire Perimeter
• Functions of Matrices
• scientific article; zbMATH DE number 691245 (Why is no real title available?)
• Numerical Methods for Structured Markov Chains
• Numerical solution of algebraic Riccati equations.
• Parallel Solution of Certain Toeplitz Linear Systems
• Phase-type Approximations to Finite-time Ruin Probabilities in the Sparre-Andersen and Stationary Renewal Risk Models
• Shift-invert Arnoldi approximation to the Toeplitz matrix exponential
• Shift-invert Lanczos method for the symmetric positive semidefinite Toeplitz matrix exponential.
• The complex step approximation to the Fréchet derivative of a matrix function
• The Erlangization method for Markovian fluid flows
• The scaling and squaring method for the matrix exponential revisited

Cited in

(18)

• Circulant preconditioners for analytic functions of Toeplitz matrices
• On the exponential of semi-infinite quasi-Toeplitz matrices
• Optimal preconditioners for systems defined by functions of Toeplitz matrices
• Non-Toeplitz decay bounds for inverses of Hermitian positive definite tridiagonal matrices
• The exponential of quasi block-Toeplitz matrices
• On the inversion of the block double-structured and of the triple-structured Toeplitz matrices and on the corresponding reflection coefficients
• On barrier option pricing by Erlangization in a regime-switching model with jumps
• Shift techniques for quasi-birth and death processes: canonical factorizations and matrix equations
• Decay bounds for functions of Hermitian matrices with banded or Kronecker structure
• Localization in matrix computations: theory and applications
• Fast computation of the matrix exponential for a Toeplitz matrix
• On functions of quasi-Toeplitz matrices
• Divide-and-conquer methods for functions of matrices with banded or hierarchical low-rank structure
• Approximations for time-dependent distributions in Markovian fluid models
• Efficient preconditioning for time fractional diffusion inverse source problems
• A series expansion formula of the scale matrix with applications in CUSUM analysis
• Relative error-based time-limited \(\mathcal{H}_2\) model order reduction via oblique projection
• A parallel-in-time iterative algorithm for Volterra partial integro-differential problems with weakly singular kernel

Describes a project that uses

Uses Software

• MATLAB expm
• mftoolbox

This page was built for publication: Computing the exponential of large block-triangular block-Toeplitz matrices encountered in fluid queues

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q281989)