Abstract
We introduce a class of Multigrid methods for solving banded, symmetric Toeplitz systems Ax=b. We use a, special choice of the projection operator whose coefficients simply depend on some spectral properties of A. This choice leads to an iterative Multigrid method with convergence rate smaller than 1 independent of the condition number K2(A) and of the dimension of the matrix. In the second part the B0 class is introduced: this class, of Toeplitz matrices contains the linear space generated by the matrices arising from the finite differences discretization of the differential operators
, m∈N +. To sum up we present an adaptive algorithm which has a input the coefficients of A and return an iterative Multigrid method with convergence speed independent of the mesh spacing h and with an asymptotical cost of O(n).
Similar content being viewed by others
References
W. Hackbursch,Multigrid Methods and Applications, 1985, Springer Verlag, Berlin.
W. Hackbusch,Multigrid methods II, Lecture notes in Math. 1228 (1987).
K. Stuben, U. Trottenberg,Multigrid methods, Lecture notes in Math. 960 (1981).
D. Bini, M. Capovani,Spectral and Computational Properties of Band Simmetric Matrices, Linear Algebra Appl. 52/53, 99–125 (1983).
R. S. Varga,Matrix Iterative Analysis, 1962, Prentice/Hall.
A. Greenbaum,Analysis of a multigrid method as an iterative technique for solving linear systems, SIAM J. Numer. Anal. 21 (3), 473–458 (1984).
J. Stoer, R. Bulirsch,Introduction to Numerical Analysis, 1980, Springer Verlag, Berlin.
U. Grenander, G. Szego,Toeplitz Forms and Their Applications, 1984, Second edition, Chelsea, New York.
I. S. Iokhvidov,Hankel and Toeplitz forms: algebraic theory, 1982, Birkhauser, Boston.
S. Serra,On multi-iterative methods, To appear.
S. Serra,Proprietà algebriche e computazionali delle matrici di Toeplitz e metodi Multigrid, Thesis in computer science, University of Pisa 1990.
G. Fiorentino,Formulazione algebrica dei metodi multigrid. Applicazioni alla risoluzione di sistemi di Toeplitz a bonda, Thesis in computer science, University of Pisa 1990.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Fiorentino, G., Serra, S. Multigrid methods for toeplitz matrices. Calcolo 28, 283–305 (1991). https://doi.org/10.1007/BF02575816
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF02575816