caa a22 4500 605497176 CHVBK 20210128100540.0 cr unu---uuuuu 210128e20150601xx s 000 0 eng 10.1007/s10543-014-0512-2 doi (NATIONALLICENCE)springer-10.1007/s10543-014-0512-2 Generalized grid transfer operators for multigrid methods applied on Toeplitz matrices [Elektronische Daten] [Matthias Bolten, Marco Donatelli, Thomas Huckle, Christos Kravvaritis] In this paper we discuss classical sufficient conditions to be satisfied from the grid transfer operators in order to obtain optimal two-grid and V-cycle multigrid methods utilizing the theory for Toeplitz matrices. We derive relaxed conditions that allow the construction of special grid transfer operators that are computationally less expensive while preserving optimality. This is particularly useful when the generating symbol of the system matrix has a zero of higher order, like in the case of higher order PDEs. These newly derived conditions allow the use of rank deficient grid transfer operators. In this case the use of a pre-relaxation iteration that is lacking the smoothing property is proposed. Combining these pre-relaxations with the new rank deficient grid transfer operators yields a substantial reduction of the convergence rate and of the computational cost at each iteration compared with the classical choice for Toeplitz matrices. The proposed strategy, i.e. a rank deficient grid transfer operator plus a specific pre-relaxation, is applied to linear systems whose system matrix is a Toeplitz matrix where the generating symbol is a high-order polynomial. The necessity of using high-order polynomials as generating symbols for the grid transfer operators usually destroys the Toeplitz structure on the coarser levels. Therefore, we discuss some effective and computational cheap coarsening strategies found in the literature. In particular, we present numerical results showing near-optimal behavior while keeping the Toeplitz structure on the coarser levels. Springer Science+Business Media Dordrecht, 2014 Multigrid methods nationallicence Toeplitz matrices nationallicence Grid transfer operators nationallicence Bolten Matthias Department of Mathematics and Science, University of Wuppertal, 42097, Wuppertal, Germany aut Donatelli Marco Dipartimento di Scienza e Alta Tecnologia, Università dell'Insubria, Via Valleggio 11, 22100, Como, Italy aut Huckle Thomas Department of Informatics, Technical University of Munich, Boltzmannstr. 3, 85748, Garching, Germany aut Kravvaritis Christos Department of Mathematics, University of Athens, Panepistimioupolis, 157 84, Athens, Greece aut BIT Numerical Mathematics Springer Netherlands 55/2(2015-06-01), 341-366 0006-3835 55:2<341 2015 55 10543 https://doi.org/10.1007/s10543-014-0512-2 text/html Onlinezugriff via DOI BK010053 XK010053 XK010000 Metadata rights reserved Springer special CC-BY-NC licence nationallicence 1 research-article jats NATIONALLICENCE NATIONALLICENCE NL-springer NATIONALLICENCE 856 40 https://doi.org/10.1007/s10543-014-0512-2 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Bolten Matthias Department of Mathematics and Science, University of Wuppertal, 42097, Wuppertal, Germany aut NATIONALLICENCE 700 1- Donatelli Marco Dipartimento di Scienza e Alta Tecnologia, Università dell'Insubria, Via Valleggio 11, 22100, Como, Italy aut NATIONALLICENCE 700 1- Huckle Thomas Department of Informatics, Technical University of Munich, Boltzmannstr. 3, 85748, Garching, Germany aut NATIONALLICENCE 700 1- Kravvaritis Christos Department of Mathematics, University of Athens, Panepistimioupolis, 157 84, Athens, Greece aut NATIONALLICENCE 773 0- BIT Numerical Mathematics Springer Netherlands 55/2(2015-06-01), 341-366 0006-3835 55:2<341 2015 55 10543