The structure-preserving doubling algorithm (SDA)  is a fairly efficient method for solving problems closely related to Hamiltonian (or Hamiltonian-like) matrices, such as  computing the required solutions to  algebraic Riccati equations. However, for  large-scale problems, the SDA with an $/bigO(n^3)$ computational complexity does not work well. In this talk, we devise a new decoupled form of the  SDA and propose a novel doubling method  (we name it dSDA) to solve large-scale problems owning  low-rank structures. Decoupling the original two to four iteration formulae in the SDA, the proposed dSDA is much more efficient since only one iterate (instead of the original two to four) is computed.  For large-scale problems, further efficiency is gained from the low-rank structures for the kernels are of much smaller sizes comparing with those in the original SDA. More importantly, the dSDA can take full advantage of the structures existed in the original data, such as structural sparsity or low-rank update of a diagonal matrix, thus requiring $/bigO(n)$ flops per iteration, enabling it more suitable for large-scale problems. Illustrative numerical results will be presented to show the efficiency of our approach. 

海报