Design and analysis of Toeplitz preconditioners

From MaRDI portal





The preconditioned conjugate gradient method (PCG) for solving symmetric positive definite Toeplitz systems \(Ax=b\) can be derived by iteratively minimizing the quadratic form \(x^ TAx/2-b^ Tx\) with the conjugate gradient method and preconditioning. Since the convergence rate of the conjugate gradient method depends on the spectrum of the matrix \(A\), a preconditioning step is to be introduced at each conjugate iteration, so that the spectrum of the preconditioned matrix is clustered around 1 or has a small condition number. The convergence rate of the PCG method depends heavily on the choice of the preconditioning matrix for the given Toeplitz matrix. \textit{G. Strang's} preconditioner [Stud. Appl. Math. 74, 171-176 (1986; Zbl 0621.65025)] is obtained by preserving the central half diagonals of \(A\) and using them to form a circulant matrix and the computational complexity is \(O(N\log N)\). \textit{T. F. Chan's} preconditioner [SIAM J. Sci. Stat. Comput. 9, No. 4, 766-771 (1988; Zbl 0646.65042)] is generated by using all elements of \(A\), but the convergence rate is not improved compared with Strang's preconditioner. The paper presents another direction to generalize Strang's preconditioner using all elements of \(A\), and Strang's and Chan's preconditioners can be regarded as special cases of the generalization. A new preconditioner with better performance is obtained. The inverse Toeplitz matrix-vector product is formulated as a partially characterized linear deconvolution problem. The preconditioning step corresponds to the implementation of the approximating circular deconvolution. All resulting preconditioners can be inverted with \(O(N\log N)\) operations with various fast transformation algorithms such as the fast Fourier transform, the fast cosine transform and the fast sine transform.




Cited in
(33)








This page was built for publication: Design and analysis of Toeplitz preconditioners

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3991434)