Grace C. Lim

Publication Date

1995

Document Type

Dissertation/Thesis

First Advisor

Ammar, Gregory S.

Degree Name

M.S. (Master of Science)

Legacy Department

Department of Mathematical Sciences

LCSH

Toeplitz matrices

Abstract

This thesis reviews the definition of Toeplitz matrices and discusses specific direct solvers for Toeplitz systems of equations. Direct solvers for a Toeplitz system of equations (Mx = b) can be considered as a two phase procedure: a factorization phase which determines the last column of M~l and a solution phase which computes M~lb. The focus of this thesis will be the solution phase (or second phase) of these solvers. We first present the connection between the classical theory of Szego polynomials and the inverse Cholesky factorization. This prominent association leads to the derivation and understanding of the Szego recursions and its equivalence to the Levinson-Durbin algorithm. In the factorization phase, the Levinson-Durbin algorithm is used to generate the coefficients of Szego polynomials for the last column of M~l. By performing direct multiplication of any arbitrary b with the coefficients of Szego polynomials, the Levinson algorithm is determined. The basics behind the factorization and solution phases is developed from the Christoffel-Darboux-Szego formula which is derived using the Szego recursions. The Christoffel-Darboux-Szego formula is used to derive Trench’s algorithm for constructing the M-1. The second part of the thesis examines the solution phase based on the Toeplitz inversion formulas given by Gohberg-Semencul and Ammar-Gader. The efficient implementation of the second phase relies on the use of fast Fourier transforms to evaluate cyclic convolutions. Some basic concepts of the fast Fourier transform and its use in the solution phase are described. The decomposition of the Toeplitz inversion formulas and the utilization of the properties of circulant matrices are combined with the techniques of fast Fourier transform to attain the solution for the second phase. This method of O(nlogn) is used for both fast and superfast algorithms.

Comments

Includes bibliographical references (leaf [47])

Extent

46 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