[go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

\(\mathcal H\)-FAINV: hierarchically factored approximate inverse preconditioners

  • S.I.: EMG 2014
  • Published:
Computing and Visualization in Science

Abstract

Given a sparse matrix, its LU-factors, inverse and inverse factors typically suffer from substantial fill-in, leading to non-optimal complexities in their computation as well as their storage. In the past, several computationally efficient methods have been developed to compute approximations to these otherwise rather dense matrices. Many of these approaches are based on approximations through sparse matrices, leading to well-known ILU, sparse approximate inverse or factored sparse approximate inverse techniques and their variants. A different approximation approach is based on blockwise low rank approximations and is realized, for example, through hierarchical (\(\mathcal H\)-) matrices. While \(\mathcal H\)-inverses and \(\mathcal H\)-LU factors have been discussed in the literature, this paper will consider the construction of an approximation of the factored inverse through \(\mathcal H\)-matrices (\(\mathcal H\)-FAINV). We will describe a blockwise approach that permits to replace (exact) matrix arithmetic through approximate efficient \(\mathcal H\)-arithmetic. We conclude with numerical results in which we use approximate factored inverses as preconditioners in the iterative solution of the discretized convection–diffusion problem.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

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
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12

Similar content being viewed by others

References

  1. Bangerth, W., Hartmann, R., Kanschat, G.: deal.II—a general purpose object oriented finite element library. ACM Trans. Math. Softw. 33(4), 24/1–24/27 (2007)

    Article  MathSciNet  Google Scholar 

  2. Bangerth, W., Heister, T., Heltai, L., Kanschat, G., Kronbichler, M., Maier, M., Turcksin, B., Young, T.D.: The deal.ii library, version 8.1. arXiv:1312.2266v4 (preprint) (2013)

  3. Bebendorf, M.: Hierarchical matrices. In: A Means to Efficiently Solve Elliptic Boundary Value Problems. Lecture Notes in Computational Science and Engineering, vol. 63. Springer (2008)

  4. Benzi, M.: Preconditioning techniques for large linear systems: a survey. J. Comput. Phys. 182, 418–477 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  5. Benzi, M., Meyer, C., Tuma, M.: A sparse approximate inverse preconditioner for the conjugate gradient method. SIAM J. Sci. Comput. 17, 1135–1149 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  6. Benzi, M., Tuma, M.: A sparse approximate inverse preconditioner for nonsymmetric linear systems. SIAM J. Sci. Comput. 19, 968–994 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  7. Benzi, M., Tuma, M.: A comparative study of sparse approximate inverse preconditioners. Appl. Numer. Methods 30, 305–340 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  8. Benzi, M., Tuma, M.: Orderings for factorized sparse approximate inverse preconditioners. SIAM J. Sci. Comput. 21, 1851–1868 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  9. Börm, S.: \({\cal {H}}^2\)-matrix arithmetics in linear complexity. Computing 77, 1–28 (2006)

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  11. Börm, S., Grasedyck, L.: HLIB version 1.3. www.hlib.org

  12. Börm, S., Grasedyck, L., Hackbusch, W.: Hierarchical matrices. Lecture Notes No. 21, Max-Planck-Institute for Mathematics in the Sciences, Leipzig, Germany (2003)

  13. Bridson, R., Tang, W.P.: Ordering, anisotropy and factored sparse approximate inverses. SIAM J. Sci. Comput. 21, 867–882 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  14. Bru, R., Marin, J., Mas, J., Tuma, M.: Balanced incomplete factorization. SIAM J. Sci. Comput. 30, 2302–2318 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  15. Byckling, M., Huhtanen, M.: Preconditioning with direct approximate factoring of the inverse. SIAM J. Sci. Comput. 36, A88–A104 (2014)

  16. Duff, I.S., Erisman, A.M., Gear, C.W., Reid, J.K.: Sparsity structure and gaussian elimination. SIGNUM Newsl. 23, 2–8 (1988)

    Article  Google Scholar 

  17. Faustmann, M., Melenk, J.M., Praetorius, D.: H-matrix approximability of the inverse of FEM matrices. Numer. Math. (2015). doi:10.1007/s00211-015-0706-9

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

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  21. Hackbusch, W.: Hierarchische Matrizen. Springer, Berlin (2009). (in German, English (revised) edition to appear in 2015)

    Book  MATH  Google Scholar 

  22. Kolotilina, Y., Yeremin, Y.: Factorized sparse approximate inverse preconditionings I. theory. SIAM J. Matrix Anal. Appl. 14, 45–58 (1993)

    Article  MathSciNet  MATH  Google Scholar 

  23. Kriemann, R.: \(\cal {H}\)-LU factorization on many-core systems. Tech. Rep. MIS-Preprint 5/2014, Max Planck Institute for Mathematics in the Sciences (2014)

  24. Saad, Y.: Iterative Methods for Sparse Linear Systems. SIAM, Bangkok (2003)

    Book  MATH  Google Scholar 

  25. Wang, S., Li, X.S., Xia, J., Situ, Y., de Hoop, M.V.: Efficient scalable algorithms for solving dense linear systems with hierarchically semiseparable structures. SIAM J. Sci. Comput. 35, C519–C544 (2013)

    Article  MATH  Google Scholar 

  26. Xia, J., Chandrasekaran, S., Gu, M., Li, X.S.: Fast algorithms for hierarchically semiseparable matrices. Numer. Linear Algebra Appl. 17, 953–976 (2010)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Max Planck Institute for Mathematics in the Sciences, Inselstr. 22, 04103, Leipzig, Germany

    R. Kriemann

  2. Hamburg University of Technology, Am Schwarzenberg-Campus 3, 21073, Hamburg, Germany

    S. Le Borne

Authors
  1. R. Kriemann
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. S. Le Borne
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to S. Le Borne.

Additional information

Communicated by: Artem Napov, Yvan Notay, and Stefan Vandewalle.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Kriemann, R., Le Borne, S. \(\mathcal H\)-FAINV: hierarchically factored approximate inverse preconditioners. Comput. Visual Sci. 17, 135–150 (2015). https://doi.org/10.1007/s00791-015-0254-y

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00791-015-0254-y

Keywords