Mathematics of Computation

Efficient inversion of the Galerkin matrix of general second-order elliptic operators with nonsmooth coefficients

Author(s): Mario Bebendorf.
Journal: Math. Comp. 74 (2005), 1179-1199.
MSC (2000): Primary 35C20, 65F05, 65F50, 65N30
Posted: September 17, 2004
Retrieve article in: PDF DVI PostScript

Abstract: This article deals with the efficient (approximate) inversion of finite element stiffness matrices of general second-order elliptic operators with $L^\infty$ -coefficients. It will be shown that the inverse stiffness matrix can be approximated by hierarchical matrices ( $\mathcal{H}$ -matrices). Furthermore, numerical results will demonstrate that it is possible to compute an approximate inverse with almost linear complexity.

1.: M. Bebendorf: Approximation of boundary element matrices. Numer. Math. 86, 565-589, 2000. MR 2001j:65022
2.: M. Bebendorf: Effiziente numerische Lösung von Randintegralgleichungen unter Verwendung von Niedrigrang-Matrizen. dissertation.de, Verlag im Internet, 2001. ISBN 3-89825-183-7.
3.: M. Bebendorf and S. Rjasanow: Adaptive Low-Rank Approximation of Collocation Matrices. Computing 70(1), 1-24, 2003. MR 2004a:65177
4.: M. Bebendorf and W. Hackbusch: Existence of $\mathcal{H}$ -Matrix Approximants to the Inverse FE-Matrix of Elliptic Operators with $L^\infty$ -Coefficients. Numer. Math. 95, 1-28, 2003. MR 2004e:65128
5.: M. Bebendorf: A Note on the Poincaré-Inequality for Convex Domains. J. Anal. Appl. 22, 751-756, 2003. MR 2004e:65128
6.: G. Beylkin, R. Coifman, and V. Rokhlin: Fast wavelet transforms and numerical algorithms. I. Comm. Pure Appl. Math. 44(2), 141-183, 1991.
7.: W. Dahmen, S. Prössdorf and R. Schneider: Wavelet approximation methods for pseudodifferential equations. II. Matrix compression and fast solution. Adv. Comput. Math. 1(3-4), 259-335, 1993. MR 95g:65149
8.: W. Dahmen, S. Prössdorf, and R. Schneider: Wavelet approximation methods for pseudodifferential equations. I. Stability and convergence. Math. Z. 215(4), 583-620, 1994. MR 95g:65148
9.: G. Dolzmann and S. Müller: Estimates for Green's matrices of elliptic systems by $L^{p}$ theory. Manuscripta Math. 88, 261-273, 1995. MR MR96g:35054
10.: D. Gilbarg and N. S. Trudinger: Elliptic partial differential equations of second order, Reprint of the 1998 edition, Springer, Berlin, 2001. MR 2001k:35004
11.: L. Grasedyck: Theorie und Anwendungen Hierarchischer Matrizen. Dissertation, Universität Kiel, 2001. MR
12.: M. Grüter and K.-O. Widman: The Green function for uniformly elliptic equations. Manuscripta Math. 37, 303-342, 1982. MR 83h:35033
13.: L. Greengard and V. Rokhlin: A new version of the fast multipole method for the Laplace equation in three dimensions. Acta Numerica, 1997, pages 229-269. Cambridge Univ. Press, Cambridge, 1997. MR 99c:65012
14.: W. Hackbusch: Theorie und Numerik elliptischer Differentialgleichungen. B. G. Teubner, Stuttgart, 1996 - English translation: Elliptic differential equations. Theory and numerical treatment. Springer-Verlag, Berlin, 1992. MR 94b:35001
15.: W. Hackbusch: A sparse matrix arithmetic based on $\mathcal{H}$ -matrices. I. Introduction to $\mathcal H$ -matrices. Computing 62, 89-108, 1999. MR 2000c:65039
16.: W. Hackbusch and B. N. Khoromskij: A sparse $\mathcal H$ -matrix arithmetic. II. Application to multi-dimensional problems. Computing 64, 21-47, 2000. MR 2001i:65053
17.: W. Hackbusch and Z. P. Nowak: On the fast matrix multiplication in the boundary element method by panel clustering. Numer. Math. 54, 463-491, 1989. MR 89k:65162
18.: S. Prössdorf and B. Silbermann: Numerical analysis for integral and related operator equations, Akademie Verlag, Berlin, 1991. MR 94f:65126a
19.: E. Tyrtyshnikov: Mosaic-skeleton approximations. Calcolo 33(1-2), 47-57 (1998), 1996. MR 99f:15005

Retrieve articles in Mathematics of Computation with MSC (2000): 35C20, 65F05, 65F50, 65N30

Mario Bebendorf
Affiliation: Fakultät für Mathematik und Informatik, Universität Leipzig, Augustusplatz 10/11, D-04109 Leipzig, Germany
Email: bebendorf@math.uni-leipzig.de

DOI: 10.1090/S0025-5718-04-01716-8
PII: S 0025-5718(04)01716-8
Received by editor(s): June 4, 2003
Received by editor(s) in revised form: January 15, 2004
Posted: September 17, 2004
Additional Notes: This work was supported by the DFG priority program SPP 1146 ``Modellierung inkrementeller Umformverfahren''
Copyright of article: Copyright 2004, American Mathematical Society

			Journals Home Search Author Info Subscribe Tech Support Help
ISSN 1088-6842(e) ISSN 0025-5718(p)

Previous issue \| Table of contents \| Next issue Articles in press \| Recently posted articles \| Most recent issue \| All issues Previous Article \| Next Article


	Comments: webmaster@ams.org © Copyright 2008, American Mathematical Society Privacy Statement		Search the AMS