Distributed and adaptive fast multipole method in three dimensions

DOI10.4208/CICP.OA-2020-0072zbMATH Open1473.65004arXiv2002.04894OpenAlexW3188144631MaRDI QIDQ5163871FDOQ5163871

Authors: Jonathan R. Bull, Stefan Engblom 

Publication date: 9 November 2021

Published in: Communications in Computational Physics (Search for Journal in Brave)

Abstract: We develop a general distributed implementation of an adaptive fast multipole method in three space dimensions. We rely on a balanced type of adaptive space discretisation which supports a highly transparent and fully distributed implementation. A complexity analysis indicates favorable scaling properties and numerical experiments on up to 512 cores and 1 billion source points verify them. The parameters controlling the algorithm are subject to in-depth experiments and the performance response to the input parameters implies that the overall implementation is well-suited to automated tuning.

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

Recommendations

• A fast adaptive multipole algorithm in three dimensions
• Massively parallel implementation of a fast multipole method for distributed memory machines
• A kernel-independent adaptive fast multipole algorithm in two and three dimensions
• Optimizing the adaptive fast multipole method for fractal sets
• Adaptive spatial decomposition in fast multipole method

zbMATH Keywords

message passing interface (MPI)balanced treedistributed parallelizationadaptive fast multipole methodmultipole acceptance criterion

Mathematics Subject Classification ID

Numerical summation of series (65B10) Parallel numerical computation (65Y05) Complexity and performance of numerical algorithms (65Y20) Distributed algorithms (68W15) Numerical algorithms for specific classes of architectures (65Y10)

Cites Work

• PetFMM -- a dynamically load-balancing parallel fast multipole library
• DASHMM Accelerated Adaptive Fast Multipole Poisson-Boltzmann Solver on Distributed Memory Architecture
• A fast algorithm for particle simulations
• A kernel-independent adaptive fast multipole algorithm in two and three dimensions
• A fast adaptive multipole algorithm in three dimensions
• Fast multipole methods on graphics processors
• Bottom-Up Construction and 2:1 Balance Refinement of Linear Octrees in Parallel
• Title not available (Why is that?)
• Accelerated Cartesian expansions -- a fast method for computing of potentials of the form \(R^{ - \nu }\) for all real \(\nu \)
• The inverse fast multipole method: using a fast approximate direct dolver as a preconditioner for dense linear systems
• PVFMM: A parallel kernel independent FMM for particle and volume potentials
• On well-separated sets and fast multipole methods
• An adaptive fast multipole accelerated Poisson solver for complex geometries
• Fast multipole preconditioners for sparse matrices arising from elliptic equations
• Dynamic autotuning of adaptive fast multipole methods on hybrid multicore CPU and GPU systems

Cited In (14)

• Optimizing the adaptive fast multipole method for fractal sets
• Revision of DASHMM: dynamic adaptive system for hierarchical multipole methods
• Title not available (Why is that?)
• High performance BLAS formulation of the adaptive fast multipole method
• Title not available (Why is that?)
• Algorithm 967
• An Implementation of the Fast Multipole Method without Multipoles
• A fast adaptive multipole algorithm in three dimensions
• A parallel implementation of a fast multipole-based 3-D capacitance extraction program on distributed memory multicomputers
• Dynamic autotuning of adaptive fast multipole methods on hybrid multicore CPU and GPU systems
• A free-space adaptive FMM-based PDE solver in three dimensions
• Adaptive spatial decomposition in fast multipole method
• An adaptive fast multipole method in Cartesian basis, enabled by algorithmic differentiation
• DASHMM: dynamic adaptive system for hierarchical multipole methods

Uses Software

• Matlab
• CUDA
• PetFMM
• pvfmm
• DASHMM
• exafmm

This page was built for publication: Distributed and adaptive fast multipole method in three dimensions

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