Volume 13, pp. 81-105, 2002.
Multigrid preconditioning and Toeplitz matrices
Thomas Huckle and Jochen Staudacher
Abstract
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