In this paper we are interested in the solution by multigrid strategies of multilevel linear systems whose coefficient matrices belong to the circulant, Hartley, or τ algebras or to the Toeplitz class and are generated by (the Fourier expansion of) a nonnegative multivariate polynomial f. It is well known that these matrices are banded and have eigenvalues equally distributed as f, so they are ill-conditioned whenever f takes the zero value; they can even be singular and need a low-rank correction. We prove the V-cycle multigrid iteration to have a convergence rate independent of the dimension even in presence of ill-conditioning. If the (multilevel) coefficient matrix has partial dimension nr at level r, r = 1, . . . ,d, then the size of the algebraic system is N(n) = Πr=1 d nr, O(N(n)) operations are required by our technique, and therefore the corresponding method is optimal. Some numerical experiments concerning linear systems arising in applications, such as elliptic PDEs with mixed boundary conditions and image restoration problems, are considered and discussed.cussed.

V-cycle optimal convergence for certain (multilevel) structured linear systems

DONATELLI, MARCO;SERRA CAPIZZANO, STEFANO
2005

Abstract

In this paper we are interested in the solution by multigrid strategies of multilevel linear systems whose coefficient matrices belong to the circulant, Hartley, or τ algebras or to the Toeplitz class and are generated by (the Fourier expansion of) a nonnegative multivariate polynomial f. It is well known that these matrices are banded and have eigenvalues equally distributed as f, so they are ill-conditioned whenever f takes the zero value; they can even be singular and need a low-rank correction. We prove the V-cycle multigrid iteration to have a convergence rate independent of the dimension even in presence of ill-conditioning. If the (multilevel) coefficient matrix has partial dimension nr at level r, r = 1, . . . ,d, then the size of the algebraic system is N(n) = Πr=1 d nr, O(N(n)) operations are required by our technique, and therefore the corresponding method is optimal. Some numerical experiments concerning linear systems arising in applications, such as elliptic PDEs with mixed boundary conditions and image restoration problems, are considered and discussed.cussed.
Circulant; Hartley, and τ algebra; Multi-iterative methods; Multilevel matrices; Toeplitz class; Two-grid and multigrid iterations
File in questo prodotto:
File Dimensione Formato  
9-42198.pdf

accesso aperto

Tipologia: Documento in Post-print
Licenza: DRM non definito
Dimensione 344 kB
Formato Adobe PDF
344 kB Adobe PDF Visualizza/Apri

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/1491773
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 73
  • ???jsp.display-item.citation.isi??? 66
social impact