The USC Andrew and Erna Viterbi School of Engineering USC Signal and Image Processing Institute USC Ming Hsieh Department of Electrical Engineering University of Southern California

Technical Report USC-SIPI-155

“Design and Analysis of Toeplitz Preconditioners”

by Takang Ku and C.C. Jay Kuo

May 1990

The solution of symmetric positive definite Toeplitz systems Ax = b by the preconditioned conjugate gradient (PCG) method was recently proposed by Strang [21] and analyzed by Strang and R. Chan [7]. The convergence rate of the PCG method heavily depends on the choice of preconditioners for given Toeplitz matrices. In this paper, we present a general approach to the design of Toeplitz preconditioners based on the idea to approximate a partially characterized linear deconvolution with circular deconvolutions. All resulting preconditioners can therefore be inverted via various fast transform algorithms with O(N log N) operations. For a wide class of problems, the PCG method converges in a finite number of iterations independent of N so that the computational complexity for solving these Toeplitz systems is O(N log N).

To download the report in PDF format click here: USC-SIPI-155.pdf (1.2Mb)