A wavelet-based nested iteration–inexact conjugate gradient algorithm for adaptively solving elliptic PDEs

摘要

In Cohen et al. (Math Comput 70:27–75, 2001), a new paradigm for the adaptive solution of linear elliptic partial differential equations (PDEs) was proposed, based on wavelet discretizations. Starting from a well-conditioned representation of the linear operator equation in infinite wavelet coordinates, one performs perturbed gradient iterations involving approximate matrix–vector multiplications of finite portions of the operator. In a bootstrap-type fashion, increasingly smaller tolerances guarantee convergence of the adaptive method. In addition, coarsening performed on the iterates allow one to prove asymptotically optimal complexity results when compared to the wavelet best N-term approximation. In the present paper, we study adaptive wavelet schemes for symmetric operators employing inexact conjugate gradient routines. Inspired by fast schemes on uniform grids, we incorporate coarsening and the adaptive application of the elliptic operator into a nested iteration algorithm. Our numerical results demonstrate that the runtime of the algorithm is linear in the number of unknowns and substantial savings in memory can be achieved in two and three space dimensions.