A <Emphasis Type="Italic">V</Emphasis>-cycle Multigrid for multilevel matrix algebras: proof of optimality |
| |
Authors: | Antonio Aricò Marco Donatelli |
| |
Institution: | (1) Dipartimento di Fisica e Matematica, Università dell’Insubria - Sede di Como, Via Valleggio 11, 22100 Como, Italy |
| |
Abstract: | We analyze the convergence rate of a multigrid method for multilevel linear systems whose coefficient matrices are generated
by a real and nonnegative multivariate polynomial f and belong to multilevel matrix algebras like circulant, tau, Hartley, or are of Toeplitz type. In the case of matrix algebra
linear systems, we prove that the convergence rate is independent of the system dimension even in presence of asymptotical
ill-conditioning (this happens iff f takes the zero value). More precisely, if the d-level coefficient matrix has partial dimension n
r
at level r, with , then the size of the system is , , and O(N(n)) operations are required by the considered V-cycle Multigrid in order to compute the solution within a fixed accuracy. Since the total arithmetic cost is asymptotically
equivalent to the one of a matrix-vector product, the proposed method is optimal. Some numerical experiments concerning linear
systems arising in 2D and 3D applications are considered and discussed. |
| |
Keywords: | 65N55 65F10 65F15 |
本文献已被 SpringerLink 等数据库收录! |
|