Volume 13, pp. 81-105, 2002.

Multigrid preconditioning and Toeplitz matrices

Thomas Huckle and Jochen Staudacher


In this paper we discuss multigrid methods for symmetric Toeplitz matrices. Then the restriction and prolongation operators can be seen as projected Toeplitz matrices. Because of the intimate connection between such matrices and trigonometric series we can express the multigrid algorithm in terms of the underlying functions with special zeros. This shows how to choose the prolongation/restriction operator in order to get fast convergence. We start by considering Toeplitz matrices with generating functions having a single zero of finite order in $]-\pi,\pi]$, and we extend previous results on multigrid for Toeplitz matrices, in particular, by introducing a natural coarse grid operator. Afterwards we carry over our reasoning to cases with more than one zero and, we study how the previous cases relate to Toeplitz systems resulting from the discretization of Fredholm integral equations of the first kind which arise in image processing. Next, we take a brief look at Block Toeplitz systems with Toeplitz Blocks. We show how the one-dimensional techniques can be carried over easily for positive definite problems with a single zero in $]-\pi,\pi]^2$ and we also present a multigrid algorithm for linear systems arising from practical image deblurring problems. Finally, we give a new characterization of the well-known difficulties encountered in the indefinite case.

Full Text (PDF) [284 KB], BibTeX

Key words

multigrid methods, iterative methods, preconditioning, Toeplitz matrices, Fredholm integral equations, image deblurring.

AMS subject classifications

65N55, 65F10, 65F22, 65F35, 65R20.

Links to the cited ETNA articles

[3]Vol. 6 (1997), pp. 162-181 A. Brandt and I. Livshits: Wave-ray multigrid method for standing wave equations

ETNA articles which cite this article

Vol. 44 (2015), pp. 25-52 Matthias Bolten, Marco Donatelli, and Thomas Huckle: Analysis of smoothed aggregation multigrid methods based on Toeplitz matrices
Vol. 53 (2020), pp. 283-312 Alessandro Buccini and Marco Donatelli: A multigrid frame based method for image deblurring

< Back