Wavelet and multiscale methods for operator equations

Abstract

More than anything else, the increase of computing power seems to stimulate the greed for tackling ever larger problems involving large-scale numerical simulation. As a consequence, the need for understanding something like theintrinsic complexityof a problem occupies a more and more pivotal position. Moreover, computability often only becomes feasible if an algorithm can be found that isasymptotically optimal. This means that storage and the number of floating point operations needed to resolve the problem with desired accuracy remainproportionalto the problem size when the resolution of the discretization is refined. A significant reduction of complexity is indeed often possible, when the underlying problem admits a continuous model in terms of differential or integral equations. The physical phenomena behind such a model usually exhibit characteristic features over a wide range of scales. Accordingly, the most successful numerical schemes exploit in one way or another the interaction of different scales of discretization. A very prominent representative is themultigridmethodology; see, for instance, Hackbusch (1985) and Bramble (1993). In a way it has caused a breakthrough in numerical analysis since, in an important range of cases, it does indeed provide asymptotically optimal schemes. For closely related multilevel techniques and a unified treatment of several variants, such asmultiplicativeoradditive subspace correctionmethods, see Bramble, Pasciak and Xu (1990), Oswald (1994), Xu (1992), and Yserentant (1993). Although there remain many unresolved problems, multigrid or multilevel schemes in the classical framework of finite difference and finite element discretizations exhibit by now a comparatively clear profile. They are particularly powerful for elliptic and parabolic problems.