Superfast Solution of Real Positive Definite Toeplitz Systems

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^ν. 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 8nlog ₂² n real arithmetic operations without explicit use of the bit-reversal permutation. Since Levinson’s algorithm requires slightly more than 2n² operations to obtain this polynomial, we achieve crossover with Levinson’s algorithm at $n = 256$.