|
|
|
“Preconditioned Iterative Methods for Solving Toeplitz Systems”
by Ta-Kang Ku
August 1991
In the dissertation, we study the use of preconditioned iterative methods to solve linear systems of equations associated with Toeplitz, block Toeplitz and Toeplitz-plus-Hankel coefficient matrices. Two main issues are considered: the design of preconditioners and the convergence rate of preconditioned iterative methods.
A systematic approach to the design of Toeplitz preconditioners with circulant matrices is proposed. This preconditioning scheme is then generalized to block Toeplitz and Toeplitz-plus-Hankel matrices. All resulting preconditioners of size N can be inverted with O(N log N) operations via various fast transform algorithms. Another novel scheme to design Toeplitz preconditioners baseon the minimum-phase LU (MPLU) factorization is also examined. The MPLU preconditioner can be inverted with O(N) operations.
The convergence rate of preconditioned iterative methods depends on the eigenvalue or singular value distribution of preconditioned matrices. We perform spectral analysis for a large class of symmetric and nonsymmetric Toeplitz in general, and rational Toeplitz in particular. For rational Toeplitz, we classify the eigenvalues into outlying and clustered eigenvalues, and show that the number of outliers depends on the order of the rational generating function, and the clustering radius is proportional to the magnitude of the last elements in the generating sequence used to construct the preconditioner. Similar spectral results are obtained for Toeplitz-plus-Hankel systems. A direct consequence of the analysis is that preconditioned iterative methods converge in a fixed number of iterations independent of the problem size. The computational complexity of preconditioned iterative methods for solving an N x N Toeplitz system is therefore proportional to O(N log N).
Compared to direct methods, preconditioned iterative methods provide three advantages: low computational complexity, ease of parallel implementation and stable numerical property.