Look-ahead Levinson and Schur algorithms for non-Hermitian Toeplitz systems (Q1893485)

The classical Schur and Levinson algorithms compute the columns of the \(U\) factor in an LDU factorization of a Hermitian Toeplitz matrix \(T\) or its inverse, respectively. They break down when \(T\) is not strongly regular, i.e., when not all the leading principal submatrices are nonsingular. Several variants were proposed to deal with the non- Hermitian and the non strongly regular case when exact arithmetic is used. Some of the steps may be ill-conditioned though, leading to unstable algorithms. In this paper, look-ahead steps, searching for only stable operations are proposed. A step is only executed when two successive leading principal submatrices are sufficiently well-conditioned. When the lengths of these steps are bounded, the algorithms require \(O(N^ 2)\) operations for a Toeplitz matrix of size \(N\). Another variant using divide and conquer and fast polynomial arithmetic needs only \(O(N \log^ 2 N)\) operations. In comparison with other look-ahead methods for Toeplitz matrices [cf. e.g. \textit{T. F. Chan} and \textit{P. C. Hansen} [IEEE Trans. Signal Processing 40, No. 5, 1079-1090 (1992; Zbl 0756.65044); \textit{R. W. Freund} and \textit{H. Zha}, Linear Algebra Appl. 188-189, 255-303 (1993; Zbl 0777.65011); \textit{M. H. Gutknecht}, Linear Algebra Appl. 188-189, 351-421 (1993; Zbl 0777.65014)], the stepping condition requiring two successive submatrices to be nonsingular is stronger, resulting in generally larger look-ahead steps.