Fast Adaptive Numerical Methods for High Frequency Waves and Interface Tracking

The main focus of this thesis is on fast numerical methods, where adaptivity is an important mechanism to lowering the methods' complexity. The application of the methods are in the areas of wireless communication, antenna design, radar signature computation, noise prediction, medical ultrasonography, crystal growth, flame propagation, wave propagation, seismology, geometrical optics and image processing. We first consider high frequency wave propagation problems with a variable speed function in one dimension, modeled by the Helmholtz equation. One significant difficulty of standard numerical methods for such problems is that the wave length is very short compared to the computational domain and many discretization points are needed to resolve the solution. The computational cost, thus grows algebraically with the frequency w. For scattering problems with impenetrable scatterer in homogeneous media, new methods have recently been derived with a provably lower cost in terms of w. In this thesis, we suggest and analyze a fast numerical method for the one dimensional Helmholtz equation with variable speed function (variable media) that is based on wave-splitting. The Helmholtz equation is split into two one-way wave equations which are then solved iteratively for a given tolerance. We show rigorously that the algorithm is convergent, and that the computational cost depends only weakly on the frequency for fixed accuracy. We next consider interface tracking problems where the interface moves by a velocity field that does not depend on the interface itself. We derive fast adaptive numerical methods for such problems. Adaptivity makes methods robust in the sense that they can handle a large class of problems, including problems with expanding interface and problems where the interface has corners. They are based on a multiresolution representation of the interface, i.e. the interface is represented hierarchically by wavelet vectors corresponding to increasingly detailed meshes. The complexity of standard numerical methods for interface tracking, where the interface is described by marker points, is O(N/dt), where N is the number of marker points on the interface and dt is the time step. The methods that we develop in this thesis have O(dt^(-1)log N) computational cost for the same order of accuracy in dt. In the adaptive version, the cost is O(tol^(-1/p)log N), where tol is some given tolerance and p is the order of the numerical method for ordinary differential equations that is used for time advection of the interface. Finally, we consider time-dependent Hamilton-Jacobi equations with convex Hamiltonians. We suggest a numerical method that is computationally efficient and accurate. It is based on a reformulation of the equation as a front tracking problem, which is solved with the fast interface tracking methods together with a post-processing step. The complexity of standard numerical methods for such problems is O(dt^(-(d+1))) in d dimensions, where dt is the time step. The complexity of our method is reduced to O(dt^(-d)|log dt|) or even to O(dt^(-d)).QC 20121116