5. Doubling Algorithms

This chapter concerns the treatment of the most recent and advanced algorithms for solving algebraic Riccati and related matrix equations. The emphasis is on algorithms that exploit the specific structure of the matrices and pencils whose graph invariant or graph deflating subspaces provide the solutions of the matrix equations. We consider in particular the main doubling algorithms: The three variants of the structured doubling algorithm (SDA) and the cyclic reduction (CR) algorithm, which have a quadratic convergence in the generic case. We also provide a detailed analysis of these algorithms and point out their interplay. The algorithms are complemented with acceleration techniques obtained by means of the shift strategies reported in Chapter 2. Read More: https://epubs.siam.org/doi/abs/10.1137/1.9781611972092.ch