Approximate Inverse Circulant-plus-Diagonal Preconditioners for Toeplitz-plus-Diagonal Matrices

Michael K. Ng, Jianyu Pan

Research output: Contribution to journalJournal articlepeer-review

40 Citations (Scopus)
4 Downloads (Pure)

Abstract

We consider the solutions of Hermitian positive definite Toeplitz-plus-diagonal systems (T +D)x = b, where T is a Toeplitz matrix and D is diagonal and positive. However, unlike the case of Toeplitz systems, no fast direct solvers have been developed for solving them. In this paper, we employ the preconditioned conjugate gradient method with approximate inverse circulant-plus-diagonal preconditioners to solving such systems. The proposed preconditioner can be constructed and implemented efficiently using fast Fourier transforms. We show that if the entries of T decay away exponentially from the main diagonals, the preconditioned conjugate gradient method applied to the preconditioned system converges very quickly. Numerical examples including spatial regularization for image deconvolution application are given to illustrate the effectiveness of the proposed preconditioner.

Original languageEnglish
Pages (from-to)1442-1464
Number of pages23
JournalSIAM Journal on Scientific Computing
Volume32
Issue number3
DOIs
Publication statusPublished - 21 May 2010

Scopus Subject Areas

  • Computational Mathematics
  • Applied Mathematics

User-Defined Keywords

  • Approximate inverse
  • Circulant matrices
  • Convergence analysis
  • Toeplitz-plus-diagonal matrices

Fingerprint

Dive into the research topics of 'Approximate Inverse Circulant-plus-Diagonal Preconditioners for Toeplitz-plus-Diagonal Matrices'. Together they form a unique fingerprint.

Cite this