Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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

Request Permissions   Purchase Content 
 
 

 

Existence of $ \mathcal{H}$-matrix approximants to the inverses of BEM matrices: The simple-layer operator


Authors: Markus Faustmann, Jens Markus Melenk and Dirk Praetorius
Journal: Math. Comp. 85 (2016), 119-152
MSC (2010): Primary 65F05; Secondary 65N38, 65F30, 65F50
DOI: https://doi.org/10.1090/mcom/2990
Published electronically: June 18, 2015
MathSciNet review: 3404445
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We consider the question of approximating the inverse $ \mathbf W = \mathbf V^{-1}$ of the Galerkin stiffness matrix $ \mathbf V$ obtained by discretizing the simple-layer operator $ V$ with piecewise constant functions. The block partitioning of $ \mathbf W$ is assumed to satisfy any one of several standard admissibility criteria that are employed in connection with clustering algorithms to approximate the discrete BEM operator $ \mathbf V$. We show that $ \mathbf W$ can be approximated by blockwise low-rank matrices such that the error decays exponentially in the block rank employed. Similar exponential approximability results are shown for the Cholesky factorization of $ \mathbf V$.


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

  • [Beb00] Mario Bebendorf, Approximation of boundary element matrices, Numer. Math. 86 (2000), no. 4, 565-589. MR 1794343 (2001j:65022), https://doi.org/10.1007/PL00005410
  • [Beb05] M. Bebendorf, Hierarchical LU decomposition-based preconditioners for BEM, Computing 74 (2005), no. 3, 225-247. MR 2139414 (2005m:65056), https://doi.org/10.1007/s00607-004-0099-6
  • [Beb07] 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
  • [BG99] S. Börm and L. Grasedyck, H-Lib - a library for $ \mathcal {H}$- and $ \mathcal {H}^2$-matrices, available at http://www.hlib.org, 1999.
  • [BG04] Steffen Börm and Lars Grasedyck, Low-rank approximation of integral operators by interpolation, Computing 72 (2004), no. 3-4, 325-332. MR 2081826 (2005h:45017), https://doi.org/10.1007/s00607-003-0036-0
  • [BG05] Steffen Börm and Lars Grasedyck, Hybrid cross approximation of integral operators, Numer. Math. 101 (2005), no. 2, 221-249. MR 2195343 (2006m:65311), https://doi.org/10.1007/s00211-005-0618-1
  • [BH03] Mario Bebendorf and Wolfgang Hackbusch, Existence of $ \mathcal {H}$-matrix approximants to the inverse FE-matrix of elliptic operators with $ L^\infty $-coefficients, Numer. Math. 95 (2003), no. 1, 1-28. MR 1993936 (2004e:65128), https://doi.org/10.1007/s00211-002-0445-6
  • [Bör10a] Steffen Börm, Approximation of solution operators of elliptic partial differential equations by $ \mathcal {H}$- and $ \mathcal {H}^2$-matrices, Numer. Math. 115 (2010), no. 2, 165-193. MR 2606959 (2011c:65254), https://doi.org/10.1007/s00211-009-0278-7
  • [Bör10b] Steffen Börm, Efficient numerical methods for non-local operators, EMS Tracts in Mathematics, vol. 14, European Mathematical Society (EMS), Zürich, 2010. $ \mathcal {H}^2$-matrix compression, algorithms and analysis. MR 2767920 (2012i:65001)
  • [Bre99] 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
  • [CDGS10] S. Chandrasekaran, P. Dewilde, M. Gu, and N. Somasunderam, On the numerical rank of the off-diagonal blocks of Schur complements of discretized elliptic PDEs, SIAM J. Matrix Anal. Appl. 31 (2010), no. 5, 2261-2290. MR 2740619 (2011j:15023), https://doi.org/10.1137/090775932
  • [CMZ15] Eduardo Corona, Per-Gunnar Martinsson, and Denis Zorin, An $ O(N)$ direct solver for integral equations on the plane, Appl. Comput. Harmon. Anal. 38 (2015), no. 2, 284-317. MR 3303676, https://doi.org/10.1016/j.acha.2014.04.002
  • [DFG$^+$01] W. Dahmen, B. Faermann, I. G. Graham, W. Hackbusch, and S. A. Sauter, Inverse inequalities on non-quasi-uniform meshes and application to the mortar element method, Math. Comp. 73 (2004), no. 247, 1107-1138. MR 2047080 (2005d:65187), https://doi.org/10.1090/S0025-5718-03-01583-7
  • [FMP14] M. Faustmann, J. M. Melenk, and D. Praetorius, A new proof for existence of $ \mathcal {H}$-matrix approximants to the inverse of FEM matrices: the Dirichlet problem for the Laplacian, Spectral and High Order Methods for Partial Differential Equations - ICOSAHOM 2012, Springer Lect. Notes Comput. Sci. Eng. 95, 2014, pp. 249-259.
  • [FMP15a] M. Faustmann, J. M. Melenk, and D. Praetorius, Existence of $ \mathcal {H}$-matrix approximants to the inverses of BEM matrices: the hyper singular integral operator, ASC Report 08/2015), Institute for Analysis and Scientific Computing, Vienna University of Technology, Wien (2015) arXiv:1503.01943 [Math.MA].
  • [FMP15b] M. Faustmann, J. M. Melenk, and D. Praetorius, $ \mathcal {H}$-matrix approximability of the inverse of FEM matrices, to appear in Numer. Math. (2015), arXiv:1308.0499 [math.NA].
  • [GGMR09] Leslie Greengard, Denis Gueyffier, Per-Gunnar Martinsson, and Vladimir Rokhlin, Fast direct solvers for integral equations in complex three-dimensional domains, Acta Numer. 18 (2009), 243-275. MR 2506042 (2010e:65252), https://doi.org/10.1017/S0962492906410011
  • [GH03] 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
  • [GHK08] L. Grasedyck, W. Hackbusch, and R. Kriemann, Performance of $ {\mathcal {H}}{\text -}{\rm LU}$ preconditioning for sparse matrices, Comput. Methods Appl. Math. 8 (2008), no. 4, 336-349. MR 2604746 (2011h:65049), https://doi.org/10.2478/cmam-2008-0024
  • [GKLB08] Lars Grasedyck, Ronald Kriemann, and Sabine Le Borne, Parallel black box $ \mathcal {H}$-LU preconditioning for elliptic boundary value problems, Comput. Vis. Sci. 11 (2008), no. 4-6, 273-291. MR 2425496 (2009m:65056), https://doi.org/10.1007/s00791-008-0098-9
  • [GKLB09] Lars Grasedyck, Ronald Kriemann, and Sabine Le Borne, Domain decomposition based $ \mathcal {H}$-LU preconditioning, Numer. Math. 112 (2009), no. 4, 565-600. MR 2507619 (2010e:65200), https://doi.org/10.1007/s00211-009-0218-6
  • [GM13] A. Gillman and P. G. Martinsson, A direct solver with $ O(N)$ complexity for variable coefficient elliptic PDEs discretized via a high-order composite spectral collocation method, SIAM J. Sci. Comput. 36 (2014), no. 4, A2023-A2046. MR 3253692, https://doi.org/10.1137/130918988
  • [GR97] Leslie Greengard and Vladimir Rokhlin, A new version of the fast multipole method for the Laplace equation in three dimensions, Acta numerica, 1997, Acta Numer., vol. 6, Cambridge Univ. Press, Cambridge, 1997, pp. 229-269. MR 1489257 (99c:65012), https://doi.org/10.1017/S0962492900002725
  • [Gra01] L. Grasedyck, Theorie und Anwendungen Hierarchischer Matrizen, Ph.D. thesis, Universität Kiel, 2001.
  • [Gra05] L. Grasedyck, Adaptive recompression of $ \mathcal {H}$-matrices for BEM, Computing 74 (2005), no. 3, 205-223. MR 2139413 (2006e:65235), https://doi.org/10.1007/s00607-004-0103-1
  • [Hac99] 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
  • [Hac09] W. Hackbusch, Hierarchische Matrizen: Algorithmen und Analysis, Springer, 2009.
  • [HB02] W. Hackbusch and S. Börm, Data-sparse approximation by adaptive $ \mathcal {H}^2$-matrices, Computing 69 (2002), no. 1, 1-35. MR 1954142 (2004c:65155), https://doi.org/10.1007/s00607-002-1450-4
  • [HG12] Kenneth L. Ho and Leslie Greengard, A fast direct solver for structured linear systems by recursive skeletonization, SIAM J. Sci. Comput. 34 (2012), no. 5, A2507-A2532. MR 3023714, https://doi.org/10.1137/120866683
  • [HJ13] Roger A. Horn and Charles R. Johnson, Matrix Analysis, 2nd ed., Cambridge University Press, Cambridge, 2013. MR 2978290
  • [HK00a] W. Hackbusch and B. N. Khoromskij, A sparse $ \mathcal {H}$-matrix arithmetic: general complexity estimates, J. Comput. Appl. Math. 125 (2000), no. 1-2, 479-501. Numerical analysis 2000, Vol. VI, Ordinary differential equations and integral equations. MR 1803209 (2002f:65151), https://doi.org/10.1016/S0377-0427(00)00486-6
  • [HK00b] 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)
  • [HKS00] W. Hackbusch, B. Khoromskij, and S. A. Sauter, On $ \mathcal {H}^2$-matrices, Lectures on applied mathematics (Munich, 1999) Springer, Berlin, 2000, pp. 9-29. MR 1767761 (2001f:65034)
  • [HN89] W. Hackbusch and Z. P. Nowak, On the fast matrix multiplication in the boundary element method by panel clustering, Numer. Math. 54 (1989), no. 4, 463-491. MR 972420 (89k:65162), https://doi.org/10.1007/BF01396324
  • [HS93] Wolfgang Hackbusch and Stefan A. Sauter, On the efficient use of the Galerkin method to solve Fredholm integral equations, Proceedings of ISNA '92--International Symposium on Numerical Analysis, Part I (Prague, 1992), 1993, pp. 301-322. MR 1228511 (95c:65204)
  • [HW08] George C. Hsiao and Wolfgang L. Wendland, Boundary Integral Equations, Applied Mathematical Sciences, vol. 164, Springer-Verlag, Berlin, 2008. MR 2441884 (2009i:45001)
  • [HY13a] K.L. Ho and L. Ying, Hierarchical interpolative factorization for elliptic operators: differential equations, Tech. report, 2013, arXiv:1307.2895 [math.NA].
  • [HY13b] K.L. Ho and L. Ying, Hierarchical interpolative factorization for elliptic operators: integral equations, Tech. report, 2013, arXiv:1307.2666 [math.NA].
  • [LBG06] Sabine Le Borne and Lars Grasedyck, $ \mathcal {H}$-matrix preconditioners in convection-dominated problems, SIAM J. Matrix Anal. Appl. 27 (2006), no. 4, 1172-1183 (electronic). MR 2205618 (2007d:65033), https://doi.org/10.1137/040615845
  • [LGWX12] Shengguo Li, Ming Gu, Cinna Julie Wu, and Jianlin Xia, New efficient and robust HSS Cholesky factorization of SPD matrices, SIAM J. Matrix Anal. Appl. 33 (2012), no. 3, 886-904. MR 3023456, https://doi.org/10.1137/110851110
  • [Lin04] M. Lintner, The eigenvalue problem for the 2D Laplacian in $ \mathcal {H}$-matrix arithmetic and application to the heat and wave equation, Computing 72 (2004), no. 3-4, 293-323. MR 2081825 (2005j:65040), https://doi.org/10.1007/s00607-003-0061-z
  • [Mar09] Per-Gunnar Martinsson, A fast direct solver for a class of elliptic partial differential equations, J. Sci. Comput. 38 (2009), no. 3, 316-330. MR 2475654 (2010c:65041), https://doi.org/10.1007/s10915-008-9240-6
  • [McL00] William McLean, Strongly Elliptic Systems and Boundary Integral Equations, Cambridge University Press, Cambridge, 2000. MR 1742312 (2001a:35051)
  • [MR05] P. G. Martinsson and V. Rokhlin, A fast direct solver for boundary integral equations in two dimensions, J. Comput. Phys. 205 (2005), no. 1, 1-23. MR 2132300 (2005k:65292), https://doi.org/10.1016/j.jcp.2004.10.033
  • [Neč67] Jindřich Nečas, Les méthodes directes en théorie des équations elliptiques, Masson et Cie, Éditeurs, Paris; Academia, Éditeurs, Prague, 1967 (French). MR 0227584 (37 #3168)
  • [NH88] Z. P. Novak and W. Hackbusch, Complexity of the method of panels, Computational processes and systems, No. 6 (Russian), ``Nauka'', Moscow, 1988, pp. 233-244 (Russian). MR 982061 (90e:65193)
  • [Rat98] Andreas Rathsfeld, A wavelet algorithm for the boundary element solution of a geodetic boundary value problem, Comput. Methods Appl. Mech. Engrg. 157 (1998), no. 3-4, 267-287. Seventh Conference on Numerical Methods and Computational Mechanics in Science and Engineering (NMCM 96) (Miskolc). MR 1634292 (99d:86002), https://doi.org/10.1016/S0045-7825(97)00240-5
  • [Rat01] A. Rathsfeld, On a hierarchical three-point basis in the space of piecewise linear functions over smooth surfaces, Problems and methods in mathematical physics (Chemnitz, 1999) Oper. Theory Adv. Appl., vol. 121, Birkhäuser, Basel, 2001, pp. 442-470. MR 1847223 (2002f:65178)
  • [Riv74] Theodore J. Rivlin, The Chebyshev polynomials, Wiley-Interscience [John Wiley & Sons], New York-London-Sydney, 1974. Pure and Applied Mathematics. MR 0450850 (56 #9142)
  • [Rok85] V. Rokhlin, Rapid solution of integral equations of classical potential theory, J. Comput. Phys. 60 (1985), no. 2, 187-207. MR 805870 (86k:65120), https://doi.org/10.1016/0021-9991(85)90002-6
  • [Sau92] S.A. Sauter, Über die effiziente Verwendung des Galerkinverfahrens zur Lösung Fredholmscher Integralgleichungen, Ph.D. thesis, Universität Kiel, 1992.
  • [Sch97] J. Schöberl, NETGEN - An advancing front 2D/3D-mesh generator based on abstract rules, Comput. Visual. Sci (1997), no. 1, 41-52.
  • [Sch98] Reinhold Schneider, Multiskalen- und Wavelet-Matrixkompression, Advances in Numerical Mathematics, B. G. Teubner, Stuttgart, 1998 (German, with German summary). Analysisbasierte Methoden zur effizienten Lösung großer vollbesetzter Gleichungssysteme. [Analysis-based methods for the efficient solution of large nonsparse systems of equations]. MR 1623209 (99f:65067)
  • [Sch06] R. Schreittmiller, Zur Approximation der Lösungen elliptischer Systeme partieller Differentialgleichungen mittels Finiter Elemente und $ {\mathcal H}$-Matrizen, Ph.D. thesis, Technische Universität München, 2006.
  • [SS11] Stefan A. Sauter and Christoph Schwab, Boundary Element Methods, Springer Series in Computational Mathematics, vol. 39, Springer-Verlag, Berlin, 2011. Translated and expanded from the 2004 German original. MR 2743235 (2011i:65003)
  • [Ste08] Olaf Steinbach, Numerical Approximation Methods for Elliptic Boundary Value Problems, Finite and Boundary Elements, Springer, New York, 2008. Translated from the 2003 German original. MR 2361676 (2008i:65271)
  • [SY12] Phillip G. Schmitz and Lexing Ying, A fast direct solver for elliptic problems on general meshes in 2D, J. Comput. Phys. 231 (2012), no. 4, 1314-1338. MR 2876456, https://doi.org/10.1016/j.jcp.2011.10.013
  • [SZ90] L. Ridgway Scott and Shangyou Zhang, Finite element interpolation of nonsmooth functions satisfying boundary conditions, Math. Comp. 54 (1990), no. 190, 483-493. MR 1011446 (90j:65021), https://doi.org/10.2307/2008497
  • [Tau03] J. Tausch, Sparse BEM for potential theory and Stokes flow using variable order wavelets, Comput. Mech. 32 (2003), no. 4-6, 312-318. MR 2031264 (2004j:65202), https://doi.org/10.1007/s00466-003-0488-2
  • [TW03] Johannes Tausch and Jacob White, Multiscale bases for the sparse representation of boundary integral operators on complex geometry, SIAM J. Sci. Comput. 24 (2003), no. 5, 1610-1629. MR 1978152 (2004d:65151), https://doi.org/10.1137/S1064827500369451
  • [Tyr00] E. E. Tyrtyshnikov, Incomplete cross approximation in the mosaic-skeleton method, Computing 64 (2000), no. 4, 367-380. International GAMM-Workshop on Multigrid Methods (Bonn, 1998). MR 1783468 (2001h:65034), https://doi.org/10.1007/s006070070031
  • [vPSS97] Tobias von Petersdorff, Christoph Schwab, and Reinhold Schneider, Multiwavelets for second-kind integral equations, SIAM J. Numer. Anal. 34 (1997), no. 6, 2212-2227. MR 1480377 (98i:65110), https://doi.org/10.1137/S0036142994272957
  • [XCGL09] Jianlin Xia, Shivkumar Chandrasekaran, Ming Gu, and Xiaoye S. Li, Superfast multifrontal method for large structured linear systems of equations, SIAM J. Matrix Anal. Appl. 31 (2009), no. 3, 1382-1411. MR 2587783 (2011c:65072), https://doi.org/10.1137/09074543X
  • [Xia13] Jianlin Xia, Efficient structured multifrontal factorization for general large sparse matrices, SIAM J. Sci. Comput. 35 (2013), no. 2, A832-A860. MR 3035488, https://doi.org/10.1137/120867032

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 65F05, 65N38, 65F30, 65F50

Retrieve articles in all journals with MSC (2010): 65F05, 65N38, 65F30, 65F50


Additional Information

Markus Faustmann
Affiliation: Institute for Analysis and Scientific Computing (Inst. E 101), Vienna University of Technology, Wiedner Hauptstraße 8-10, 1040 Wien, Austria
Email: markus.faustmann@tuwien.ac.at

Jens Markus Melenk
Affiliation: Institute for Analysis and Scientific Computing (Inst. E 101), Vienna University of Technology, Wiedner Hauptstraße 8-10, 1040 Wien, Austria
Email: melenk@tuwien.ac.at

Dirk Praetorius
Affiliation: Institute for Analysis and Scientific Computing (Inst. E 101), Vienna University of Technology, Wiedner Hauptstraße 8-10, 1040 Wien, Austria
Email: dirk.praetorius@tuwien.ac.at

DOI: https://doi.org/10.1090/mcom/2990
Received by editor(s): November 20, 2013
Received by editor(s) in revised form: July 28, 2014, and August 11, 2014
Published electronically: June 18, 2015
Dedicated: Dedicated to Wolfgang Hackbusch on the occasion of his 65th birthday
Article copyright: © Copyright 2015 American Mathematical Society

American Mathematical Society