Data-sparse approximation to the operator-valued functions of elliptic operator

Gavrilyuk, Ivan; Hackbusch, Wolfgang; Khoromskij, Boris

doi:10.1090/S0025-5718-03-01590-4

Data-sparse approximation to the operator-valued functions of elliptic operator
HTML articles powered by AMS MathViewer

by Ivan P. Gavrilyuk, Wolfgang Hackbusch and Boris N. Khoromskij PDF

Math. Comp. 73 (2004), 1297-1324 Request permission

Abstract:

In previous papers the arithmetic of hierarchical matrices has been described, which allows us to compute the inverse, for instance, of finite element stiffness matrices discretising an elliptic operator $\mathcal {L}.$ The required computing time is up to logarithmic factors linear in the dimension of the matrix. In particular, this technique can be used for the computation of the discrete analogue of a resolvent $\left ( zI-\mathcal {L}\right ) ^{-1},$ $z\in \mathbb {C}.$

In the present paper, we consider various operator functions, the operator exponential $e^{-t\mathcal {L}},$ negative fractional powers ${\mathcal {L} }^{-\alpha }$, the cosine operator function $\cos (t\sqrt {\mathcal {L} })\mathcal {L}^{-k}$ and, finally, the solution operator of the Lyapunov equation. Using the Dunford-Cauchy representation, we get integrals which can be discretised by a quadrature formula which involves the resolvents $\left ( z_{k}I-\mathcal {L}\right ) ^{-1}$ mentioned above. We give error estimates which are partly exponentially, partly polynomially decreasing.

References

T. Ya. Azizov, N. D. Kopachevskii, and L. D. Orlova, Evolution and spectral problems related to small motions of viscoelastic fluid, Proceedings of the St. Petersburg Mathematical Society, Vol. VI, Amer. Math. Soc. Transl. Ser. 2, vol. 199, Amer. Math. Soc., Providence, RI, 2000, pp. 1–24. MR 1766018, DOI 10.1090/trans2/199/01
M. Bebendorf and W. Hackbusch: Existence of$\mathcal {H}$-matrix approximants to the inverse FE-matrix of elliptic operators. Max-Planck-Institut für Mathematik in den Naturwissenschaften Leipzig, Preprint 21, 2002; Numer. Math. (to appear).
Richard Bellman, Introduction to matrix analysis, McGraw-Hill Book Co., Inc., New York-Toronto-London, 1960. MR 0122820
S. Börm, L. Grasedyck, and W. Hackbusch. Introduction to hierarchical matrices with applications. Max-Planck-Institut für Mathematik in den Naturwissenschaften Leipzig, Preprint Nr 18, 2002.
Robert Dautray and Jacques-Louis Lions, Mathematical analysis and numerical methods for science and technology. Vol. 5, Springer-Verlag, Berlin, 1992. Evolution problems. I; With the collaboration of Michel Artola, Michel Cessenat and Hélène Lanchon; Translated from the French by Alan Craig. MR 1156075, DOI 10.1007/978-3-642-58090-1
Ivan P. Gavrilyuk, Strongly $P$-positive operators and explicit representations of the solutions of initial value problems for second-order differential equations in Banach space, J. Math. Anal. Appl. 236 (1999), no. 2, 327–349. MR 1704587, DOI 10.1006/jmaa.1999.6430
Ivan P. Gavrilyuk, An algorithmic representation of fractional powers of positive operators, Numer. Funct. Anal. Optim. 17 (1996), no. 3-4, 293–305. MR 1393162, DOI 10.1080/01630569608816695
I.P. Gavrilyuk, W. Hackbusch and B.N. Khoromskij: $\mathcal {H}$-matrix approximation for the operator exponential with applications. Numer. Math. 92 (2002), 83-111.
I. P. Gavrilyuk, W. Hackbusch, and B. N. Khoromskij, $\scr H$-matrix approximation for elliptic solution operators in cylinder domains, East-West J. Numer. Math. 9 (2001), no. 1, 25–58. MR 1839197
I. P. Gavrilyuk and V. L. Makarov, Representation and approximation of the solution of an initial value problem for a first order differential equation in Banach spaces, Z. Anal. Anwendungen 15 (1996), no. 2, 495–527. MR 1394440, DOI 10.4171/ZAA/712
Ivan P. Gavrilyuk and Vladimir L. Makarov, Explicit and approximate solutions of second order elliptic differential equations in Hilbert and Banach spaces, Numer. Funct. Anal. Optim. 20 (1999), no. 7-8, 695–715. MR 1714886, DOI 10.1080/01630569908816919
I.P. Gavrilyuk and V.L. Makarov: Exponentially convergent parallel discretization methods for the first order evolution equations, Universität Leipzig, Preprint NTZ 12/2000.
L. Grasedyck, W. Hackbusch and B.N. Khoromskij: Application of $\mathcal {H}$-matrices in control theory. Max-Planck-Institut für Mathematik in den Naturwissenschaften Leipzig, Preprint 62, 2002; Computing 70 (2003), 121–165.
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 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
Marlis Hochbruck and Christian Lubich, On Krylov subspace approximations to the matrix exponential operator, SIAM J. Numer. Anal. 34 (1997), no. 5, 1911–1925. MR 1472203, DOI 10.1137/S0036142995280572
B.N. Khoromskij: Data-sparse elliptic operator inverse based on explicit approximation to the Green function, J. Numer. Math. 11, no. 2 (2003), 135–162.
Y. Maday, B. Pernaud-Thomas, and H. Vandeven, Reappraisal of Laguerre type spectral methods, Rech. Aérospat. 6 (1985), 353–375 (French, with English summary); English transl., Rech. Aérospat. (English Edition) 6 (1985), 13–35. MR 850680
Y. Saad, Analysis of some Krylov subspace approximations to the matrix exponential operator, SIAM J. Numer. Anal. 29 (1992), no. 1, 209–228. MR 1149094, DOI 10.1137/0729014
Dongwoo Sheen, Ian H. Sloan, and Vidar Thomée, A parallel method for time-discretization of parabolic problems based on contour integral representation and quadrature, Math. Comp. 69 (2000), no. 229, 177–195. MR 1648403, DOI 10.1090/S0025-5718-99-01098-4
Frank Stenger, Numerical methods based on sinc and analytic functions, Springer Series in Computational Mathematics, vol. 20, Springer-Verlag, New York, 1993. MR 1226236, DOI 10.1007/978-1-4612-2706-9
Frank Stenger, Collocating convolutions, Math. Comp. 64 (1995), no. 209, 211–235. MR 1270624, DOI 10.1090/S0025-5718-1995-1270624-7
F. Stenger, B. Barkey and R. Vakili: in “Proceedings of Computation and Control III” (K. Bowers and J. Lund, eds.), Birkhäuser (1993), pp. 341-354.