A factored variant of the Newton iteration for the solution of algebraic Riccati equations via the matrix sign function

Abstract

In this paper we introduce a variant of the Newton iteration for the matrix sign function that results in an efficient numerical solver for a certain class of algebraic Riccati equations (AREs). In particular, when the Hamiltonian matrix associated with the ARE can be composed as [ACTCBBT−AT] , with B and CT having a much larger number of rows than columns, the new algorithm exploits the special structure of the off-diagonal blocks to yield an alternative factored Newton iteration which reduces the cost per iteration by a factor of up to 8 (16 in case A is symmetric negative definite) w.r.t. the conventional iterative scheme. Experiments with a large collection of benchmark examples show that the factored iteration attains numerical accuracy similar to that of the conventional Newton iteration as well as the structure-preserving doubling algorithm. High-performance implementations of these methods, making heavy use of LAPACK linked to a multi-threaded implementation of BLAS, demonstrate the clear advantage of the new iteration on a 48-core AMD-based platform.