Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

On the spectral equivalence of hierarchical matrix preconditioners for elliptic problems


Authors: M. Bebendorf, M. Bollhöfer and M. Bratsch
Journal: Math. Comp. 85 (2016), 2839-2861
MSC (2010): Primary 65F08, 65F50, 65N30
DOI: https://doi.org/10.1090/mcom/3086
Published electronically: March 28, 2016
MathSciNet review: 3522972
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We will discuss the spectral equivalence of hierarchical matrix approximations for second order elliptic problems. Our theory will show that a modified variant of the hierarchical matrix Cholesky decomposition which preserves test vectors while truncating blocks to lower rank will lead to a spectrally equivalent approximation when using an adapted truncation threshold. Our theory also covers the usual hierarchical Cholesky decomposition which does not preserve test vectors but expects a significantly more restrictive threshold adaption to obtain a spectrally equivalent approximation. Numerical experiments indicate that the adaption of the truncation parameter seems to be necessary for the traditional hierarchical Cholesky preconditioner to obtain mesh-independent convergence while the variant which preserves test vectors works in practice quite well even with a fixed parameter.


References [Enhancements On Off] (What's this?)

  • [1] Owe Axelsson, Iterative Solution Methods, Cambridge University Press, Cambridge, 1994. MR 1276069 (95f:65005)
  • [2] M. Bebendorf, A note on the Poincaré inequality for convex domains, Z. Anal. Anwendungen 22 (2003), no. 4, 751-756. MR 2036927 (2004k:26025), https://doi.org/10.4171/ZAA/1170
  • [3] Mario Bebendorf, Efficient inversion of the Galerkin matrix of general second-order elliptic operators with nonsmooth coefficients, Math. Comp. 74 (2005), no. 251, 1179-1199 (electronic). MR 2136998 (2006b:65161), https://doi.org/10.1090/S0025-5718-04-01716-8
  • [4] Mario Bebendorf, Why finite element discretizations can be factored by triangular hierarchical matrices, SIAM J. Numer. Anal. 45 (2007), no. 4, 1472-1494 (electronic). MR 2338396 (2009f:65244), https://doi.org/10.1137/060669747
  • [5] Mario Bebendorf, Hierarchical Matrices, A Means to Efficiently Solve Elliptic Boundary Value Problems, Lecture Notes in Computational Science and Engineering, vol. 63, Springer-Verlag, Berlin, 2008. MR 2451321 (2009k:15001)
  • [6] M. Bebendorf, M. Bollhöfer, and M. Bratsch, Hierarchical matrix approximation with blockwise constraints, BIT 53 (2013), no. 2, 311-339. MR 3123848
  • [7] M. Bebendorf and T. Fischer, On the purely algebraic data-sparse approximation of the inverse and the triangular factors of sparse matrices, Numer. Linear Algebra Appl. 18 (2011), no. 1, 105-122. MR 2769036 (2011k:65042), https://doi.org/10.1002/nla.714
  • [8] Susanne C. Brenner, The condition number of the Schur complement in domain decomposition, Numer. Math. 83 (1999), no. 2, 187-203. MR 1712684 (2000g:65114), https://doi.org/10.1007/s002110050446
  • [9] M. Faustmann, J. M. Melenk, and D. Praetorius,
    $ \mathcal {H}$-matrix approximability of the inverse of FEM matrices,
    Technical report, Institute for Analysis and Scientific Computing, 2013.
  • [10] K. Giebermann, Multilevel approximation of boundary integral operators, Computing 67 (2001), no. 3, 183-207. MR 1872653 (2002m:65128), https://doi.org/10.1007/s006070170005
  • [11] Lars Grasedyck and Wolfgang Hackbusch, Construction and arithmetics of $ \mathcal {H}$-matrices, Computing 70 (2003), no. 4, 295-334. MR 2011419 (2004i:65035), https://doi.org/10.1007/s00607-003-0019-1
  • [12] W. Hackbusch,
    Multi-grid Methods and Applications, volume 4 of Springer Series in Computational Mathematics.
    Springer, Berlin [u.a.], 1985.
  • [13] W. Hackbusch, A sparse matrix arithmetic based on $ \mathcal {H}$-matrices. I. Introduction to $ \mathcal {H}$-matrices, Computing 62 (1999), no. 2, 89-108. MR 1694265 (2000c:65039), https://doi.org/10.1007/s006070050015
  • [14] W. Hackbusch.
    Hierarchische Matrizen.
    Springer-Verlag, 2009.
  • [15] W. Hackbusch and B. N. Khoromskij, A sparse $ \mathcal {H}$-matrix arithmetic. II. Application to multi-dimensional problems, Computing 64 (2000), no. 1, 21-47. MR 1755846 (2001i:65053)
  • [16] Yair Shapira, Matrix-based Multigrid, Theory and Applications, Numerical Methods and Algorithms, vol. 2, Kluwer Academic Publishers, Boston, MA, 2003. Theory and applications. MR 2011771 (2004g:65002)
  • [17] U. Trottenberg, C.W. Oosterlee, and A. Schüller,
    Multigrid: Basics, Parallelism and Adaptivity,
    Academic Press, 2000.
  • [18] Petr Vaněk, Marian Brezina, and Jan Mandel, Convergence of algebraic multigrid based on smoothed aggregation, Numer. Math. 88 (2001), no. 3, 559-579. MR 1835471 (2002c:65230), https://doi.org/10.1007/s211-001-8015-y

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 65F08, 65F50, 65N30

Retrieve articles in all journals with MSC (2010): 65F08, 65F50, 65N30


Additional Information

M. Bebendorf
Affiliation: Department of Mathematics, University of Bayreuth, Germany
Email: mario.bebendorf@uni-bayreuth.de

M. Bollhöfer
Affiliation: Institute for Computational Mathematics, TU Brunswick, Germany

M. Bratsch
Affiliation: formerly Institute for Numerical Simulation, University of Bonn, Germany

DOI: https://doi.org/10.1090/mcom/3086
Keywords: Approximate LU decomposition, preconditioning, hierarchical matrices
Received by editor(s): August 13, 2014
Received by editor(s) in revised form: April 28, 2015
Published electronically: March 28, 2016
Additional Notes: This work was supported by DFG collaborative research center SFB 611
Article copyright: © Copyright 2016 American Mathematical Society

American Mathematical Society