Wavelets and Fast Numerical Algorithms Chapter uri icon



  • Wavelet based algorithms in numerical analysis are similar to other transform; methods in that vectors and operators are expanded into a basis and the; computations take place in this new system of coordinates. However, due to the; recursive definition of wavelets, their controllable localization in both space; and wave number (time and frequency) domains, and the vanishing moments; property, wavelet based algorithms exhibit new and important properties.; For example, the multiresolution structure of the wavelet expansions brings; about an efficient organization of transformations on a given scale and of; interactions between different neighbouring scales. Moreover, wide classes of; operators which naively would require a full (dense) matrix for their numerical; description, have sparse representations in wavelet bases. For these operators; sparse representations lead to fast numerical algorithms, and thus address a; critical numerical issue.; We note that wavelet based algorithms provide a systematic generalization of; the Fast Multipole Method (FMM) and its descendents.; These topics will be the subject of the lecture. Starting from the notion of; multiresolution analysis, we will consider the so-called non-standard form; (which achieves decoupling among the scales) and the associated fast numerical; algorithms. Examples of non-standard forms of several basic operators (e.g.; derivatives) will be computed explicitly.

publication date

  • April 22, 1993

Full Author List

  • Beylkin G