## Abstract

Aggregation-based multigrid with standard piecewise constant like prolongation is investigated. Unknowns are aggregated either by pairs or by quadruplets; in the latter case the grouping may be either linewise or boxwise. A Fourier analysis is developed for a model twodimensional anisotropic problem. Most of the results are stated for an arbitrary smoother (which fits with the Fourier analysis framework). It turns out that the convergence factor of two-grid schemes can be bounded independently of the grid size. With a sensible choice of the (linewise or boxwise) coarsening, the bound is also uniform with respect to the anisotropy ratio, without requiring a specialized smoother. The bound is too large to guarantee optimal convergence properties with the V-cycle or the standard W-cycle, but a W-cycle scheme accelerated by the recursive use of the conjugate gradient method exhibits near grid independent convergence

## Authors

Adrian C. **Muresan****
**Tiberiu Popoviciu Institute of Numerical Analysis, Romanian Academy

Yvan Notay

Universite Libre de Bruxelles, Service de Metrologie Nucleaire (C.P. 165/84), 50, Av. F.D. Roosevelt, B-1050 Brussels, Belgium

## Keywords

multigrid; aggregation; Fourier analysis; Krylov subspace method; conjugate gradient; preconditioning

### References

See the expanding block below.

## Paper coordinates

A.C. Muresan, Y. Notay, *Analysis of aggregation-based multigrid, *SIAM J. SCI. COMPUT. c 2008 Society for Industrial and Applied Mathematics, Vol. 30, No. 2, pp. 1082–1103, 10.1137/060678397

http://doi.org/10.1137/060678397

## About this paper

##### Print ISSN

??

##### Online ISSN

??

##### Google Scholar Profile

[1] O. Axelsson and P. S. Vassilevski, A black-box generalized conjugate gradient solver with inner iterations and variable-step preconditioning, SIAM J. Matrix Anal. Appl., 12 (1991), pp. 625–644.

[2] A. Ben Israel and T. N. E. Greville, Generalized Inverses: Theory and Applications, John Wiley and Sons, New York, 1974.

[3] D. Braess, Towards algebraic multigrid for elliptic problems of second order, Computing, 55 (1995), pp. 379–393.

[4] D. Braess, Finite Elements. Theory, Fast Solvers, and Applications in Solid Mechanics, Cambridge University Press, Cambridge, UK, 1997.

[5] V. E. Bulgakov, Multi-level iterative technique and aggregation concept with semi-analytical preconditioning for solving boundary value problems, Comm. Numer. Methods in Engrg., 9 (1993), pp. 649–657.

[6] G. H. Golub and C. F. van Loan, Matrix Computations, 3rd ed., The Johns Hopkins University Press, Baltimore, MD 1996.

[7] W. Hackbusch, Multigrid Methods and Applications, Springer-Verlag, Berlin, 1985.

[8] W. Leontief, The Structure of the American Economy 1919–1939, Oxford University Press, New York, 1951.

[9] Y. Notay, Flexible conjugate gradients, SIAM J. Sci. Comput., 22 (2000), pp. 1444–1460.

[10] Y. Notay, Aggregation-based algebraic multilevel preconditioning, SIAM J. Matrix Anal. Appl., 27 (2006), pp. 998–1018.

[11] Y. Notay, Convergence analysis of perturbed two-grid and multigrid methods, SIAM J. Numer. Anal., 45 (2007), pp. 1035–1044.

[12] Y. Notay and P. S. Vassilevski, Recursive Krylov-based multigrid cycles, Numer. Linear Algebra Appl., to appear. Available online at http://homepages.ulb.ac.be/∼ynotay.

[13] K. Stuben, An introduction to algebraic multigrid, in Multigrid, Academic Press, San Diego, 2001, pp. 413–532, Appendix A.

[14] U. Trottenberg, C. W. Oosterlee, and A. Schuller , Multigrid, Academic Press, San Diego, 2001.

[15] P. Vanek, M. Brezina, and R. Tezaur , Two-grid method for linear elasticity on unstructured meshes, SIAM J. Sci. Comput., 21 (1999), pp. 900–923.

[16] P. Vanek, J. Mandel, and M. Brezina , Algebraic multigrid based on smoothed aggregation for second and fourth order elliptic problems, Computing, 56 (1996), pp. 179–196.

[17] R. Wienands and W. Joppich, Practical Fourier Analysis for Multigrid Methods, Chapman & Hall/CRC Press, Boca Raton, FL, 2005.

[18] R. Wienands and C. W. Oosterlee, On three-grid Fourier analysis for multigrid, SIAM J. Sci. Comput., 23 (2001), pp. 651–671.