Multigrid methods for toeplitz matrices
Tóm tắt
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).
Tài liệu tham khảo
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.