A shifted cyclic reduction algorithm for quasi-birth-death problems (Q2784374)

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.