Efficient cyclic reduction for quasi-birth-death problems with rank structured blocks

DOI10.1016/j.apnum.2016.06.014zbMath1372.65122arXiv1601.00861OpenAlexW2478938119MaRDI QIDQ2400781

Stefano Massei, Dario Andrea Bini, Leonardo Robol

Publication date: 30 August 2017

Published in: Applied Numerical Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

algorithmMarkov chainsnumerical experimentsmatrix equationscyclic reductionquasiseparable matricesdouble QBD processesH matricestridiagonal block Toeplitz systems

Mathematics Subject Classification ID

Computational methods for sparse matrices (65F50) Matrix equations and identities (15A24) Numerical analysis or methods applied to Markov chains (65C40) Toeplitz, Cauchy, and related matrices (15B05)

Related Items

Solving Rank-Structured Sylvester and Lyapunov Equations, Low-rank updates and divide-and-conquer methods for quadratic matrix equations, Quasi-Toeplitz matrix arithmetic: a MATLAB toolbox, hm-toolbox: MATLAB Software for HODLR and HSS Matrices, Rational Krylov and ADI iteration for infinite size quasi-Toeplitz matrix equations, Computing performability measures in Markov chains by means of matrix functions

Uses Software

• H2Lib

Cites Work

• Unnamed Item
• Unnamed Item
• The cyclic reduction algorithm: From Poisson equation to stochastic processes and beyond. In memoriam of Gene H. Golub
• Construction and arithmetics of \(\mathcal H\)-matrices
• Introduction to hierarchical matrices with applications.
• Convergence Analysis of the Latouche--Ramaswami Algorithm for Null Recurrent Quasi-Birth-Death Processes
• A Compressed Cyclic Reduction for QBD processes with Low-Rank Upper and Lower Transitions
• On the Numerical Rank of the Off-Diagonal Blocks of Schur Complements of Discretized Elliptic PDEs
• Tail Decay Rates in Double QBD Processes and Related Reflected Random Walks
• Effective Methods for Solving Banded Toeplitz Systems
• Matrix-geometric invariant measures for G/M/l type Markov chains
• Networks of Waiting Lines
• Numerical Methods for Structured Markov Chains
• A Fast Direct Solution of Poisson's Equation Using Fourier Analysis
• On Direct Methods for Solving Poisson’s Equations