Publication Date

2015

Document Type

Dissertation/Thesis

First Advisor

Ammar, Gregory S.

Degree Name

Ph.D. (Doctor of Philosophy)

Legacy Department

Department of Mathematical Sciences

LCSH

Mathematics; Toeplitz matrices--Research; Algorithms--Research; Schur functions--Research

Abstract

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.

Comments

Advisors: Gregory S. Ammar.||Committee members: Douglas Bowman; Linda R. Sons; Zhuan Ye.

Extent

197 pages

Language

eng

Publisher

Northern Illinois University

Rights Statement

In Copyright

Rights Statement 2

NIU theses are protected by copyright. They may be viewed from Huskie Commons for any purpose, but reproduction or distribution in any format is prohibited without the written permission of the authors.

Media Type

Text

Download

Share

COinS