Skip to main content
SpringerLink
Log in

Finite-element based sparse approximate inverses for block-factorized preconditioners

  • Published:
Advances in Computational Mathematics Aims and scope Submit manuscript

Abstract

In this work we analyse a method to construct numerically efficient and computationally cheap sparse approximations of some of the matrix blocks arising in the block-factorized preconditioners for matrices with a two-by-two block structure. The matrices arise from finite element discretizations of partial differential equations. We consider scalar elliptic problems, however the approach is appropriate also for other types of problems such as parabolic problems or systems of equations. The technique is applicable for both selfadjoint and non-selfadjoint problems, in two as well as in three space dimensions. We analyse in detail the two-dimensional case and provide extensive numerical evidence for the efficiency of the proposed matrix approximations, both serial and parallel. Two- and three-dimensional tests are included.

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

Similar content being viewed by others

References

  1. Axelsson, O.: Notes on the numerical solution of the biharmonic equation IMA J. Appl. Math. 11, 213–226 (1972)

    Article  MathSciNet  Google Scholar 

  2. Axelsson, O.: Iterative Solution Methods. Cambridge University Press (1994)

  3. Axelsson, O.: Stabilization of algebraic multilevel iteration methods; additive methods. Numer. Algorithms 21, 23–47 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  4. Axelsson, O., Barker, V.A.: Finite Element Solution of Boundary Value Problems. Theory and Computation. Academic (1984)

  5. Axelsson, O., Blaheta, R.: Two simple derivations of universal bounds for the C.B.S inequality constant. Appl. Math. 49, 57–72 (2001)

    Article  MathSciNet  Google Scholar 

  6. Axelsson, O., Blaheta, R., Neytcheva, M.: Preconditioning of boundary value problems using elementwise Schur complements. SIAM J. Matrix Anal. Appl. 31, 767–789 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  7. Axelsson, O., Eijkhout, V.: The nested recursive two-level factorization method for nine-point difference matrices. SIAM J. Stat. Sci. Comput. 12, 1373–1400 (1991)

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  9. Axelsson, O., Neytcheva, M.: Preconditioning methods for linear systems arising in constrained optimization problems. Numer. Linear. Algebr. Appl. 10, 3–31 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  10. Axelsson, O., Neytcheva, M.: A general approach to analyse preconditioners for two-bytwo block matrices. TR 2010-029, Institute for Information Technology, Uppsala University. http://www.it.uu.se/research/publications/reports/2010-029/2010-029-nc.pdf (2010). Accessed 19 July 2011

  11. Axelsson, O., Padiy, A.: On the additive version of the algebraic multilevel iteration method for anisotropic elliptic problems. SIAM J. Sci. Comput. 20, 1807–1830 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  12. Axelsson, O., Vassilevski, P.S.: Algebraic multilevel preconditioning methods I. Numer. Math. 56, 157–177 (1989)

    Article  MathSciNet  MATH  Google Scholar 

  13. Axelsson, O., Vassilevski, P.S.: Algebraic multilevel preconditioning methods II. SIAM J. Numer. Anal. 2, 1569–1590 (1990)

    Article  MathSciNet  Google Scholar 

  14. Axelsson, O., Vassilevski, P.S.: Variable-step multilevel preconditioning methods, I: self-adjoint and positive definite elliptic problems. Numer. 4(1), 75–101 (1994)

    MathSciNet  Google Scholar 

  15. Bank, R.E., Welfert, B.D., Yserentant, H.: A class of iterative methods for solving saddle point problems. Numer. Math. 56, 645–666 (1990)

    Article  MathSciNet  MATH  Google Scholar 

  16. Benzi, M., Golub, G.H., Liesen, J.: Numerical solution of saddle point problems. Acta Numer. 14, 1–137 (2005)

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  18. Bhatia, R.: Matrix Analysis. Springer, New York (1997)

    Google Scholar 

  19. Bollhofer, M., Mehrmann, V.: Algebraic multilevel methods and sparse approximate inverses. SIAM J. Matrix Anal. Appl. 24, 191–218 (2002)

    Article  MathSciNet  Google Scholar 

  20. Botta, E.F.F., Wubs, F.W.: Matrix renumbering ILU: an effective algebraic multilevel ILU preconditioner for sparse matrices. SIAM J. Matrix Anal. Appl. 20, 1007–1026 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  21. Bängtsson, E., Lund, B.: A comparison between two solution techniques to solve the equations of glacial rebound for an elastic Earth. Int. J. Numer. Methods Eng. 75, 479–502 (2008)

    Article  MATH  Google Scholar 

  22. Chow, E., Saad,Y.: Approximate inverse techniques for block-partitioned matrices. SIAM J. Sci. Comput. 18, 1657–1675 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  23. Cosgrove, J.D.F., Díaz, J.C., Griewank, A.: Approximate inverse preconditionings for sparse linear systems. Int. J. Comput. Math. 44, 91–110 (1992)

    Article  MATH  Google Scholar 

  24. Fried, I.: Bounds on the spectral and maximum norms of the finite element stiffness, flexibility and mass matrices. Int. J. Solids Struct. 9, 1013–1034 (1973)

    Article  MathSciNet  MATH  Google Scholar 

  25. Grote, M., Huckle, T.: Parallel preconditioning with sparse approximate inverses. SIAM J. Sci. Comput. 18, 838–853 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  26. Huckle, T.: Approximate sparsity patterns for the inverse of a matrix and preconditioning. Appl. Numer. Math. 30, 291–303 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  27. Kaporin, I.E.: New convergence results and preconditioning strategies for the conjugate gradient method. Numer. Linear. Algebr. Appl. 1, 179–210 (1994)

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  29. Kraus, J.K.: Algebraic multilevel preconditioning of finite element matrices using local Schur complements. Numer. Linear. Algebr. Appl. 13, 49–70 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  30. Linnér, E.: Sparse approximate inverses in a Finite Element framework. M.Sc. thesis, Institute of Information technology, Uppsala University (2009)

  31. Neytcheva, M.: On element-by-element Schur complement approximations. Linear Algebra Appl. 434, 2308–2324 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  32. Neytcheva, M., Bängtsson, E.: Preconditioning of nonsymmetric saddle point systems as arising in modelling of visco-elastic problems. ETNA 29, 193–211 (2008)

    Google Scholar 

  33. Neytcheva, M., Bängtsson, E., E. Linnér E.: Finite-element based sparse approximate inverses for block-factorized preconditioners. TR 2010-010, Institute for Information Technology, Uppsala University (2010)

  34. Notay, Y.: Optimal V-cycle algebraic multilevel preconditioning. Numer. Linear. Algebr. Appl. 5, 441–459 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  35. Notay, Y.: Using approximate inverses in algebraic multilevel methods. Numer. Math. 80, 397–417 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  36. Notay, Y.: Robust parameter-free algebraic multilevel preconditioning. Numer. Linear. Algebr. Appl. 9, 409–428 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  37. Saad, Y.: Multilevel ILU with reorderings for diagonal dominance.SIAM J. Sci. Comput. 27, 1032–1057 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  38. Saad, Y., Suchomel, B.: ARMS: an algebraic recursive multilevel solver for general sparse linear systems. Numer. Linear. Algebr. Appl. 9, 359–378 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  39. Tang, W.P., Wan, W.-L.: Sparse approximate inverse smoother for multigrid. SIAM J. Matrix Anal. Appl. 21, 1236–1252 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  40. Vassilevski, P.S.: Multilevel Block Factorization Preconditioners. Springer, New York (2008)

    MATH  Google Scholar 

  41. Wathen, A.J.: Realistic eigenvalue bounds for the Galerkin mass matrix. IMA J. Numer. Anal. 7, 449–457 (1987)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Information Technology, Uppsala University, Box 337, 751 05, Uppsala, Sweden

    Maya Neytcheva & Erik Bängtsson

  2. Centre for Image Analysis, Uppsala University, Box 337, 751 05, Uppsala, Sweden

    Elisabeth Linnér

Authors
  1. Maya Neytcheva
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Erik Bängtsson
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Elisabeth Linnér
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Maya Neytcheva.

Additional information

Communicated by Juan Manuel Peña.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Neytcheva, M., Bängtsson, E. & Linnér, E. Finite-element based sparse approximate inverses for block-factorized preconditioners. Adv Comput Math 35, 323–355 (2011). https://doi.org/10.1007/s10444-011-9176-5

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10444-011-9176-5

Keywords

Mathematics Subject Classifications (2010)

Search

Navigation