Design and analysis of Toeplitz preconditioners
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.
- Computational and Information Science
- scientific article; zbMATH DE number 1421686
- scientific article; zbMATH DE number 2069439
- A modified T. Chan's preconditioner for Toeplitz systems
- Recursive-Based PCG Methods for Toeplitz Systems with Nonnegative Generating Functions
- Superlinear PCG methods for symmetric Toeplitz systems
- The Spectrum of a Family of Circulant Preconditioned Toeplitz Systems
- scientific article; zbMATH DE number 1223054
- Toeplitz Equations by Conjugate Gradients with Circulant Preconditioner
- Approximate inverse circulant-plus-diagonal preconditioners for Toeplitz-plus-diagonal matrices
- Displacement structure approach to discrete-trigonometric-transform based preconditioners of G. Strang type and of T. Chan type
- Jackson's theorem and circulant preconditioned Toeplitz systems
- A fast, preconditioned conjugate gradient Toeplitz solver
- The rate of convergence of Toeplitz based PCG methods for second order nonlinear boundary value problems
- Circulant preconditioners for Toeplitz-block matrices
- Fast iterative methods for least squares estimations
- Toeplitz approximate inverse preconditioner for banded Toeplitz matrices
- Displacement preconditioner for Toeplitz least squares iterations
- Band preconditioners for block-Toeplitz -- Toeplitz-block systems
- Fast algorithms for solving FLS \(R\)-factor block circulant linear systems and inverse problem of \(\mathcal{A} X = b\)
- Circulant integral operators as preconditioners for Wiener-Hopf equations
- A fast, preconditioned conjugate gradient Toeplitz and Toeplitz-like solvers
- Recursive self preconditioning method based on Schur complement for Toeplitz matrices
- C. G. preconditioning for Toeplitz matrices
- A survey and some extensions of T. Chan's preconditioner
- Preconditioning random Toeplitz systems
- The Spectrum of a Family of Circulant Preconditioned Toeplitz Systems
- Approximate inverse circulant-plus-diagonal preconditioners for Toeplitz-plus-diagonal matrices
- Circulant Preconditioners for Toeplitz Matrices with Positive continuous Generating Functions
- Toeplitz Preconditioners Constructed from Linear Approximation Processes
- Circulant Preconditioners for Toeplitz Matrices with Piecewise Continuous Generating Functions
- FFT-Based Preconditioners for Toeplitz-Block Least Squares Problems
- Conjugate Gradient Methods for Toeplitz Systems
- scientific article; zbMATH DE number 822859 (Why is no real title available?)
- Generalization of Strang's Preconditioner with Applications to Toeplitz Least Squares Problems
- scientific article; zbMATH DE number 7479348 (Why is no real title available?)
- A preconditioned MINRES method for nonsymmetric Toeplitz matrices
- Displacement Structure Approach to Discrete-Trigonometric-Transform Based Preconditioners of G.Strang Type and of T.Chan Type
- Computational and Information Science
- An efficient conjugate gradient preconditioner for Toeplitz systems
- Accelerated circulant and skew circulant splitting methods for Hermitian positive definite Toeplitz systems
- Toeplitz preconditioners for Hermitian Toeplitz systems
- A modified T. Chan's preconditioner for Toeplitz systems
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)