A parallel directional fast multipole method

DOI10.1137/130945569MaRDI QIDQ2930031OpenAlexarXivFDO

Authors Austin R. Benson, Jack Poulson, Kenneth Tran, Björn Engquist, Lexing Ying

Publication date 17 November 2014

Published in SIAM Journal on Scientific Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1311.4257

zbMATH Keywords

\(N\)-body problemsdirectionalfast multipole methodsHelmholtz equationmultileveloscillatory kernelsparallelscattering problems

Mathematics Subject Classification ID

Fundamental solutions, Green's function methods, etc. for boundary value problems involving PDEs (65N80) Parallel numerical computation (65Y05) Complexity and performance of numerical algorithms (65Y20) (n)-body problems (70F10) Diffraction, scattering (78A45)

Abstract: This paper introduces a parallel directional fast multipole method (FMM) for solving N-body problems with highly oscillatory kernels, with a focus on the Helmholtz kernel in three dimensions. This class of oscillatory kernels requires a more restrictive low-rank criterion than that of the low-frequency regime, and thus effective parallelizations must adapt to the modified data dependencies. We propose a simple partition at a fixed level of the octree and show that, if the partitions are properly balanced between p processes, the overall runtime is essentially O(N log N/p+ p). By the structure of the low-rank criterion, we are able to avoid communication at the top of the octree. We demonstrate the effectiveness of our parallelization on several challenging models.

Recommendations

• Fast directional algorithms for the Helmholtz kernel
• Fast Directional Multilevel Algorithms for Oscillatory Kernels
• A Directional Equispaced Interpolation-Based Fast Multipole Method for Oscillatory Kernels
• Fast directional multilevel summation for oscillatory kernels based on Chebyshev interpolation
• Cauchy fast multipole method for general analytic kernels

Cited in

(7)

• Parallel finite volume simulation of the spherical shell dynamo with pseudo-vacuum magnetic boundary conditions
• A fast directional boundary element method for wideband multi-domain elastodynamic analysis
• Massively parallelized interpolated factored Green function method
• Parallelization of the inverse fast multipole method with an application to boundary element method
• The fast multipole method on parallel clusters, multicore processors, and graphics processing units
• A Directional Equispaced Interpolation-Based Fast Multipole Method for Oscillatory Kernels
• An explicitly-sparse representation for oscillatory kernels with wave atom-like functions

This page was built for publication: A parallel directional fast multipole method

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2930031)