Multigrid method for ill-conditioned symmetric toeplitz systems

Raymond H. CHAN*, Qian Shun CHANG, Hai Wei SUN

*Corresponding author for this work

Research output: Journal PublicationsJournal Article (refereed)peer-review

79 Citations (Scopus)

Abstract

In this paper, we consider solutions of Toeplitz systems Anu = b where the Toeplitz matrices An are generated by nonnegative functions with zeros. Since the matrices An are ill conditioned, the convergence factor of classical iterative methods, such as the damped Jacobi method, will approach one as the size n of the matrices becomes large. Here we propose to solve the systems by the multigrid method. The cost per iteration for the method is of O(n log n) operations. For a class of Toeplitz matrices which includes weakly diagonally dominant Toeplitz matrices, we show that the convergence factor of the two-grid method is uniformly bounded below one independent of n, and the full multigrid method has convergence factor depending only on the number of levels. Numerical results are given to illustrate the rate of convergence.

Original languageEnglish
Pages (from-to)516-529
Number of pages14
JournalSIAM Journal on Scientific Computing
Volume19
Issue number2
DOIs
Publication statusPublished - Mar 1998
Externally publishedYes

Keywords

  • Multigrid method
  • Toeplitz matrices

Fingerprint

Dive into the research topics of 'Multigrid method for ill-conditioned symmetric toeplitz systems'. Together they form a unique fingerprint.

Cite this