Numerical Studies For M-Matrix Algebraic Riccati Equations

A new doubling algorithm - Alternating-Directional Doubling Algorithm (ADDA) - is developed for computing the unique minimal nonnegative solution of an M-Matrix Algebraic Riccati Equation (MARE). It is argued by both theoretical analysis and numerical experiments that ADDA is always faster than two existing doubling algorithms - SDA of Guo, Lin, and Xu (Numer. Math., 103 (2006), pp. 393-412) and SDA-ss of Bini, Meini, and Poloni (Numer. Math., 116 (2010), pp. 553-578) for the same purpose. A deflation technique is then presented for an irreducible singular M-matrix Algebraic Riccati Equation (MARE). The technique improves the rateof convergence of a doubling algorithm, especially for an MARE in the critical case for which without deflation the doubling algorithm converges linearly and with deflation it converges quadratically. The deflation also improves the conditioning of the MARE in the critical case and thus enables its minimal nonnegative solution to be computed more accurately.