Publication Date

1993

Document Type

Dissertation/Thesis

Degree Name

M.S. (Master of Science)

Department

Department of Mathematical Sciences

LCSH

Toeplitz matrices||Linear systems||Conjugate gradient methods

Abstract

This paper studies the solution of symmetric positive definite Toeplitz linear systems Ax = b by the preconditioned conjugate gradient method. The preconditioners P are chosen to be circulant matrices and, thus, the Fast Fourier Transform can be conveniently applied in each iteration of the algorithm. Convergence of the preconditioned conjugate gradient method is governed by the eigenvalue distribution of P^(-1)A and for a large class of problems we prove that the circulant matrix which minimizes||P — A||[sub 1] clusters the spectrum around unity as n —> ∞. Furthermore, it is shown that the preconditioned conjugate gradient method performs with computational complexity O(nlogn) as n —> ∞ for this class of problems.

Comments

Includes bibliographical references (pages [42]-43)

Extent

v, 45 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

Share

COinS