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.