A Fast Newton's Method for a Nonsymmetric Algebraic Riccati Equation

A special instance of the algebraic Riccati equation $XCX-XE-AX+B=0$ where the $n\times n$ matrix coefficients $A,B,C,E$ are rank structured matrices is considered. Relying on the structural properties of Cauchy-like matrices, an algorithm is designed for performing the customary Newton iteration in $O(n^2)$ arithmetic operations (ops). The same technique is used to reduce the cost of the algorithm proposed by L.-Z. Lu in [Numer. Linear Algebra Appl., 12 (2005), pp. 191-200] from $O(n^3)$ to $O(n^2)$ ops while still preserving quadratic convergence in the generic case. As a byproduct we show that the latter algorithm is closely related to the customary Newton method by simple formal relations. In critical cases where the Jacobian at the required solution is singular and quadratic convergence turns to linear, we provide an adaptation of the shift technique in order to get rid of the singularity. The original equation is transformed into an equivalent Riccati equation where the singularity is removed while the matrix coefficients maintain the same structure as in the original equation. This leads to a quadratically convergent algorithm with complexity $O(n^2)$ which provides approximations with full precision. Numerical experiments and comparisons which confirm the effectiveness of the new approach are reported.