Doubling algorithms for Toeplitz and related equations

Abstract

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 <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">O(n \log^{2}n)</tex> 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 <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1 \leq \alpha \leq n</tex> , an index of how close a matrix is to being Toeplitz, requiring <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">O(\alpha^{d} n \log^{2}n)</tex> operations, ( <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">d \leq 2</tex> ). 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.