A shifted cyclic reduction algorithm for quasi-birth-death problems

DOI10.1137/S0895479800371955MaRDI QIDQ2784374zbMATH OpenFDO

Authors Chao He, B. Meini, N. H. Rhee

Publication date 23 April 2002

Published in SIAM Journal on Matrix Analysis and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/S0895479800371955

zbMATH Keywords

algorithmconditioningconvergencecyclic reductionMarkov chainsnumerical examplesquadratic matrix equationsquasi-birth-death processesstochastic matrix

Mathematics Subject Classification ID

Matrix equations and identities (15A24) Stochastic matrices (15B51) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Branching processes (Galton-Watson, birth-and-death, etc.) (60J80) Numerical computation of matrix norms, conditioning, scaling (65F35)

Review text

The authors are interested in a solution \(G\) of the matrix equation \(G=A_0+A_1G+A_2G^2\), where the matrices \(A_i, i=0,1,2,\) are nonnegative and \(A_0+A_1+A_2\) is stochastic, that plays an important role in the study of quasi-birth-death processes (QBDs). A shifted cyclic reduction algorithm is presented. The authors show that the speed of convergence of their modification of the algorithm is always faster than that of the original cyclic reduction. The numerical results of the tests which show that the shifted cyclic reduction algorithm is fast and numerically accurate conclude the paper. NEWLINENEWLINENEWLINEThe paper is organized as follows. In Section 2 the cyclic reduction algorithm for QBDs is recalled. In Section 3 the shifting technique is applied and it is shown how the solutions of the shifted matrix equation are related to the solution of the original one. In Section 4 the convergence properties of the cyclic reduction algorithm applied to the shifted matrix equation is analyzed. In Section 5 the conditioning of the two matrix equations is studied. Finally, in Section 6 some numerical results are presented.

Recommendations

• Comments on a Shifted Cyclic Reduction Algorithm for Quasi-Birth-Death Problems
• ON LATOUCHE–RAMASWAMI'S LOGARITHMIC REDUCTION ALGORITHM FOR QUASI-BIRTH-AND-DEATH PROCESSES
• Shift Techniques and Canonical Factorizations in the Solution of M/G/1-Type Markov Chains
• A logarithmic reduction algorithm for quasi-birth-death processes
• On quadratic matrix equations with infinite size coefficients encountered in QBD stochastic processes.

Cited in

(28)

• Improved cyclic reduction for solving queueing problems
• Non-skip-free M/G/1-type Markov chains and Laurent matrix power series
• Diagonal update method for a quadratic matrix equation
• A ``shift-and-deflate technique for quadratic matrix polynomials
• On some Krylov subspace based methods for large-scale nonsymmetric algebraic Riccati problems
• A structure-preserving doubling algorithm for solving a class of quadratic matrix equation with \(M\)-matrix
• Highly accurate doubling algorithm for quadratic matrix equation from quasi-birth-and-death process
• Shift techniques for quasi-birth and death processes: canonical factorizations and matrix equations
• Efficient cyclic reduction for quasi-birth-death problems with rank structured blocks
• Convergence of pure and relaxed Newton methods for solving a matrix polynomial equation arising in stochastic models
• Efficient methods for solving a nonsymmetric algebraic Riccati equation arising in stochastic fluid models
• A compressed cyclic reduction for QBD processes with low-rank upper and lower transitions
• A subspace shift technique for nonsymmetric algebraic Riccati equations associated with an M-matrix.
• Matrix structures in queuing models
• A fast Newton's iteration for M/G/1-type and GI/M/1-type Markov chains
• Two Types ofRG-Factorizations of Quasi-birth-and-death Processes and Their Applications to Stochastic Integral Functionals
• General solution of the Poisson equation for quasi-birth-and-death processes
• A logarithmic reduction algorithm for quasi-birth-death processes
• Comments on a Shifted Cyclic Reduction Algorithm for Quasi-Birth-Death Problems
• The unified frame of alternating direction method of multipliers for three classes of matrix equations arising in control theory
• Newton-Shamanskii method for a quadratic matrix equation arising in quasi-birth-death problems
• A nontrivial solution to a stochastic matrix equation.
• Shift Techniques and Canonical Factorizations in the Solution of M/G/1-Type Markov Chains
• Highly accurate Latouche-Ramaswami logarithmic reduction algorithm for quasi-birth-and-death process
• Optimal constant for generalized diagonal update method
• On the solution of algebraic Riccati equations arising in fluid queues
• Newton's method for the quadratic matrix equation
• Solving the nonnegative solution for a (shifted) nonsymmetric algebraic Riccati equation in the critical case

This page was built for publication: A shifted cyclic reduction algorithm for quasi-birth-death problems

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