Skip to main content
SpringerLink
Log in

\(\mathcal {H}\)-matrix approximability of the inverses of FEM matrices

  • Published:
Numerische Mathematik Aims and scope Submit manuscript

Abstract

We study the question of approximability for the inverse of the FEM stiffness matrix for (scalar) second order elliptic boundary value problems by blockwise low rank matrices such as those given by the \(\mathcal {H}\)-matrix format introduced by Hackbusch (Computing 62(2):89–108, 1999). We show that exponential convergence in the local block rank \(r\) can be achieved. We also show that exponentially accurate \(LU\)-decompositions in the \(\mathcal {H}\)-matrix format are possible for the stiffness matrices arising in the FEM. Our analysis avoids any coupling of the block rank \(r\) to the mesh width \(h\). We also cover fairly general boundary conditions of mixed Dirichlet–Neumann–Robin boundary conditions.

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

Access this article

Log in via an institution

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

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3

Similar content being viewed by others

References

  1. Adams, R.A.: Sobolev spaces, Pure and Applied Mathematics, vol. 65. Academic Press, New York (1975)

  2. Bebendorf, M.: Hierarchical LU decomposition-based preconditioners for BEM. Computing 74(3), 225–247 (2005)

    Article  MATH  MathSciNet  Google Scholar 

  3. Bebendorf, M.: Why finite element discretizations can be factored by triangular hierarchical matrices. SIAM J. Numer. Anal. 45(4), 1472–1494 (2007)

    Article  MATH  MathSciNet  Google Scholar 

  4. Bebendorf, M., Hackbusch, W.: Existence of \(\cal {H}\)-matrix approximants to the inverse FE-matrix of elliptic operators with \(L^{\infty }\)-coefficients. Numer. Math. 95(1), 1–28 (2003)

    Article  MATH  MathSciNet  Google Scholar 

  5. Bennighof, J.K., Lehoucq, R.B.: An automated multilevel substructuring method for eigenspace computation in linear elastodynamics. SIAM J. Sci. Comput. 25(6), 2084–2106 (electronic) (2004). doi:10.1137/S1064827502400650

  6. Börm, S.: Approximation of solution operators of elliptic partial differential equations by \(\cal {H}\)- and \({\cal {H}}^2\)-matrices. Numer. Math. 115(2), 165–193 (2010)

    Article  MATH  MathSciNet  Google Scholar 

  7. Börm, S.: Efficient Numerical Methods for Non-local Operators, EMS Tracts in Mathematics, vol. 14. European Mathematical Society (EMS), Zürich (2010)

    Book  Google Scholar 

  8. Börm, S., Grasedyck, L.: H-Lib—a library for \(\cal {H}\)-and \({\cal {H}}^2\)-matrices. http://www.hlib.org (1999)

  9. Brenner, S., Scott, L.: The Mathematical Theory of Finite Element Methods, Texts in Applied Mathematics, vol. 15. Springer, New York (2002)

    Book  Google Scholar 

  10. Brenner, S.C.: The condition number of the Schur complement in domain decomposition. Numer. Math. 83(2), 187–203 (1999)

    Article  MATH  MathSciNet  Google Scholar 

  11. Chandrasekaran, S., Dewilde, P., Gu, M., Somasunderam, N.: On the numerical rank of the off-diagonal blocks of Schur complements of discretized elliptic PDEs. SIAM J. Matrix Anal. Appl. 31(5), 2261–2290 (2010). doi:10.1137/090775932

  12. Dahmen, W., Faermann, B., Graham, I.G., Hackbusch, W., Sauter, S.A.: Inverse inequalities on non-quasiuniform meshes and application to the mortar element method. Math. Comput. 73, 1107–1138 (2001)

    Article  MathSciNet  Google Scholar 

  13. Demkowicz, L., Kurtz, J., Pardo, D., Paszyński, M., Rachowicz, W., Zdunek, A.: Computing with \(hp\)-adaptive finite elements, vol. 2. Chapman & Hall/CRC Applied Mathematics and Nonlinear Science Series, Frontiers: three dimensional elliptic and Maxwell problems with applications. Chapman & Hall/CRC, Boca Raton (2008)

  14. Ern, A., Guermond, J.L.: Evaluation of the condition number in linear systems arising in finite element approximations. M2AN Math. Model. Numer. Anal. 40(1), 29–48 (2006)

    Article  MATH  MathSciNet  Google Scholar 

  15. Faustmann, M.: \({\cal {H}}\)-matrix approximantion of inverses of FEM and BEM matrices. doctoral thesis, work in progress, Vienna (2015)

  16. Faustmann, M., Melenk, J.M., Praetorius, D.: Existence of \({\cal {H}}\)-matrix approximation to the inverse of BEM matrices: the simple layer operator. Institute for Analysis and Scientific Computing, Vienna University of Technology, Wien, Tech. Rep. in preparation (2013)

  17. Faustmann, M., Melenk, J.M., Praetorius, D.: Existence of \({\cal {H}}\)-matrix approximants to the inverses of BEM matrices: the hyper singular integral operator. Work in progress (2014)

  18. Giebermann, K.: Multilevel approximation of boundary integral operators. Computing 67(3), 183–207 (2001). doi:10.1007/s006070170005

  19. Gillman, A., Martinsson, P.: A direct solver with \(O(N)\) complexity for variable coefficient elliptic PDEs discretized via a high-order composite spectral collocation method. Tech. rep. (2013). arXiv:1302.5995 [math.NA]

  20. Grasedyck, L.: Theorie und Anwendungen Hierarchischer Matrizen. Doctoral thesis, Kiel (2001) (in German)

  21. Grasedyck, L.: Adaptive recompression of \({\cal H}\)-matrices for BEM. Computing 74(3), 205–223 (2005)

    Article  MATH  MathSciNet  Google Scholar 

  22. Grasedyck, L., Hackbusch, W.: Construction and arithmetics of \({\cal H}\)-matrices. Computing 70(4), 295–334 (2003)

    Article  MATH  MathSciNet  Google Scholar 

  23. Grasedyck, L., Hackbusch, W., Kriemann, R.: Performance of \({\cal H}\)-LU preconditioning for sparse matrices. Comput. Methods Appl. Math. 8(4), 336–349 (2008)

    Article  MATH  MathSciNet  Google Scholar 

  24. Grasedyck, L., Kriemann, R., Le Borne, S.: Parallel black box \({\cal H}\)-LU preconditioning for elliptic boundary value problems. Comput. Vis. Sci. 11(4–6), 273–291 (2008). doi:10.1007/s00791-008-0098-9

  25. Grasedyck, L., Kriemann, R., Le Borne, S.: Domain decomposition based \({\cal H}\)-LU preconditioning. Numer. Math. 112(4), 565–600 (2009)

    Article  MATH  MathSciNet  Google Scholar 

  26. Greengard, L., Gueyffier, D., Martinsson, P.G., Rokhlin, V.: Fast direct solvers for integral equations in complex three-dimensional domains. Acta Numer. 18, 243–275 (2009). doi:10.1017/S0962492906410011

  27. Hackbusch, W.: A sparse matrix arithmetic based on \({\cal H}\)-matrices. Introduction to \({\cal H}\)-matrices. Computing 62(2), 89–108 (1999)

  28. Hackbusch, W.: Hierarchische Matrizen: Algorithmen und Analysis. Springer, Dordrecht (2009)

    Book  Google Scholar 

  29. Hackbusch, W., Börm, S.: \({\cal H}^2\)-matrix approximation of integral operators by interpolation. Appl. Numer. Math. 43(1–2), 129–143 (2002). doi:10.1016/S0168-9274(02)00121-6 (19th Dundee Biennial Conference on Numerical Analysis)

  30. Hackbusch, W., Khoromskij, B., Sauter, S.A.: On \({\cal H}^2\)-matrices. In: Lectures on applied mathematics (Munich, 1999), pp. 9–29. Springer, Berlin (2000)

  31. Ho, K., Ying, L.: Hierarchical interpolative factorization for elliptic operators: differential equations. Tech. rep. (2013). arXiv:1307.2895 [math.NA]

  32. Ho, K.L., Greengard, L.: A fast direct solver for structured linear systems by recursive skeletonization. SIAM J. Sci. Comput. 34(5), A2507–A2532 (2012). doi:10.1137/120866683

  33. Horn, R.A., Johnson, C.R.: Matrix Analysis, 2nd edn. Cambridge University Press, Cambridge (2013)

    MATH  Google Scholar 

  34. Karniadakis, G., Sherwin, S.: Spectral/hp Element Methods for CFD. Oxford University Press, Oxford (1999)

    MATH  Google Scholar 

  35. Le Borne, S., Grasedyck, L.: \({\cal H}\)-matrix preconditioners in convection-dominated problems. SIAM J. Matrix Anal. Appl. 27(4), 1172–1183 (electronic) (2006). doi:10.1137/040615845

  36. Li, S., Gu, M., Wu, C.J., Xia, J.: New efficient and robust HSS Cholesky factorization of SPD matrices. SIAM J. Matrix Anal. Appl. 33(3), 886–904 (2012). doi:10.1137/110851110

  37. Lintner, M.: The eigenvalue problem for the 2D Laplacian in \({\cal H}\)- matrix arithmetic and application to the heat and wave equation. Computing 72(3–4), 293–323 (2004)

    MATH  MathSciNet  Google Scholar 

  38. Martinsson, P.G.: A fast direct solver for a class of elliptic partial differential equations. J. Sci. Comput. 38(3), 316–330 (2009). doi:10.1007/s10915-008-9240-6

  39. Schmitz, P.G., Ying, L.: A fast direct solver for elliptic problems on general meshes in 2D. J. Comput. Phys. 231(4), 1314–1338 (2012). doi:10.1016/j.jcp.2011.10.013

  40. Schwab, C.: \(p\)- and \(hp\)-finite element methods. Theory and applications in solid and fluid mechanics. Numerical Mathematics and Scientific Computation. The Clarendon Press, Oxford University Press, New York (1998)

  41. Scott, L.R., Zhang, S.: Finite element interpolation of nonsmooth functions satisfying boundary conditions. Math. Comput. 54(190), 483–493 (1990)

    Article  MATH  MathSciNet  Google Scholar 

  42. Xia, J.: Efficient structured multifrontal factorization for general large sparse matrices. SIAM J. Sci. Comput. 35(2), A832–A860 (2013). doi:10.1137/120867032

  43. Xia, J., Chandrasekaran, S., Gu, M., Li, X.S.: Superfast multifrontal method for large structured linear systems of equations. SIAM J. Matrix Anal. Appl. 31(3), 1382–1411 (2009). doi:10.1137/09074543X

Download references

Author information

Authors and Affiliations

  1. Institute for Analysis and Scientific Computing (Inst. E 101), Vienna University of Technology, Wiedner Hauptstrae 8-10, 1040 , Vienna, Austria

    Markus Faustmann, Jens Markus Melenk & Dirk Praetorius

Authors
  1. Markus Faustmann
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Jens Markus Melenk
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Dirk Praetorius
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Markus Faustmann.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Faustmann, M., Melenk, J.M. & Praetorius, D. \(\mathcal {H}\)-matrix approximability of the inverses of FEM matrices. Numer. Math. 131, 615–642 (2015). https://doi.org/10.1007/s00211-015-0706-9

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00211-015-0706-9

Mathematics Subject Classification

Search

Navigation