ICM 1998, Berlin, Aug. 18–27

Abstracts of Plenary and Invited Lectures

Section:

15. Numerical Analysis and Scientific Computing

1991 MS Classification: 65, 15, 35 Beylkin, Gregory, University of Colorado at Boulder, USA On multiresolution methods in numerical analysis

Multiresolution methods have a fairly long history in numerical analysis, going back to the introduction of multigrid methods. A significant new interest in multiresolution methods was generated recently by the development of wavelet bases and other bases with controlled time-frequency localization. The introduction of these new tools allows us to relate numerical analysis with harmonic analysis and signal processing by the fundamental need to have efficient representations of operators and functions. The task of constructing fast algorithms for evaluating operators on functions or computing functions of operators is somewhat different in signal processing and numerical analysis. Whereas there has been a general acceptance of wavelet methods in signal processing (e. g., wavelet decompositions as a part of efficient compression algorithms), the acceptance in numerical analysis has been somewhat slower. In numerical analysis it is useful to compare the wavelet approach with the multigrid and the Fast Multipole Method (FMM). For most problems the wavelet approach, FMM, and multigrid methods provide the same asymptotic complexity. The differences are typically in the “constants”of the complexity estimates and these differences will, most likely, diminish in the future. In order to emphasize several distinct features of the wavelet approach, we consider two topics. First, we describe connections between the multiresolution LU decomposition, multigrid and multiresolution reduction/homogenization for self-adjoint, strictly elliptic operators and, second, the effects of computing exponentials of such operators on numerical properties of time evolution schemes for advection-diffusion equations. We note that both topics are in the area of active research. The essence of the first topic is that multiresolution LU decomposition (the usual LU decomposition interlaced with projections) is equivalent to what can, perhaps, be called the “direct” multigrid, i. e., a multigrid method without the so-called W-cycles. The reason for the absense of W-cycles is that on every scale we construct equations for the orthogonal projection of the true solution on that scale. Once these equations are solved, there is no need to return to a coarser scale to correct the solution (which is the role of W-cycles in multigrid). Equations oftained in this manner on coarser scales are of interest by themselves, since they can be interpreted as “homogenized” or reduced equations, leading to multiresolution homogenization. The essence of the second topic is that we can significantly improve properties of time evolution schemes for advection-diffusion equations by using exponentials of operators represented in wavelet bases. As it turns out, the exponential exp (−tL) of a self-adjoint, strictly elliptic operator L is sparse (for a finite but arbitrary precision) for all t ≥ 0, which makes algorithms for its construction feasible in two and three spatial dimensions. Given a proper choice of basis and several additional algorithms, we are led to adaptive numerical schemes for the solution of advection-diffusion equations.