Superfast Solution of Real Positive Definite Toeplitz Systems

Abstract

We describe an implementation of the generalized Schur algorithm for the superfast solution of real positive definite Toeplitz systems of order $n + 1$, where $n = 2^\nu$. Our implementation uses the split-radix Fast Fourier Transform algorithms for real data of Duhamel. We are able to obtain the nth Szegö polynomial using less than $8n\log _2^2 n$ real arithmetic operations without explicit use of the bit-reversal permutation. Since Levinson’s algorithm requires slightly more than $2n^2 $ operations to obtain this polynomial, we achieve crossover with Levinson’s algorithm at $n = 256$.