We introduce a multigrid technique for the solution of multilevel circulant linear systems whose coefficient matrix has eigenvalues of the form $f(x_j^{[n]})$, where $f$ is continuous and independent of $n=(n_1,\ldots,n_d)$, and $x_j^{[n]} \equiv 2\pi j/n = (2\pi j_1/n_1, \ldots, 2\pi j_d/n_d)$, $0 \le j_r \le n_r - 1$. The interest of the proposed technique pertains to the multilevel banded case, where the total cost is optimal, i.e., $O(N)$ arithmetic operations (ops), $N=\prod_{r=1}^d n_r$, instead of $O(N\log N)$ ops arising from the use of FFTs. In fact, multilevel banded circulants are used as preconditioners for elliptic and parabolic PDEs (with Dirichlet or periodic boundary conditions) and for some two-dimensional image restoration problems where the point spread function (PSF) is numerically banded, so that the overall cost is reduced from $O(k(\varepsilon,n)N \log N)$ to $O(k(\varepsilon,n)N)$, where $k(\varepsilon,n)$ is the number of PCG iterations to reach the solution within an accuracy of $\varepsilon$. Several numerical experiments concerning one-rank regularized circulant discretization of elliptic $2q$-differential operators over one-dimensional and two-dimensional square domains with mixed boundary conditions are performed and discussed.

Multigrid methods for multilevel circulant matrices

SERRA CAPIZZANO, STEFANO;
2005-01-01

Abstract

We introduce a multigrid technique for the solution of multilevel circulant linear systems whose coefficient matrix has eigenvalues of the form $f(x_j^{[n]})$, where $f$ is continuous and independent of $n=(n_1,\ldots,n_d)$, and $x_j^{[n]} \equiv 2\pi j/n = (2\pi j_1/n_1, \ldots, 2\pi j_d/n_d)$, $0 \le j_r \le n_r - 1$. The interest of the proposed technique pertains to the multilevel banded case, where the total cost is optimal, i.e., $O(N)$ arithmetic operations (ops), $N=\prod_{r=1}^d n_r$, instead of $O(N\log N)$ ops arising from the use of FFTs. In fact, multilevel banded circulants are used as preconditioners for elliptic and parabolic PDEs (with Dirichlet or periodic boundary conditions) and for some two-dimensional image restoration problems where the point spread function (PSF) is numerically banded, so that the overall cost is reduced from $O(k(\varepsilon,n)N \log N)$ to $O(k(\varepsilon,n)N)$, where $k(\varepsilon,n)$ is the number of PCG iterations to reach the solution within an accuracy of $\varepsilon$. Several numerical experiments concerning one-rank regularized circulant discretization of elliptic $2q$-differential operators over one-dimensional and two-dimensional square domains with mixed boundary conditions are performed and discussed.
2005
circulant algebra; two-grid and multigrid iterations; multilevel matrices
SERRA CAPIZZANO, Stefano; Tablino Possio, C.
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: https://hdl.handle.net/11383/1492688
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 38
  • ???jsp.display-item.citation.isi??? 35
social impact