Multigrid methods for Toeplitz matrices

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[Figure not available: see fulltext.], 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).