MULTIGRID METHOD FOR ILL-CONDITIONED SYMMETRIC TOEPLITZ SYSTEMS

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

68 Scopus Citations
View graph of relations

Author(s)

Detail(s)

Original languageEnglish
Pages (from-to)516-529
Journal / PublicationSIAM Journal of Scientific Computing
Volume19
Issue number2
Publication statusPublished - Mar 1998
Externally publishedYes

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.

Research Area(s)

  • Multigrid method, Toeplitz matrices

Citation Format(s)

MULTIGRID METHOD FOR ILL-CONDITIONED SYMMETRIC TOEPLITZ SYSTEMS. / CHAN, Raymond H.; CHANG, Qian-Shun; SUN, Hai-Wei.

In: SIAM Journal of Scientific Computing, Vol. 19, No. 2, 03.1998, p. 516-529.

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review