Skip to main content
Log in

On the multi-level splitting of finite element spaces

  • Asymptotic Behavior and Acceleration og Iterative Sequences
  • Published:
Numerische Mathematik Aims and scope Submit manuscript

Summary

In this paper we analyze the condition number of the stiffness matrices arising in the discretization of selfadjoint and positive definite plane elliptic boundary value problems of second order by finite element methods when using hierarchical bases of the finite element spaces instead of the usual nodal bases. We show that the condition number of such a stiffness matrix behaves like O((log κ)2) where κ is the condition number of the stiffness matrix with respect to a nodal basis. In the case of a triangulation with uniform mesh sizeh this means that the stiffness matrix with respect to a hierarchical basis of the finite element space has a condition number behaving like\(O\left( {\left( {\log \frac{1}{h}} \right)^2 } \right)\) instead of\(O\left( {\left( {\frac{1}{h}} \right)^2 } \right)\) for a nodal basis. The proofs of our theorems do not need any regularity properties of neither the continuous problem nor its discretization. Especially we do not need the quasiuniformity of the employed triangulations. As the representation of a finite element function with respect to a hierarchical basis can be converted very easily and quickly to its representation with respect to a nodal basis, our results mean that the method of conjugate gradients needs onlyO(log n) steps andO(n log n) computer operations to reduce the energy norm of the error by a given factor if one uses hierarchical bases or related preconditioning procedures. Heren denotes the dimension of the finite element space and of the discrete linear problem to be solved.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Axelsson, O., Barker, V.A.: Finite element solution of boundary value problems: Theory and computation. New York: Academic Press 1984

    Google Scholar 

  2. Axelsson, O., Gustafsson, I.: Preconditioning and two-level multigrid methods of arbitrary degree of approximation. Math. Comput.40, 219–242 (1983)

    Google Scholar 

  3. Bank, R.E.: PLTMG user's guide, Edition 4.0, Technical Report, Department of Mathematics, University of California at San Diego 1985

  4. Bank, R.E., Dupont, T.: An optimal order process for solving finite element equation. Math. Comput.36, 35–51 (1981)

    Google Scholar 

  5. 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

  6. Braess, D.: The contraction number of a multigrid method for solving the Poisson equation. Numer. Math.37, 387–404 (1981)

    Google Scholar 

  7. Hackbusch, W.: On the convergence of multi-grid iterations. Beiträge Numer. Math.9, 213–329 (1981)

    Google Scholar 

  8. Hackbusch, W.: Multi-grid convergence theory. In: Multigrid methods. (W. Hackbusch and U. Trottenberg eds.).

  9. Hackbusch, W., Trottenberg, U.: Multigrid methods. Proceedings, Köln 1981, Lect. Notes Math. 960. Berlin, Heidelberg, New York: Springer 1982

    Google Scholar 

  10. Oganesjan, L.A., Ruhovec, L.A.: Variational difference methods for the solution of elliptic differential equations (in Russian) Erevan 1979

  11. Thomée, V.: Galerkin finite element methods for parabolic problems. Lect. Notes Math. 1054. Berlin, Heidelberg, New York: Springer 1984

    Google Scholar 

  12. Wendland, W.L.: Elliptic systems in the plane. London, San Francisco, Melbourne: Pitman 1979

    Google Scholar 

  13. Yserentant, H.: The convergence of multi-level methods for solving finite element equations in the presence of singularities (To appear in Math. Comput.)

  14. Yserentant, H.: On the convergence of multi-level methods for strongly nonuniform families of grids and any number of smoothing steps per level. Computing30, 305–313 (1983)

    Google Scholar 

  15. Yserentant, H.: Über die Maximumnormkonvergenz der Methode der finiten Elemente bei geringsten Regularitätsvoraussetzungen. Z. Angew. Math. Mech.65, 91–100 (1985)

    Google Scholar 

  16. Zienciewicz, O.C., Kelly, D.W., Gago, J., Babuška, I.: Hierarchical finite element approaches, error estimates and adaptive refinement. In: The mathematics of finite elements and applications IV. (J.R. Whiteman ed.) London: Academic Press 1982

    Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Rights and permissions

Reprints and permissions

About this article

Cite this article

Yserentant, H. On the multi-level splitting of finite element spaces. Numer. Math. 49, 379–412 (1986). https://doi.org/10.1007/BF01389538

Download citation

  • Received:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF01389538

Subject Classification

Navigation