Algebraic multigrid by smoothed aggregation for second and fourth order elliptic problems. (English) Zbl 0851.65087

The authors develop an algebraic multigrid algorithm for symmetric positive definite linear systems based on a concept of smoothed aggregation relying on a suitable decomposition of the set of nodes and a corresponding tentative interpolation. The coarsening is governed by abstract multigrid theory and by requirements reflecting practical experience. Favorable behaviour of the algorithm is demonstrated on eleven real-world examples from solid elasticity, plate bending, and shells. The code is available via internet on the address given in the paper.


65N55 Multigrid methods; domain decomposition for boundary value problems involving PDEs
74B05 Classical linear elasticity
74S05 Finite element methods applied to problems in solid mechanics
65N30 Finite element, Rayleigh-Ritz and Galerkin methods for boundary value problems involving PDEs
65F10 Iterative numerical methods for linear systems
35J40 Boundary value problems for higher-order elliptic equations
74K20 Plates
74K15 Membranes
Full Text: DOI


[1] Alcouffe, R. E., Brandt, A., Dendy, J. E., Painter J. W.: The multi-grid methods for the diffusion equation with strongly discontinuous coefficients. SIAM J. Sci. Stat. Comput.2, 430–454 (1981). · Zbl 0474.76082
[2] Bramble, J., Zhang, X.: Multigrid methods for the biharmonic problem discretized by conformingC 1 finite elements on nonnested meshes (submitted). · Zbl 0842.65081
[3] Bramble, J. H., Pasciak, J. E., Wang, J., Xu, J.: Convergence estimates for multigrip algorithms without regularity assumptions. Math. Comp.57, 23–45 (1991). · Zbl 0727.65101
[4] Brandt, A.: Algebraic multigrid theory: The symmetric case. Appl. Math. Comput.19, 23–56 (1986). · Zbl 0616.65037
[5] Brandt, A., McCormick, S. F., Ruge, J. W.: Algebraic multigrid (AMG) for sparse matrix equations. In: Sparsity and its applications (Evans, D. J., ed.), pp. 257–284 Cambridge: Cambridge University Press 1985. · Zbl 0548.65014
[6] Brenner, S. C.: An optimal order nonconforming multigrid method for the biharmonic equation. SIAM J. Numer. Anal.26, 1124–1138 (1989). · Zbl 0679.65083
[7] Chan, T. F., Go, S., Zou, J.: Multilevel domain decomposition and multigrid methods for unstructured meshes: algorithms and theory. Tech. Report Cam 95-24, Dept. Math., UCLA, May 1995.
[8] Dendy, J. E., Ida, M. P., Rutledge, J. M.: A semicoarsening multigrid algorithm for SIMD machines., SIAM J. Sci. Stat. Comput.13, 1460–1469 (1992). · Zbl 0767.65085
[9] Hackbusch, W.: Multigrid methods and applications. Computational mathematics, Vol. 4. Berlin Heidelberg New York: Springer 1985. · Zbl 0595.65106
[10] Mandel, J.: Balancing domain decomposition. Comm. Numer. Meth. Eng.9, 233–241 (1993). · Zbl 0796.65126
[11] Oswald, P.: Hierarchical conforming finite element methods for the biharmonic equation. SIAM J. Numer Anal.29, 1620–1625 (1992). · Zbl 0771.65071
[12] Peisker, P., Braess, D.: A conjugate gradient method and a multigrid method for Morley’s finite element approximation of the biharmonic equation. Numer. Math.50, 567–586 (1987). · Zbl 0595.65113
[13] Ruge, J. W.: Algebraic multigrid (AMG) for geodetic survey problems, in Prelimary Proc. Internat. Multigrid Conference, Fort Collins, CO, 1983, Institute for Computational Studies at Colorado State University.
[14] Ruge, J. W., Stüben, K.: Efficient solution of finite difference and finite element equations by algebraic multigrid (AMG), In: Multigrid methods for integral and differential equations (Paddon, D. J., Holstein, H., eds.), pp. 169–212. The Institute of Mathematics and its Applications Conference Series, Oxford: Clarendon Press 1985. · Zbl 0581.65072
[15] Ruge, J. W., Stüben, K.: Algebraic multigrid (AMG) In: Multigrid methods (McCormick, S. F., ed.), pp. 73–130, Philadelphia: SIAM 1987.
[16] Smith, R. A., Weiser, A.: Semicoarsening multigrid on a hypercube. SIAM J. Sci. Stat. Comput.13, 1314–1329 (1992). · Zbl 0767.65087
[17] Stüben, K.: Algebraic multigrid (AMG): experiences and comparisons, Appl. Math. Comput.13, 419–452 (1983). · Zbl 0533.65064
[18] Vaněk, P.: Fast multigrid solver. Appl. Math.40, 1–20 (1995). · Zbl 0824.65016
[19] Vaněk, P.: Acceleration of convergence of a two-level algorithm by smoothing transfer operator. Appl. Math.37, 265–274 (1992). · Zbl 0773.65021
[20] Vaněk, P., Mandel, J., Brezina, M.: Algebraic multigrid on unstructured meshes (Submitted).
[21] Zhang, X.: Multilevel Schwarz methods for the biharmonic Dirichlet problem. SIAM J. Sci. Comput.15, 621–644 (1994). · Zbl 0803.65118
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.