A Block-Shifted Cyclic Reduction Algorithm for Solving a Class of Quadratic Matrix Equations
Incremental improvement to the cyclic reduction algorithm for solving quadratic matrix equations in QBD stochastic processes.
The paper addresses the convergence issue of the cyclic reduction algorithm for quadratic matrix equations when multiple eigenvalues lie on the unit circle, proposing a Block-Shifted CR algorithm that uses SVD and block shift-and-deflate techniques to extend applicability. Numerical experiments show effectiveness and robustness.
The cyclic reduction (CR) algorithm is an efficient method for solving quadratic matrix equations that arise in quasi-birth-death (QBD) stochastic processes. However, its convergence is not guaranteed when the associated matrix polynomial has more than one eigenvalue on the unit circle. To address this limitation, we introduce a novel iteration method, referred to as the Block-Shifted CR algorithm, that improves the CR algorithm by utilizing singular value decomposition (SVD) and block shift-and-deflate techniques. This new approach extends the applicability of existing solvers to a broader class of quadratic matrix equations. Numerical experiments demonstrate the effectiveness and robustness of the proposed method.