THE BEST CIRCULANT PRECONDITIONERS FOR HERMITIAN TOEPLITZ SYSTEMS

Raymond H. CHAN, Andy M. YIP, Michael K. NG

Research output: Journal Publications and ReviewsRGC 21 - Publication in refereed journalpeer-review

26 Citations (Scopus)

Abstract

In this paper, we propose a new family of circulant preconditioners for ill-conditioned Hermitian Toeplitz systems Ax = b. The preconditioners are constructed by convolving the generating function ƒ of A with the generalized Jackson kernels. For an n-by-n Toeplitz matrix A, the construction of the preconditioners requires only the entries of A and does not require the explicit knowledge of ƒ. When ƒ is a nonnegative continuous function with a zero of order 2p, the condition numberof A is known to grow as O(n2p ). We show, however, that our preconditioner is positive definite and the spectrum of the preconditioned matrix is uniformly bounded except for at most 2p +1 outliers. Moreover, the smallest eigenvalue is uniformly bounded away from zero. Hence the conjugate gradient method, when applied to solving the preconditioned system, converges linearly. The total complexity of solving the system is therefore of O(n log n) operations. In the case when ƒ is positive, we show that the convergence is superlinear. Numerical results are included to illustrate the effectiveness of our new circulant preconditioners.
Original languageEnglish
Pages (from-to)876-896
JournalSIAM Journal on Numerical Analysis
Volume38
Issue number3
Online published17 Aug 2000
DOIs
Publication statusPublished - 2000
Externally publishedYes

Research Keywords

  • Circulant preconditioner
  • Kernel functions
  • Preconditioned conjugate gradient method
  • Toeplitz systems

Fingerprint

Dive into the research topics of 'THE BEST CIRCULANT PRECONDITIONERS FOR HERMITIAN TOEPLITZ SYSTEMS'. Together they form a unique fingerprint.

Cite this