Look-ahead Levinson and Schur Algorithms For Non-hermitian Toeplitz Systems

We present generalizations of the nonsymmetric Levinson and Schur algorithms for non-Hermitian Toeplitz matrices with some singular or ill-conditioned leading principal submatrices. The underlying recurrences allow us to go from any pair of successive well-conditioned leading principal submatrices to any such pair of larger order. If the look-ahead step size between these pairs is bounded, our gen-eralized Levinson and Schur recurrences require O(N 2) operations, and the Schur recurrences can be combined with recursive doubling so that an O(N log2N) algo-rithm results. The overhead (in operations and storage) of look-ahead steps is very small. There are various options for applying these algorithms to solving linear systems with Toeplitz matrix