Fast directional algorithms for the Helmholtz kernel

✍ Scribed by Björn Engquist; Lexing Ying

• Publisher: Elsevier Science
• Year: 2010
• Tongue: English
• Weight: 804 KB
• Volume: 234
• Category: Article
• ISSN: 0377-0427
• DOI: 10.1016/j.cam.2009.08.036

✦ Synopsis

This paper presents a new directional multilevel algorithm for solving N-body or N-point problems with highly oscillatory kernels. We address the problem by first proving that the interaction between a ball of radius r and a well-separated region has an approximate low rank representation, as long as the well-separated region belongs to a cone with a spanning angle of O(1/r) and is at a distance which is at least O(r 2 ) away from the ball.

Based on this representation, our algorithm organizes the high frequency computation using a multidirectional and multiscale strategy. Our algorithm is proved to have an optimal O(N log N) computational complexity for any given accuracy when the points are sampled from a two-dimensional surface.