Fast algorithms for high frequency wave propagation

Direct numerical approximation of high frequency wave propagation typically requires a very large number of unknowns (N). We will consider fast algorithms for iterative methods applied to boundary integral formulations and to variable coefficient differential equations. For integral formulations we present a multi-level fast multipole method based on directional decomposition, which can be proved to have near optimal order of complexity: O(NlogN). A random sampling algorithm for matrix compression increases the efficiency. In the variable coefficient frequency domain differential equation case we develop new preconditioners based on sweeping processes. Hierarchical matrix techniques for compression or moving perfectly matched layers play important roles in generating algorithms of close to optimal computational complexity.