Doubling algorithms for Toeplitz and related equations
Doubling algorithms for Toeplitz and related equations
复制标题
DOI：
10.1109/icassp.1980.1171074
复制
发表时间：
1980-04
期刊：
影响因子：
--
通讯作者：
M. Morf
中科院分区：
文献类型：
--
作者：
M. Morf
提出了一类新的求解Toeplitz方程及相关方程的二分算法。对于标量n乘n Toeplitz矩阵，它们需要O（n \log^{2}n）计算，类似于Gustavson和Yun基于HGCD（half-greatest-common-divisor）的算法。然而，这些新算法基于“移位”或位移秩1 \leq \alpha \leq n的概念，这是一个矩阵与Toeplitz的接近程度的指标，需要O（\alpha^{d} n \log^{2}n）运算，（d \leq 2）。本文给出了这类“α-Toeplitz矩阵”的一个基本的加倍算法，并讨论了这些结果在有关问题中的应用，如带状矩阵、块矩阵和Hankel矩阵的求逆。
A new class of doubling or halving algorithms for solving Toeplitz and related equations is presented. For scalar n by n Toeplitz matrices, they require O(n \log^{2}n) computations, similarly to the HGCD (half-greatest-common-divisor) based algorithm of Gustavson and Yun. However, these new algorithms are based on the notions of "shift" or displacement rank 1 \leq \alpha \leq n , an index of how close a matrix is to being Toeplitz, requiring O(\alpha^{d} n \log^{2}n) operations, ( d \leq 2 ). A basic version of a doubling algorithm for such "α-Toeplitz matrices" is presented, and the applications of these results to related problems are mentioned, such as the inversion of banded-, block- and Hankel matrices.