In this note we propose a multigrid approach to the solution of (multilevel) banded circulant linear system. In particular, we discuss how to define a "coarse-grid projector" such that the projected matrix at lower dimension preserves the circulant structure. This approach naturally leads to an optimal algorithm having Linear cost as the size N of the system and so improving the the classical one based on Fast Fourier Transforms (FFTs) that costs O(N log N) arithmetic operations (ops). It's worth mentioning that these banded circulants are used as preconditioners for elliptic and parabolic PDEs (with Dirichlet or periodic boundary conditions) and for some 2D image restoration problems where the point spread function (PSF) is numerically banded. Therefore the use of the proposed multigrid technique reduces the overall cost from O(k(epsilon,n)NlogN) to O(k(epsilon,n)N), where k(epsilon,n) is the number of Preconditioned Conjugate Gradient (PCG) iterations to reach the solution within a given accuracy of c. The full analysis of convergence and the related numerical experiments are reported in a forthcoming paper [18].
Serra Capizzano, S., TABLINO POSSIO, C. (2001). Preliminary remarks on multigrid methods for circulant matrices. In NUMERICAL ANALYSIS AND ITS APPLICATIONS (pp.152-159). BERLIN : Springer.
Preliminary remarks on multigrid methods for circulant matrices
TABLINO POSSIO, CRISTINA
2001
Abstract
In this note we propose a multigrid approach to the solution of (multilevel) banded circulant linear system. In particular, we discuss how to define a "coarse-grid projector" such that the projected matrix at lower dimension preserves the circulant structure. This approach naturally leads to an optimal algorithm having Linear cost as the size N of the system and so improving the the classical one based on Fast Fourier Transforms (FFTs) that costs O(N log N) arithmetic operations (ops). It's worth mentioning that these banded circulants are used as preconditioners for elliptic and parabolic PDEs (with Dirichlet or periodic boundary conditions) and for some 2D image restoration problems where the point spread function (PSF) is numerically banded. Therefore the use of the proposed multigrid technique reduces the overall cost from O(k(epsilon,n)NlogN) to O(k(epsilon,n)N), where k(epsilon,n) is the number of Preconditioned Conjugate Gradient (PCG) iterations to reach the solution within a given accuracy of c. The full analysis of convergence and the related numerical experiments are reported in a forthcoming paper [18].I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.