PetFMM -- a dynamically load-balancing parallel fast multipole library

DOI10.1002/NME.2972zbMATH Open1217.70005arXiv0905.2637OpenAlexW2168963553WikidataQ108784892 ScholiaQ108784892MaRDI QIDQ3017992FDOQ3017992

Authors: Felipe A Cruz, Matthew G. Knepley, Lorena A. Barba 

Publication date: 20 July 2011

Published in: International Journal for Numerical Methods in Engineering (Search for Journal in Brave)

Abstract: Fast algorithms for the computation of $N$-body problems can be broadly classified into mesh-based interpolation methods, and hierarchical or multiresolution methods. To this last class belongs the well-known fast multipole method (FMM), which offers O(N) complexity. This paper presents an extensible parallel library for $N$-body interactions utilizing the FMM algorithm, built on the framework of PETSc. A prominent feature of this library is that it is designed to be extensible, with a view to unifying efforts involving many algorithms based on the same principles as the FMM and enabling easy development of scientific application codes. The paper also details an exhaustive model for the computation of tree-based $N$-body algorithms in parallel, including both work estimates and communications estimates. With this model, we are able to implement a method to provide automatic, a priori load balancing of the parallel execution, achieving optimal distribution of the computational work among processors and minimal inter-processor communications. Using a client application that performs the calculation of velocity induced by $N$ vortex particles, ample verification and testing of the library was performed. Strong scaling results are presented with close to a million particles in up to 64 processors, including both speedup and parallel efficiency. The library is currently able to achieve over 85% parallel efficiency for 64 processors. The software library is open source under the PETSc license; this guarantees the maximum impact to the scientific community and encourages peer-based collaboration for the extensions and applications.

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

Recommendations

• A parallel version of the fast multipole method
• Massively parallel implementation of a fast multipole method for distributed memory machines
• Fast multipole method for particle interactions: an open source parallel library component
• On a probabilistic approach to the Schrödinger equation with a time-dependent potential
• PVFMM: A parallel kernel independent FMM for particle and volume potentials

zbMATH Keywords

parallel computingfast multipole methodparticle methodsdynamic load balancingvortex methodorder-\(N\) algorithmshierarchical algorithms

Mathematics Subject Classification ID

(n)-body problems (70F10) Computational methods for problems pertaining to mechanics of particles and systems (70-08)

Cites Work

• A fast algorithm for particle simulations
• A kernel-independent adaptive fast multipole algorithm in two and three dimensions
• Title not available (Why is that?)
• Emergence and evolution of tripole vortices from net-circulation initial conditions
• The black-box fast multipole method
• A Fast Adaptive Multipole Algorithm for Particle Simulations
• A Generalized Fast Multipole Method for Nonoscillatory Kernels
• An Implementation of the Fast Multipole Method without Multipoles
• A parallel version of the fast multipole method
• Advances in viscous vortex methods?meshless spatial adaption based on radial basis function interpolation
• A parallel implementation of the fast multipole method for Maxwell's equations
• Massively parallel implementation of a fast multipole method for distributed memory machines
• Characterization of the accuracy of the fast multipole method in particle simulations
• Provably Good Partitioning and Load Balancing Algorithms for Parallel Adaptive N-Body Simulation

Cited In (11)

• PPM -- a highly efficient parallel particle-mesh library for the simulation of continuum systems
• Optimizing the multipole-to-local operator in the fast multipole method for graphical processing units
• A parallel version of the fast multipole method
• Fast and scalable evaluation of pairwise potentials
• Title not available (Why is that?)
• PetFMM
• A distributed kernel summation framework for general‐dimension machine learning
• Distributed and Adaptive Fast Multipole Method in Three Dimensions
• On a probabilistic approach to the Schrödinger equation with a time-dependent potential
• Biomolecular electrostatics using a fast multipole BEM on up to 512 GPUs and a billion unknowns
• A Parallel Fast Multipole Method for a Space-Time Boundary Element Method for the Heat Equation

Uses Software

• NAMD
• PETSc
• CHARMM

This page was built for publication: PetFMM -- a dynamically load-balancing parallel fast multipole library

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