Wavelet Discretizations of Parabolic Integrodifferential Equations

Abstract

We consider parabolic problems $\dot{u} + Au = f$ in $(0,T)\times\Omega$, $T A is a strongly elliptic classical pseudodifferential operator of order $\rho \in [0,2]$ in $\tilde{H}^{\rho/2}(\Omega)$. We use a $\theta$-scheme for time discretization and a Galerkin method with N degrees of freedom for space discretization. The full Galerkin matrix for A can be replaced with a sparse matrix using a wavelet basis, and the linear systems for each time step are solved approximatively with GMRES. We prove that the total cost of the algorithm for M time steps is bounded by $O(MN (\log N)^\beta)$ operations and $O(N (\log N)^\beta)$ memory. We show that the algorithm gives optimal convergence rates (up to logarithmic terms) for the computed solution with respect to L2 in time and the energy norm in space.