Fast directional multilevel summation for oscillatory kernels based on Chebyshev interpolation

详细信息    查看全文

• 作者：Matthias Messner^a ; ^{m.messner@tugraz.at} ; Martin Schanz^a ; ^{m.schanz@tugraz.at} ; Eric Darve^b ; ^{eric.darve@stanford.edu} ; ^{darve@stanford.edu}
• 关键词：Fast multilevel summation ; Oscillatory kernel ; Chebyshev interpolation
• 刊名：Journal of Computational Physics
• 出版年：2012
• 出版时间：20 February 2012
• 年：2012
• 卷：231
• 期：4
• 页码：1175-1196
• 全文大小：1849 K

文摘

Many applications lead to large systems of linear equations with dense matrices. Direct matrix-vector products become prohibitive, since the computational cost increases quadratically with the size of the problem. By exploiting specific kernel properties fast algorithms can be constructed.

A directional multilevel algorithm for translation-invariant oscillatory kernels of the type K(x, y) = G(x ?#xA0;y)e^{?k?em>x?em>y?/sup>, with G(x ?#xA0;y) being any smooth kernel, will be presented. We will first present a general approach to build fast multipole methods (FMMs) based on Chebyshev interpolation and the adaptive cross approximation (ACA) for smooth kernels. The Chebyshev interpolation is used to transfer information up and down the levels of the FMM. The scheme is further accelerated by compressing the information stored at Chebyshev interpolation points using ACA and QR decompositions. This leads to a nearly optimal computational cost with a small pre-processing time due to the low computational cost of ACA. This approach is in particular faster than performing singular value decompositions.}

This does not address the difficulties associated with the oscillatory nature of K. For that purpose, we consider the following modification of the kernel K^u = K(x, y)e^{?em>?ku¡¤(x?em>y)}, where u is a unit vector (see Brandt ). We proved that the kernel K^u can be interpolated efficiently when x ?#xA0;y lies in a cone of direction u. This result is used to construct an FMM for the kernel K.

Theoretical error bounds will be presented to control the error in the computation as well as the computational cost of the method. The paper ends with the presentation of 2D and 3D numerical convergence studies, and computational cost benchmarks.