Abstract/Details

Fast algorithms for Toeplitz equations

Boman, Eugene Clayton. 
 University of Connecticut ProQuest Dissertations Publishing,  1993. 9419425.

Abstract (summary)

We study efficient methods for solving large scale positive definite Toeplitz systems equations, both direct and iterative. Our main emphasis and contributions are for the iterative Preconditioned Conjugate Gradient Algorithm in conjunction with fast (O(nlog(n))) transforms. We develop a general scheme of constructing preconditioners from classes of matrices diagonalizable by a fast transform. Our method is demonstrated in detail for one of the Fast Sine Transforms. In particular we show: (i) how to construct such a preconditioner efficiently, (ii) asymptotic clustering of the spectra of preconditioned matrices, (iii) uniform boundedness of condition numbers of preconditioners corresponding to a projection method, (iv) positive definiteness of the preconditioner. A fast method is developed for Toeplitz matrix-vector multiplication using a Fast Sine Transform and real arithmetic. Traditionally the Fast Fourier Transform is used but this method requires complex arithmetic even when the Toeplitz matrix is real.

Other fast transforms and types of preconditioners are studied although in less detail.

The results of extensive numerical experimentation are presented.

Indexing (details)


Subject
Mathematics
Classification
0405: Mathematics
Identifier / keyword
Pure sciences
Title
Fast algorithms for Toeplitz equations
Author
Boman, Eugene Clayton
Number of pages
103
Degree date
1993
School code
0056
Source
DAI-B 55/03, Dissertation Abstracts International
Place of publication
Ann Arbor
Country of publication
United States
ISBN
979-8-209-08066-4
University/institution
University of Connecticut
University location
United States -- Connecticut
Degree
Ph.D.
Source type
Dissertation or Thesis
Language
English
Document type
Dissertation/Thesis
Dissertation/thesis number
9419425
ProQuest document ID
304054737
Copyright
Database copyright ProQuest LLC; ProQuest does not claim copyright in the individual underlying works.
Document URL
https://www.proquest.com/docview/304054737/abstract