Abstract
An algebraic multigrid algorithm for symmetric, positive definite linear systems is developed based on the concept of prolongation by smoothed aggregation. Coarse levels are generated automatically. We present a set of requirements motivated heuristically by a convergence theory. The algorithm then attempts to satisfy the requirements. Input to the method are the coefficient matrix and zero energy modes, which are determined from nodal coordinates and knowledge of the differential equation. Efficiency of the resulting algorithm is demonstrated by computational results on real world problems from solid elasticity, plate bending, and shells.
Zusammenfassung
Es wird ein algebraisches Mehrgitterverfahren für symmetrische, positiv definite Systeme vorgestellt, das auf dem Konzept der geglätteten Aggregation beruht. Die Grobgittergleichungen werden automatisch erzeugt. Wir stellen eine Reihe von Bedingungen auf, die aufgrund der Konvergenztheorie heuristisch motiviert sind. Der Algorithmus versucht diese Bedingungen zu erfüllen. Eingabe der Methode sind die Matrix-Koeffizienten und die Starrkörperbewegungen, die aus den Knotenwerten unter Kenntnis der Differentialgleichung bestimmt werden. Die Effizienz des entstehenden Algorithmus wird anhand numerischer Resultate für praktische Aufgaben aus den Bereichen Elastizität, Platten und Schalen demonstriert.
Similar content being viewed by others
References
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).
Bramble, J., Zhang, X.: Multigrid methods for the biharmonic problem discretized by conformingC 1 finite elements on nonnested meshes (submitted).
Bramble, J. H., Pasciak, J. E., Wang, J., Xu, J.: Convergence estimates for multigrip algorithms without regularity assumptions. Math. Comp.57, 23–45 (1991).
Brandt, A.: Algebraic multigrid theory: The symmetric case. Appl. Math. Comput.19, 23–56 (1986).
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.
Brenner, S. C.: An optimal order nonconforming multigrid method for the biharmonic equation. SIAM J. Numer. Anal.26, 1124–1138 (1989).
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.
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).
Hackbusch, W.: Multigrid methods and applications. Computational mathematics, Vol. 4. Berlin Heidelberg New York: Springer 1985.
Mandel, J.: Balancing domain decomposition. Comm. Numer. Meth. Eng.9, 233–241 (1993).
Oswald, P.: Hierarchical conforming finite element methods for the biharmonic equation. SIAM J. Numer Anal.29, 1620–1625 (1992).
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).
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.
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.
Ruge, J. W., Stüben, K.: Algebraic multigrid (AMG) In: Multigrid methods (McCormick, S. F., ed.), pp. 73–130, Philadelphia: SIAM 1987.
Smith, R. A., Weiser, A.: Semicoarsening multigrid on a hypercube. SIAM J. Sci. Stat. Comput.13, 1314–1329 (1992).
Stüben, K.: Algebraic multigrid (AMG): experiences and comparisons, Appl. Math. Comput.13, 419–452 (1983).
Vaněk, P.: Fast multigrid solver. Appl. Math.40, 1–20 (1995).
Vaněk, P.: Acceleration of convergence of a two-level algorithm by smoothing transfer operator. Appl. Math.37, 265–274 (1992).
Vaněk, P., Mandel, J., Brezina, M.: Algebraic multigrid on unstructured meshes (Submitted).
Zhang, X.: Multilevel Schwarz methods for the biharmonic Dirichlet problem. SIAM J. Sci. Comput.15, 621–644 (1994).
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Vaněk, P., Mandel, J. & Brezina, M. Algebraic multigrid by smoothed aggregation for second and fourth order elliptic problems. Computing 56, 179–196 (1996). https://doi.org/10.1007/BF02238511
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF02238511