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

Bebendorf, Mario

doi:10.1090/S0025-5718-04-01716-8

Efficient inversion of the Galerkin matrix of general second-order elliptic operators with nonsmooth coefficients
HTML articles powered by AMS MathViewer

by Mario Bebendorf PDF

Math. Comp. 74 (2005), 1179-1199 Request permission

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.

References

Mario Bebendorf, Approximation of boundary element matrices, Numer. Math. 86 (2000), no. 4, 565–589. MR 1794343, DOI 10.1007/PL00005410
M. Bebendorf: Effiziente numerische Lösung von Randintegralgleichungen unter Verwendung von Niedrigrang-Matrizen. dissertation.de, Verlag im Internet, 2001. ISBN 3-89825-183-7.
M. Bebendorf and S. Rjasanow, Adaptive low-rank approximation of collocation matrices, Computing 70 (2003), no. 1, 1–24. MR 1972724, DOI 10.1007/s00607-002-1469-6
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
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
G. Beylkin, R. Coifman, and V. Rokhlin: Fast wavelet transforms and numerical algorithms. I. Comm. Pure Appl. Math. 44(2), 141–183, 1991.
W. Dahmen, S. Prössdorf, and R. Schneider, Wavelet approximation methods for pseudodifferential equations. II. Matrix compression and fast solution, Adv. Comput. Math. 1 (1993), no. 3-4, 259–335. MR 1242378, DOI 10.1007/BF02072014
W. Dahmen, S. Prössdorf, and R. Schneider, Wavelet approximation methods for pseudodifferential equations. I. Stability and convergence, Math. Z. 215 (1994), no. 4, 583–620. MR 1269492, DOI 10.1007/BF02571732
G. Dolzmann and S. Müller, Estimates for Green’s matrices of elliptic systems by $L^p$ theory, Manuscripta Math. 88 (1995), no. 2, 261–273. MR 1354111, DOI 10.1007/BF02567822
David Gilbarg and Neil S. Trudinger, Elliptic partial differential equations of second order, Classics in Mathematics, Springer-Verlag, Berlin, 2001. Reprint of the 1998 edition. MR 1814364
L. Grasedyck: Theorie und Anwendungen Hierarchischer Matrizen. Dissertation, Universität Kiel, 2001.
Michael Grüter and Kjell-Ove Widman, The Green function for uniformly elliptic equations, Manuscripta Math. 37 (1982), no. 3, 303–342. MR 657523, DOI 10.1007/BF01166225
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
W. Hackbusch, Elliptic differential equations, Springer Series in Computational Mathematics, vol. 18, Springer-Verlag, Berlin, 1992. Theory and numerical treatment; Translated from the author’s revision of the 1986 German original by Regine Fadiman and Patrick D. F. Ion. MR 1197118, DOI 10.1007/978-3-642-11490-8
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 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 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
Siegfried Prössdorf and Bernd Silbermann, Numerical analysis for integral and related operator equations, Mathematische Lehrbücher und Monographien, II. Abteilung: Mathematische Monographien [Mathematical Textbooks and Monographs, Part II: Mathematical Monographs], vol. 84, Akademie-Verlag, Berlin, 1991 (English, with English and German summaries). MR 1206476
Eugene Tyrtyshnikov, Mosaic-skeleton approximations, Calcolo 33 (1996), no. 1-2, 47–57 (1998). Toeplitz matrices: structures, algorithms and applications (Cortona, 1996). MR 1632459, DOI 10.1007/BF02575706