A divide-and-conquer split Schur algorithm
Kifowit, Steven J.
MetadataShow full item record
Positive definite Toeplitz systems of equations arise in a number of applications in pure and applied mathematics. Methods of solution specifically designed to exploit the symmetry of such linear systems have been studied in earnest since the late 1940's. By 1990, ''superfast'' methods, whose operation counts were asymptotically far lower than traditional methods, had been developed and implemented.;This dissertation concerns the superfast solution of Toeplitz systems. In particular, a new algorithm is described for solving the Yule-Walker equations associated with a Hermitian positive definite Toeplitz matrix. The new algorithm is based on a doubling procedure applied to the split Schur algorithm. This procedure computes the solution of the Yule-Walker equations by processing a family of split Levinson symmetric polynomials. The operation count for the new algorithm is among the lowest for all known direct methods for solving the Yule-Walker equations.;The foundations of the new superfast algorithm rest on the split Schur algorithm. A new derivation of the split Schur algorithm is also described in this work. That derivation highlights the classical underpinnings of the split Schur algorithm and reveals its nature as a recursion on a certain class of functions.;The new superfast algorithm is rich in operations on symmetric polynomials. It derives its speed from fast Fourier transform techniques for polynomial multiplication and division. A number of new symmetry-exploiting FFT techniques are also contained in this work.