Volume 29, pp. 136-149, 2007-2008.

On the parameter selection problem in the Newton-ADI iteration for large-scale Riccati equations

Peter Benner, Hermann Mena, and Jens Saak


The numerical treatment of linear-quadratic regulator (LQR) problems for parabolic partial differential equations (PDEs) on infinite-time horizons requires the solution of large-scale algebraic Riccati equations (AREs). The Newton-ADI iteration is an efficient numerical method for this task. It includes the solution of a Lyapunov equation by the alternating direction implicit (ADI) algorithm at each iteration step. Here, we study the selection of shift parameters for the ADI method. This leads to a rational min-max problem which has been considered by many authors. Since knowledge about the exact shape of the complex spectrum is crucial for computing the optimal solution, this is often infeasible for the large-scale systems arising from finite element discretization of PDEs. Therefore, several methods for computing suboptimal parameters are discussed and compared on numerical examples.

Full Text (PDF) [2.2 MB]

Key words

algebraic Riccati equation, Newton-ADI, shift parameters, Lyapunov equation, rational min-max problem, Zolotarev problem

AMS subject classifications

15A24, 30E10, 65B99

ETNA articles which cite this article

Vol. 33 (2008-2009), pp. 53-62 M. Heyouni and K. Jbilou: An extended block Arnoldi algorithm for large-scale solutions of the continuous-time algebraic Riccati equation
Vol. 43 (2014-2015), pp. 142-162 Peter Benner, Patrick Kürschner, and Jens Saak: Self-generating and efficient shift parameters in ADI methods for large Lyapunov and Sylvester equations

< Back