SIAM Journal on Matrix Analysis and Applications · 1988 · 261 citations · 22 references
Natural SciencesComputer ScienceMathematicsAlgorithmsCombinatoricsTheory Of ComputationComputational AlgebraComputational MathematicsDigital Signal ProcessingMatrix ComputationNumerical AnalysisNumerical Linear AlgebraFast Fourier TransformSchur Functions
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$.
22
Introduction to Numerical Analysis.
Carl-Erik Fröberg, Josef Stoer, Roland Bulirsch · Mathematics of Computation · 1981 · 5.5K citations
Stephen Hoffman · American Mathematical Monthly · 1968 · 1.2K citations