Existence of ℋ-matrix approximants to the inverses of BEM matrices: The simple-layer operator

Faustmann, Markus; Melenk, Jens; Praetorius, Dirk

doi:10.1090/mcom/2990

Existence of $\mathcal {H}$-matrix approximants to the inverses of BEM matrices: The simple-layer operator
HTML articles powered by AMS MathViewer

by Markus Faustmann, Jens Markus Melenk and Dirk Praetorius PDF

Math. Comp. 85 (2016), 119-152 Request permission

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

Mario Bebendorf, Approximation of boundary element matrices, Numer. Math. 86 (2000), no. 4, 565–589. MR 1794343, DOI 10.1007/PL00005410
M. Bebendorf, Hierarchical LU decomposition-based preconditioners for BEM, Computing 74 (2005), no. 3, 225–247. MR 2139414, DOI 10.1007/s00607-004-0099-6
Mario Bebendorf, Why finite element discretizations can be factored by triangular hierarchical matrices, SIAM J. Numer. Anal. 45 (2007), no. 4, 1472–1494. MR 2338396, DOI 10.1137/060669747
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.
Steffen Börm and Lars Grasedyck, Low-rank approximation of integral operators by interpolation, Computing 72 (2004), no. 3-4, 325–332. MR 2081826, DOI 10.1007/s00607-003-0036-0
Steffen Börm and Lars Grasedyck, Hybrid cross approximation of integral operators, Numer. Math. 101 (2005), no. 2, 221–249. MR 2195343, DOI 10.1007/s00211-005-0618-1
Mario Bebendorf and Wolfgang Hackbusch, Existence of $\scr 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, DOI 10.1007/s00211-002-0445-6
Steffen Börm, Approximation of solution operators of elliptic partial differential equations by $\scr H$- and $\scr H^2$-matrices, Numer. Math. 115 (2010), no. 2, 165–193. MR 2606959, DOI 10.1007/s00211-009-0278-7
Steffen Börm, Efficient numerical methods for non-local operators, EMS Tracts in Mathematics, vol. 14, European Mathematical Society (EMS), Zürich, 2010. $\scr H^2$-matrix compression, algorithms and analysis. MR 2767920, DOI 10.4171/091
Susanne C. Brenner, The condition number of the Schur complement in domain decomposition, Numer. Math. 83 (1999), no. 2, 187–203. MR 1712684, DOI 10.1007/s002110050446
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, DOI 10.1137/090775932
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, DOI 10.1016/j.acha.2014.04.002
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, DOI 10.1090/S0025-5718-03-01583-7
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.
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].
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].
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, DOI 10.1017/S0962492906410011
Lars Grasedyck and Wolfgang Hackbusch, Construction and arithmetics of $\scr H$-matrices, Computing 70 (2003), no. 4, 295–334. MR 2011419, DOI 10.1007/s00607-003-0019-1
L. Grasedyck, W. Hackbusch, and R. Kriemann, Performance of ${\scr H}{\text -}\textrm {Lu}$ preconditioning for sparse matrices, Comput. Methods Appl. Math. 8 (2008), no. 4, 336–349. MR 2604746, DOI 10.2478/cmam-2008-0024
Lars Grasedyck, Ronald Kriemann, and Sabine Le Borne, Parallel black box $\scr H$-LU preconditioning for elliptic boundary value problems, Comput. Vis. Sci. 11 (2008), no. 4-6, 273–291. MR 2425496, DOI 10.1007/s00791-008-0098-9
Lars Grasedyck, Ronald Kriemann, and Sabine Le Borne, Domain decomposition based $\scr H$-LU preconditioning, Numer. Math. 112 (2009), no. 4, 565–600. MR 2507619, DOI 10.1007/s00211-009-0218-6
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, DOI 10.1137/130918988
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, DOI 10.1017/S0962492900002725
L. Grasedyck, Theorie und Anwendungen Hierarchischer Matrizen, Ph.D. thesis, Universität Kiel, 2001.
L. Grasedyck, Adaptive recompression of $\scr H$-matrices for BEM, Computing 74 (2005), no. 3, 205–223. MR 2139413, DOI 10.1007/s00607-004-0103-1
W. Hackbusch, A sparse matrix arithmetic based on $\scr H$-matrices. I. Introduction to $\scr H$-matrices, Computing 62 (1999), no. 2, 89–108. MR 1694265, DOI 10.1007/s006070050015
W. Hackbusch, Hierarchische Matrizen: Algorithmen und Analysis, Springer, 2009.
W. Hackbusch and S. Börm, Data-sparse approximation by adaptive $\scr H^2$-matrices, Computing 69 (2002), no. 1, 1–35. MR 1954142, DOI 10.1007/s00607-002-1450-4
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, DOI 10.1137/120866683
Roger A. Horn and Charles R. Johnson, Matrix analysis, 2nd ed., Cambridge University Press, Cambridge, 2013. MR 2978290
W. Hackbusch and B. N. Khoromskij, A sparse $\scr 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, DOI 10.1016/S0377-0427(00)00486-6
W. Hackbusch and B. N. Khoromskij, A sparse $\scr H$-matrix arithmetic. II. Application to multi-dimensional problems, Computing 64 (2000), no. 1, 21–47. MR 1755846, DOI 10.1007/PL00021408
W. Hackbusch, B. Khoromskij, and S. A. Sauter, On $\scr H^2$-matrices, Lectures on applied mathematics (Munich, 1999) Springer, Berlin, 2000, pp. 9–29. MR 1767761
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, DOI 10.1007/BF01396324
Wolfgang Hackbush 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
George C. Hsiao and Wolfgang L. Wendland, Boundary integral equations, Applied Mathematical Sciences, vol. 164, Springer-Verlag, Berlin, 2008. MR 2441884, DOI 10.1007/978-3-540-68545-6
K.L. Ho and L. Ying, Hierarchical interpolative factorization for elliptic operators: differential equations, Tech. report, 2013, arXiv:1307.2895 [math.NA].
K.L. Ho and L. Ying, Hierarchical interpolative factorization for elliptic operators: integral equations, Tech. report, 2013, arXiv:1307.2666 [math.NA].
Sabine Le Borne and Lars Grasedyck, $\scr H$-matrix preconditioners in convection-dominated problems, SIAM J. Matrix Anal. Appl. 27 (2006), no. 4, 1172–1183. MR 2205618, DOI 10.1137/040615845
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, DOI 10.1137/110851110
M. Lintner, The eigenvalue problem for the 2D Laplacian in $\scr H$-matrix arithmetic and application to the heat and wave equation, Computing 72 (2004), no. 3-4, 293–323. MR 2081825, DOI 10.1007/s00607-003-0061-z
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, DOI 10.1007/s10915-008-9240-6
William McLean, Strongly elliptic systems and boundary integral equations, Cambridge University Press, Cambridge, 2000. MR 1742312
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, DOI 10.1016/j.jcp.2004.10.033
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
Z. P. Novak and U. Khakbush, Complexity of the method of panels, Computational processes and systems, No. 6 (Russian), “Nauka”, Moscow, 1988, pp. 233–244 (Russian). MR 982061
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, DOI 10.1016/S0045-7825(97)00240-5
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
Theodore J. Rivlin, The Chebyshev polynomials, Pure and Applied Mathematics, Wiley-Interscience [John Wiley & Sons], New York-London-Sydney, 1974. MR 0450850
V. Rokhlin, Rapid solution of integral equations of classical potential theory, J. Comput. Phys. 60 (1985), no. 2, 187–207. MR 805870, DOI 10.1016/0021-9991(85)90002-6
S.A. Sauter, Über die effiziente Verwendung des Galerkinverfahrens zur Lösung Fredholmscher Integralgleichungen, Ph.D. thesis, Universität Kiel, 1992.
J. Schöberl, NETGEN - An advancing front 2D/3D-mesh generator based on abstract rules, Comput. Visual. Sci (1997), no. 1, 41–52.
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, DOI 10.1007/978-3-663-10851-1
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.
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, DOI 10.1007/978-3-540-68093-2
Olaf Steinbach, Numerical approximation methods for elliptic boundary value problems, Springer, New York, 2008. Finite and boundary elements; Translated from the 2003 German original. MR 2361676, DOI 10.1007/978-0-387-68805-3
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, DOI 10.1016/j.jcp.2011.10.013
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, DOI 10.1090/S0025-5718-1990-1011446-7
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, DOI 10.1007/s00466-003-0488-2
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, DOI 10.1137/S1064827500369451
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, DOI 10.1007/s006070070031
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, DOI 10.1137/S0036142994272957
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, DOI 10.1137/09074543X
Jianlin Xia, Efficient structured multifrontal factorization for general large sparse matrices, SIAM J. Sci. Comput. 35 (2013), no. 2, A832–A860. MR 3035488, DOI 10.1137/120867032