论文标题
与低级别结构的连续算法的脱钩形式
A decoupled form of the structure-preserving doubling algorithm with low-rank structures
论文作者
论文摘要
具有结构的加倍算法（SDA）是一种相当有效的方法，用于解决与哈密顿量（或类似哈密顿的）矩阵密切相关的问题，例如计算代数riccati方程所需的解决方案。但是，对于$ \ mathbb {c}^n $中的大规模问题（也是$ \ mathbb {r}^n $），具有$ O（n^3）$计算复杂性的SDA效果不佳。在本文中，我们提出了一种新的SDA解耦形式（我们将其命名为DSDA），并在相关的Krylov子空间上构建，从而导致固有的低级结构。重要的是，该方法将原始的两到四个迭代公式解散。所得的DSDA效率要高得多，因为仅计算出一个数量（而不是原始的两到四个）。对于大规模的问题，从低级结构中获得了进一步的效率。本文介绍了DSDA的理论方面。第二篇论文将出现具有截断和许多说明性数值结果的实用算法DSDA T。
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.
