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

77 Citations (Scopus)


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
Issue number2
Publication statusPublished - Mar 1998
Externally publishedYes


  • Multigrid method
  • Toeplitz matrices


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

Cite this