Alternating-directional doubling algorithm for \(M\)-matrix algebraic Riccati equations (Q2903117)

A new doubling algorithm for computing the minimal nonnegative solution of an \(M\)-matrix algebraic Riccati equation \(XDX -AX-XB+ C = 0\) is presented and analysed. The matrices \(A\), \(B\), \(C\), and \(D\) are the blocks of the matrix NEWLINE\[NEWLINE W = \begin{pmatrix} B & -D \\ -C & A \end{pmatrix} \, , NEWLINE\]NEWLINE where \(W\) is a nonsingular or an irreducible singular \(M\)-matrix. At first, some known results on \(M\)-matrices are summarized and a new result on optimizing the product of two spectral radii of the generalized Cayley transforms of two \(M\)-matrices is proved. Then, the new alternating-directional doubling algorithm is described and analysed. The difference to known algorithms is in the initial setup. In the new algorithm two parameters are introduced to get a faster algorithm when the matrices \(A\) and \(B\) differ in magnitude. Furthermore, the convergence rates of the new algorithm and known algorithms are compared. It is shown theoretically and by numerical examples that the new doubling algorithm is faster than the doubling algorithms proposed by \textit{X.-X. Guo, W.-W. Lin} and \textit{S.-F. Xu} [Numer. Math. 103, No. 3, 393--412 (2006; Zbl 1097.65055)] and by \textit{D. A. Bini, B. Meini} and \textit{F. Poloni} [Numer. Math. 116, No. 4, 553--578 (2010; Zbl 1202.15016)].