\(\mathcal {H}\) -matrix approximability of the inverses of FEM matrices

详细信息    查看全文

• 作者：Markus Faustmann ; Jens Markus Melenk ; Dirk Praetorius
• 关键词：65F05 ; 65N30 ; 65F30 ; 65F50
• 刊名：Numerische Mathematik
• 出版年：2015
• 出版时间：December 2015
• 年：2015
• 卷：131
• 期：4
• 页码：615-642
• 全文大小：735 KB
• 参考文献：1.Adams, R.A.: Sobolev spaces, Pure and Applied Mathematics, vol. 65. Academic Press, New York (1975)
  2.Bebendorf, M.: Hierarchical LU decomposition-based preconditioners for BEM. Computing 74(3), 225-47 (2005)MATH MathSciNet CrossRef
  3.Bebendorf, M.: Why finite element discretizations can be factored by triangular hierarchical matrices. SIAM J. Numer. Anal. 45(4), 1472-494 (2007)MATH MathSciNet CrossRef
  4.Bebendorf, M., Hackbusch, W.: Existence of \(\cal {H}\) -matrix approximants to the inverse FE-matrix of elliptic operators with \(L^{\infty }\) -coefficients. Numer. Math. 95(1), 1-8 (2003)MATH MathSciNet CrossRef
  5.Bennighof, J.K., Lehoucq, R.B.: An automated multilevel substructuring method for eigenspace computation in linear elastodynamics. SIAM J. Sci. Comput. 25(6), 2084-106 (electronic) (2004). doi:10.-137/?S106482750240065-
  6.B?rm, S.: Approximation of solution operators of elliptic partial differential equations by \(\cal {H}\) - and \({\cal {H}}^2\) -matrices. Numer. Math. 115(2), 165-93 (2010)MATH MathSciNet CrossRef
  7.B?rm, S.: Efficient Numerical Methods for Non-local Operators, EMS Tracts in Mathematics, vol. 14. European Mathematical Society (EMS), Zürich (2010)CrossRef
  8.B?rm, S., Grasedyck, L.: H-Lib—a library for \(\cal {H}\) -and \({\cal {H}}^2\) -matrices. http://?www.?hlib.?org (1999)
  9.Brenner, S., Scott, L.: The Mathematical Theory of Finite Element Methods, Texts in Applied Mathematics, vol. 15. Springer, New York (2002)CrossRef
  10.Brenner, S.C.: The condition number of the Schur complement in domain decomposition. Numer. Math. 83(2), 187-03 (1999)MATH MathSciNet CrossRef
  11.Chandrasekaran, S., Dewilde, P., Gu, M., Somasunderam, N.: On the numerical rank of the off-diagonal blocks of Schur complements of discretized elliptic PDEs. SIAM J. Matrix Anal. Appl. 31(5), 2261-290 (2010). doi:10.-137/-90775932
  12.Dahmen, W., Faermann, B., Graham, I.G., Hackbusch, W., Sauter, S.A.: Inverse inequalities on non-quasiuniform meshes and application to the mortar element method. Math. Comput. 73, 1107-138 (2001)MathSciNet CrossRef
  13.Demkowicz, L., Kurtz, J., Pardo, D., Paszyński, M., Rachowicz, W., Zdunek, A.: Computing with \(hp\) -adaptive finite elements, vol. 2. Chapman & Hall/CRC Applied Mathematics and Nonlinear Science Series, Frontiers: three dimensional elliptic and Maxwell problems with applications. Chapman & Hall/CRC, Boca Raton (2008)
  14.Ern, A., Guermond, J.L.: Evaluation of the condition number in linear systems arising in finite element approximations. M2AN Math. Model. Numer. Anal. 40(1), 29-8 (2006)MATH MathSciNet CrossRef
  15.Faustmann, M.: \({\cal {H}}\) -matrix approximantion of inverses of FEM and BEM matrices. doctoral thesis, work in progress, Vienna (2015)
  16.Faustmann, M., Melenk, J.M., Praetorius, D.: Existence of \({\cal {H}}\) -matrix approximation to the inverse of BEM matrices: the simple layer operator. Institute for Analysis and Scientific Computing, Vienna University of Technology, Wien, Tech. Rep. in preparation (2013)
  17.Faustmann, M., Melenk, J.M., Praetorius, D.: Existence of \({\cal {H}}\) -matrix approximants to the inverses of BEM matrices: the hyper singular integral operator. Work in progress (2014)
  18.Giebermann, K.: Multilevel approximation of boundary integral operators. Computing 67(3), 183-07 (2001). doi:10.-007/?s006070170005
  19.Gillman, A., Martinsson, P.: A direct solver with \(O(N)\) complexity for variable coefficient elliptic PDEs discretized via a high-order composite spectral collocation method. Tech. rep. (2013). arXiv:-302.-995 [math.NA]
  20.Grasedyck, L.: Theorie und Anwendungen Hierarchischer Matrizen. Doctoral thesis, Kiel (2001) (in German)
  21.Grasedyck, L.: Adaptive recompression of \({\cal H}\) -matrices for BEM. Computing 74(3), 205-23 (2005)MATH MathSciNet CrossRef
  22.Grasedyck, L., Hackbusch, W.: Construction and arithmetics of \({\cal H}\) -matrices. Computing 70(4), 295-34 (2003)MATH MathSciNet CrossRef
  23.Grasedyck, L., Hackbusch, W., Kriemann, R.: Performance of \({\cal H}\) -LU preconditioning for sparse matrices. Comput. Methods Appl. Math. 8(4), 336-49 (2008)MATH MathSciNet CrossRef
  24.Grasedyck, L., Kriemann, R., Le Borne, S.: Parallel black box \({\cal H}\) -LU preconditioning for elliptic boundary value problems. Comput. Vis. Sci. 11(4-), 273-91 (2008). doi:10.-007/?s00791-008-0098-9
  25.Grasedyck, L., Kriemann, R., Le Borne, S.: Domain decomposition based \({\cal H}\) -LU preconditioning. Numer. Math. 112(4), 565-00 (2009)MATH MathSciNet CrossRef
  26.Greengard, L., Gueyffier, D., Martinsson, P.G., Rokhlin, V.: Fast direct solvers for integral equations in complex three-dimensional domains. Acta Numer. 18, 243-75 (2009). doi:10.-017/?S096249290641001-
  27.Hackbusch, W.: A sparse matrix arithmetic based on \({\cal H}\) -matrices. Introduction to \({\cal H}\) -matrices. Computing 62(2), 89-08 (1999)
  
• 作者单位：Markus Faustmann (1)
  Jens Markus Melenk (1)
  Dirk Praetorius (1)
  
  1. Institute for Analysis and Scientific Computing?(Inst. E 101), Vienna University of Technology, Wiedner Hauptstrae 8-10, 1040?, Vienna, Austria
  
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Numerical Analysis
  Mathematics
  Mathematical and Computational Physics
  Mathematical Methods in Physics
  Numerical and Computational Methods
  Applied Mathematics and Computational Methods of Engineering
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：0945-3245

文摘

We study the question of approximability for the inverse of the FEM stiffness matrix for (scalar) second order elliptic boundary value problems by blockwise low rank matrices such as those given by the \(\mathcal {H}\)-matrix format introduced by Hackbusch (Computing 62(2):89-08, 1999). We show that exponential convergence in the local block rank \(r\) can be achieved. We also show that exponentially accurate \(LU\)-decompositions in the \(\mathcal {H}\)-matrix format are possible for the stiffness matrices arising in the FEM. Our analysis avoids any coupling of the block rank \(r\) to the mesh width \(h\). We also cover fairly general boundary conditions of mixed Dirichlet–Neumann–Robin boundary conditions. Mathematics Subject Classification 65F05 65N30 65F30 65F50