M.S. (Master of Science)
Department of Mathematical Sciences
Toeplitz matrices||Linear systems||Conjugate gradient methods
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.
Trunkhill, William D., "The solution of Toeplitz linear systems via the preconditioned conjugate gradient method with circulant preconditioner" (1993). Graduate Research Theses & Dissertations. 6309.
v, 45 pages
Northern Illinois University
Rights Statement 2