Doubling algorithms for Toeplitz and related equations

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²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 ≤ α ≤ 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(αᵈ n log²n)</tex> operations, ( <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">d ≤ 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.