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 $r=1,\dots,d$, then the size of the system is $N(\mi{n})=\prod_{r=1}^d n_r$, $\mi{n}=(n_1, \dots, n_d)$, and $O(N(\mi{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.

A V-cycle Multigrid for multilevel matrix algebras: proof of optimality

DONATELLI, MARCO
2007

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 $r=1,\dots,d$, then the size of the system is $N(\mi{n})=\prod_{r=1}^d n_r$, $\mi{n}=(n_1, \dots, n_d)$, and $O(N(\mi{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.
http://link.springer.com/article/10.1007/s00211-006-0049-7
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11383/1496335
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 42
  • ???jsp.display-item.citation.isi??? 38
social impact