A Parallel Directional Fast Multipole Method

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-freq...

Full description

Saved in:
Bibliographic Details
Published in:SIAM journal on scientific computing 2014-01, Vol.36 (4), p.C335-C352
Main Authors: Benson, Austin R., Poulson, Jack, Tran, Kenneth, Engquist, Björn, Ying, Lexing
Format: Article
Language:English
Subjects:
Computation
Criteria
Kernels
Multipoles
Octrees
Parallel processing
Partitions
Three dimensional
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 $\mathcal{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.
ISSN:1064-8275
1095-7197
DOI:10.1137/130945569