We have decided to discontinue the publication of preprints on our preprint server as of 1 March 2024. The publication culture within mathematics has changed so much due to the rise of repositories such as ArXiV (www.arxiv.org) that we are encouraging all institute members to make their preprints available there. An institute's repository in its previous form is, therefore, unnecessary. The preprints published to date will remain available here, but we will not add any new preprints here.
MiS Preprint
42/2000
${\cal H}$-matrix approximation for the operator exponential with applications
Ivan P. Gavrilyuk, Wolfgang Hackbusch and Boris N. Khoromskij
Abstract
We develop a data-sparse and accurate approximation to parabolic solution operators in the case of a rather general elliptic part given by a strongly P-positive operator. In preceding papers a class of matrices (${\cal H}$-matrices) has been analysed which are data-sparse and allow an approximate matrix arithmetic with almost linear complexity. In particular, the matrix-vector/matrix-matrix product with such matrices as well as the computation of the inverse have linear-logarithmic cost. In the present paper, we apply the ${\cal H}$-matrix techniques to approximate the exponent of an elliptic operator. Starting with the Dunford-Cauchy representation for the operator exponent, we then discretise the integral by the exponentially convergent quadrature rule involving a short sum of resolvents. The latter are approximated by the ${\cal H}$-matrices. Our algorithm inherits a two-level parallelism with respect to both the computation of resolvents and the treatment of different time values. In the case of smooth data (coefficients, boundaries), we prove the linear-logarithmic complexity of the method.