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

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2013-11
Main Authors: Benson, Austin R, Poulson, Jack, Tran, Kenneth, Engquist, Björn, Lexing Ying
Format: Article
Language:English
Subjects:
Criteria
Kernels
Multipoles
Octrees
Partitions
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 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:2331-8422
DOI:10.48550/arxiv.1311.4257