The hierarchical basis multigrid method. (English) Zbl 0645.65074

Based on earlier work of the third author and the PLTMG package of the first author, the authors describe, analyze and implement the mentioned method for the numerical solution of a standard self-adjoint twodimensional elliptic problem as a symmetric block Gauß-Seidel method with inner iterations (which can be rewritten in V-cycle manner). For the discretization, linear triangular elements are employed. The point is here that the triangulation may be generated (refined) adaptively: The described multigrid method does not assume that the numbers of unknowns on the different refinement levels grow geometrically to assure a work estimate per iteration of the overall unknown number since on any level only the new points are iterated. The analysis also does not require the usual strong ellipticity condition. The price for these advantages is that the number of iterations depends on the number of levels.
Reviewer: G.Stoyan


65N30 Finite element, Rayleigh-Ritz and Galerkin methods for boundary value problems involving PDEs
65F10 Iterative numerical methods for linear systems
65F35 Numerical computation of matrix norms, conditioning, scaling
35J25 Boundary value problems for second-order elliptic equations
Full Text: DOI EuDML


[1] Axelsson, O., Barker, V.A.: Finite Element Solution of Boundary Value Problems: Theory and Computation. New York: Academic Press 1984 · Zbl 0537.65072
[2] Bank, R.E.: PLTMG User’s Guide, Edition 4.0; Technical Report, Department of Mathematics. University of California at San Diego 1985
[3] Bank, R.E., Dupont, T.: Analysis of a Two-Level Scheme for Solving Finite Element Equations. Report CNA-159; Center for Numerical Analysis, University of Texas at Austin 1980
[4] Bank, R.E., Dupont, T.: An Optimal Order Process for Solving Finite Element Equations. Math. Comput.36, 35-51 (1981) · Zbl 0466.65059 · doi:10.1090/S0025-5718-1981-0595040-2
[5] Bank, R.E., Sherman, A., Weiser, A.: Refinement Algorithms and Data Structures for Local Mesh Refinement. In: Scientific Computing (R. Stepleman et al. eds.), Amsterdam: IMACS/North Holland 1983
[6] Braess, D.: The Contraction Number of a Multigrid Method for Solving the Poisson Equation. Numer. Math.37, 387-404 (1981) · Zbl 0461.65078 · doi:10.1007/BF01400317
[7] Bramble, J.H., Pasciak, J.E., Schatz, A.H.: An Iterative, Method for Elliptic Problems and Regions Partioned into Substructures. Math. Comput.46, 361-369 (1986) · Zbl 0595.65111 · doi:10.1090/S0025-5718-1986-0829613-0
[8] Bramble, J.H., Pasciak, J.E., Schatz, A.H.: The Construction of Preconditioners for Elliptic Problems by Substructuring. I. Math. Comput.47, 103-134 (1986) · Zbl 0615.65112 · doi:10.1090/S0025-5718-1986-0842125-3
[9] Hackbusch, W.: Multigrid Methods and Applications. Berlin Heidelberg New York: Springer 1985 · Zbl 0595.65106
[10] Hageman, L.A., Young, D.M.: Applied Iterative Methods. New York: Academic Press 1981 · Zbl 0459.65014
[11] Maitre, J.F., Musy, F.: The Contraction Number of a Class of Two-Level Methods; an Exact Evaluation for some Finite Element Subspaces and Model Problems. In: Multigrid Methods (W. Hackbusch, U. Trottenberg eds.), Lect. Notes Math. 960, Berlin Heidelberg New York: Springer 1982 · Zbl 0505.65049
[12] Rivara, M.C.: Algorithms for Refining Triangular Grids Suitable for Adaptive and Multigrid Techniques. Int J. Numer. Methods Eng.20, 745-756 (1984) · Zbl 0536.65085 · doi:10.1002/nme.1620200412
[13] Young, D.M.: Convergence Properties of the Symmetric and Unsymmetric Successive Overrelaxation Method and Related Methods. Math. Comput.24, 793-807 (1970) · Zbl 0221.65060 · doi:10.1090/S0025-5718-1970-0281331-4
[14] Yserentant, H.: On the Multi-Level Splitting of Finite Element Spaces. Numer. Math.49, 379-412 (1986) · Zbl 0608.65065 · doi:10.1007/BF01389538
[15] Yserentant, H.: Hierarchical Bases Give Conjugate Gradient Type Methods a Multigrid Speed of Convergence. Appl. Math. Comput.19, 347-358 (1986) · Zbl 0614.65114 · doi:10.1016/0096-3003(86)90113-X
[16] Yserentant, H.: On the Multi-Level Splitting of Finite Element Spaces for Indefinite Elliptic Boundary Value Problems. Siam J. Numer. Anal.23, 581-595 (1986) · Zbl 0616.65102 · doi:10.1137/0723037
[17] Yserentant, H.: Hierarchical Bases of Finite Element Spaces in the Discretization of Nonsymmetric Elliptic Boundary Value Problems. Computing35, 39-49 (1985) · Zbl 0566.65080 · doi:10.1007/BF02240145
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.