Bjorn Engquist, University of Texas at Austin

KAUST-IAMCS Workshop on Multiscale Modeling, Advanced Discretization Techniques, and Simulation of Wave Propagation

May 7-8, 2011

King Abdullah University of Science and Technology (KAUST)

Thuwal, Kingdom of Saudi Arabia

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 frequency domain equations. For integral formulations we present a multi-level fast multipole method based on directional decomposition, which is proved to have near optimal order of complexity: O(NlogN). A random sampling algorithm for matrix compression increases the efficiency. In the variable coefficient Helmholtz differential equation case we develop new preconditioners based sweeping processes. Hierarchical matrix techniques for compression or moving perfectly matched layers play important roles in generating algorithms of close to optimal computational complexity. Also here the number of operations scales essentially linearly in N. Applications to exploration seismology will be discussed.