|
|
|
“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).