Highly accurate doubling algorithms for \(M\)-matrix algebraic Riccati equations (Q515850): Difference between revisions

This is about the minimal solution of the \(M\)-matrix algebraic Riccati equation (MARE) \(XDX - AX - XB + C = 0\), where \[ W=\begin{bmatrix} B & -D\\-C&A\end{bmatrix} \] is a nonsingular or an irreducible singular \(M\)-matrix. If an \(M\)-matrix \(S\) has a triplet representation \((N_S,u,v)\) with \(N_S=\mathrm{diag}(S)-S\), \(u>0\), and \(v=Su\geq 0\) and if the triplet is known with high relative accuracy, then \(Sx=b\) can be solved with the same entry-wise relative accuracy using a GHT-like method (see [\textit{A. S. Alfa} et al., Math. Comput. 71, No. 237, 217--236 (2002; Zbl 0984.65033)]). When doubling algorithms are used to solve the MARE, there can be some critical stages in which cancellation occurs, preventing to compute accurate triplets for the \(M\)-matrices in the iteration steps. \textit{G. T. Nguyen} and \textit{F. Poloni} [Numer. Math. 130, No. 4, 763--792 (2015; Zbl 1326.65055)] described a cancellation-free implementation of a structured doubling algorithm, assuming that \(W\mathbf{1}=0\) (\(\mathbf{1}\) is a vector of all ones). In this paper the authors remove the latter condition using an iteration of auxiliary vectors to obtain accurate triplets. They also introduce a new entry-wise relative residual error to estimate the accuracy of the minimal solution.