zbMATH — the first resource for mathematics

Efficient cyclic reduction for quasi-birth-death problems with rank structured blocks. (English) Zbl 1372.65122
Summary: We provide effective algorithms for solving block tridiagonal block Toeplitz systems with \(m \times m\) quasiseparable blocks, as well as quadratic matrix equations with \(m \times m\) quasiseparable coefficients, based on cyclic reduction and on the technology of rank-structured matrices. The algorithms rely on the exponential decay of the singular values of the off-diagonal submatrices generated by cyclic reduction. We provide a formal proof of this decay in the Markovian framework. The results of the numerical experiments that we report confirm a significant speed up over the general algorithms, already starting with the moderately small size \(m \approx 10^2\).

65F30 Other matrix algorithms (MSC2010)
65F50 Computational methods for sparse matrices
15B05 Toeplitz, Cauchy, and related matrices
65C40 Numerical analysis or methods applied to Markov chains
15A24 Matrix equations and identities
Full Text: DOI
[1] Bini, D. A.; Favati, P.; Meini, B., A compressed cyclic reduction for QBD processes with low-rank upper and lower transitions, (Matrix-Analytic Methods in Stochastic Models, (2013), Springer), 25-40 · Zbl 1280.60045
[2] Bini, D. A.; Latouche, G.; Meini, B., Numerical methods for structured Markov chains, (2005), Oxford University Press · Zbl 1076.60002
[3] Bini, D. A.; Meini, B., Effective methods for solving banded Toeplitz systems, SIAM J. Matrix Anal. Appl., 20, 700-719, (1999) · Zbl 0930.65015
[4] Bini, D. A.; Meini, B., The cyclic reduction algorithm: from Poisson equation to stochastic processes and beyond, Numer. Algorithms, 51, 23-60, (2009) · Zbl 1170.65021
[5] Börm, S., H2lib, (2015), Available from GitHub at
[6] Börm, S.; Grasedyck, L.; Hackbusch, W., Hierarchical matrices, Lect. Notes, vol. 21, 2003, (2003)
[7] Börm, S.; Grasedyck, L.; Hackbusch, W., Introduction to hierarchical matrices with applications, Eng. Anal. Bound. Elem., 27, 405-422, (2003) · Zbl 1035.65042
[8] Buzbee, B. L.; Golub, G. H.; Nielson, C. W., On direct methods for solving Poisson’s equations, SIAM J. Numer. Anal., 7, 627-656, (1970) · Zbl 0217.52902
[9] Chandrasekaran, S.; Dewilde, P.; Gu, M.; Somasunderam, N., On the numerical rank of the off-diagonal blocks of Schur complements of discretized elliptic pdes, SIAM J. Matrix Anal. Appl., 31, 2261-2290, (2010) · Zbl 1209.65032
[10] Gail, H.; Hantler, S.; Taylor, B., Matrix-geometric invariant measures for g/m/l type Markov chains, Commun. Stat., Stoch. Models, 14, 537-569, (1998) · Zbl 0913.60085
[11] Grasedyck, L.; Hackbusch, W., Construction and arithmetics of h-matrices, Computing, 70, 295-334, (2003) · Zbl 1030.65033
[12] Guo, C. H., Convergence analysis of the latouche-ramaswami algorithm for null recurrent quasi-birth-death processes, SIAM J. Matrix Anal. Appl., 23, 744-760, (2002) · Zbl 1005.65014
[13] Henrici, P., Applied and computational complex analysis. vol. 1, Wiley Classics Library, (1988), John Wiley & Sons, Inc. New York, Power series—integration—conformal mapping—location of zeros, Reprint of the 1974 original, A Wiley-Interscience Publication
[14] Hockney, R. W., A fast direct solution of Poisson’s equation using Fourier analysis, J. ACM, 12, 95-113, (1965) · Zbl 0139.10902
[15] Jackson, J. R., Networks of waiting lines, Oper. Res., 5, 518-521, (1957) · Zbl 1414.90067
[16] Massei, S.; Robol, L., H2lib’s MATLAB bindings, (2015), Available from GitHub at
[17] Miyazawa, M., Tail decay rates in double QBD processes and related reflected random walks, Math. Oper. Res., 34, 547-575, (2009) · Zbl 1213.60151
[18] Pérez, J. F.; Van Houdt, B., Quasi-birth-and-death processes with restricted transitions and its applications, Perform. Eval., 68, 126-141, (2011)
[19] Vandebril, R.; Van Barel, M.; Mastronardi, N., Matrix computations and semiseparable matrices. linear systems, vol. 1, (2008), Johns Hopkins University Press Baltimore, MD · Zbl 1141.65019
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.