Toeplitz Equations by Conjugate Gradients with Circulant Preconditioner
SIAM Journal on Scientific and Statistical Computing1989Vol. 10(1), pp. 104–119
Citations Over TimeTop 1% of 1989 papers
Abstract
This paper studies the solution of symmetric positive definite Toeplitz systems $Ax = b$ by the preconditioned conjugate gradient method. The preconditioner is a circulant matrix C that copies the middle diagonals of A, and each iteration uses the Fast Fourier Transform. Convergence is governed by the eigenvalues of $C^{ - 1} A$–a Toeplitz-circulant eigenvalue problem—and it is fast if those eigenvalues are clustered. The limiting behavior of the eigenvalues is found as the dimension increases, and it is proved that they cluster around $\lambda = 1$. For a wide class of problems the error after q conjugate gradient steps decreases as $r^{q^2 } $.
Related Papers
- → Practical compressive sensing with Toeplitz and circulant matrices(2010)172 cited
- → Circulant and skew-circulant splitting methods for Toeplitz systems(2003)63 cited
- → Asymptotically Good Pseudomodes for Toeplitz Matrices and Wiener-Hopf Operators(2004)3 cited
- Practical Compressive Sensing with Toeplitz and Circulant Matrices(2010)
- → Non-Circulant Type Preconditioners(2004)