  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 in
$\mathbb{C}^n$ (also $\mathbb{R}^n$), the SDA with an $O(n^3)$ computational
complexity does not work well. In this paper, we propose a new decoupled form
of the SDA (we name it as dSDA), building on the associated Krylov subspaces
thus leading to the inherent low-rank structures. Importantly, the approach
decouples the original two to four iteration formulae. The resulting dSDA is
much more efficient since only one quantity (instead of the original two to
four) is computed iteratively. For large-scale problems, further efficiency is
gained from the low-rank structures. This paper presents the theoretical
aspects of the dSDA. A practical algorithm dSDA t with truncation and many
illustrative numerical results will appear in a second paper.
