FFT, FMM, or multigrid? A comparative study of state-of-the-art Poisson solvers for uniform and nonuniform grids in the unit cube
From MaRDI portal
Publication:2815697
DOI10.1137/15M1010798zbMATH Open1369.65138arXiv1408.6497OpenAlexW3104266598MaRDI QIDQ2815697FDOQ2815697
Authors: Amir Gholami, Dhairya Malhotra, Hari Sundar, George Biros 
Publication date: 30 June 2016
Published in: SIAM Journal on Scientific Computing (Search for Journal in Brave)
Abstract: In this work, we benchmark and discuss the performance of the scalable methods for the Poisson problem which are used widely in practice: the fast Fourier transform (FFT), the fast multipole method (FMM), the geometric multigrid (GMG), and algebraic multigrid (AMG). In total we compare five different codes, three of which are developed in our group. Our FFT, GMG, and FMM are parallel solvers that use high-order approximation schemes for Poisson problems with continuous forcing functions (the source or right-hand side). We examine and report results for weak scaling, strong scaling, and time to solution for uniform and highly refined grids. We present results on the Stampede system at the Texas Advanced Computing Center and on the Titan system at the Oak Ridge National Laboratory. In our largest test case, we solved a problem with 600 billion unknowns on 229,379 cores of Titan. Overall, all methods scale quite well to these problem sizes. We have tested all of the methods with different source functions (the right-hand side in the Poisson problem). Our results indicate that FFT is the method of choice for smooth source functions that require uniform resolution. However, FFT loses its performance advantage when the source function has highly localized features like internal sharp layers. FMM and GMG considerably outperform FFT for those cases. The distinction between FMM and GMG is less pronounced and is sensitive to the quality (from a performance point of view) of the underlying implementations. The high-order accurate versions of GMG and FMM significantly outperform their low-order accurate counterparts.
Full work available at URL: https://arxiv.org/abs/1408.6497
Recommendations
parallel computingfast Fourier transformmultigridfast multipole methodco-designPoisson solversexascale algorithms
Parallel numerical computation (65Y05) Multigrid methods; domain decomposition for boundary value problems involving PDEs (65N55) Numerical methods for trigonometric approximation and interpolation (65T40) Numerical solution of discretized equations for boundary value problems involving PDEs (65N22) Numerical methods for discrete and fast Fourier transforms (65T50) Multipole methods applied to problems in optics and electromagnetic theory (78M16)
Cites Work
- SuperLU_DIST
- PPM -- a highly efficient parallel particle-mesh library for the simulation of continuum systems
- p4est: scalable algorithms for parallel adaptive mesh refinement on forests of octrees
- P3DFFT: A framework for parallel computations of Fourier transforms in three dimensions
- PFFT: An extension of FFTW to massively parallel architectures
- Algorithm 967
- Title not available (Why is that?)
- Multi-Level Adaptive Solutions to Boundary-Value Problems
- deal.II—A general-purpose object-oriented finite element library
- High-Order Methods for Incompressible Fluid Flow
- A kernel-independent adaptive fast multipole algorithm in two and three dimensions
- An overview of the Trilinos project
- A fast adaptive multipole algorithm in three dimensions
- Title not available (Why is that?)
- A new fast-multipole accelerated Poisson solver in two dimensions
- Hybrid multigrid/Schwarz algorithms for the spectral element method
- Bottom-Up Construction and 2:1 Balance Refinement of Linear Octrees in Parallel
- A Fast Adaptive Multipole Algorithm for Particle Simulations
- A free-space adaptive FMM-based PDE solver in three dimensions
- Parallel Algorithms for the Spectral Transform Method
- Multiprocessor FFTs
- FFTs and three-dimensional Poisson solvers for hypercubes
- A Parallel Geometric Multigrid Method for Finite Elements on Octree Meshes
- A local corrections algorithm for solving Poisson's equation in three dimensions
- Title not available (Why is that?)
- Comparison of multigrid algorithms for high-order continuous finite element discretizations.
Cited In (32)
- FLUPS: a Fourier-based library of unbounded Poisson solvers
- A direction-splitting Navier-Stokes solver on co-located grids
- High-performance implementation of discontinuous Galerkin methods with application in fluid flow
- Quantifying mixing in arbitrary fluid domains: a Padé approximation approach
- Extreme scale FMM-accelerated boundary integral equation solver for wave scattering
- A fast multi-resolution lattice Green's function method for elliptic difference equations
- An integral equation method for the Cahn-Hilliard equation in the wetting problem
- Hybrid multigrid methods for high-order discontinuous Galerkin discretizations
- \texttt{PittPack}: an open-source Poisson's equation solver for extreme-scale computing with accelerators
- A High-Accurate Fast Poisson Solver Based on Harmonic Surface Mapping Algorithm
- Computation of volume potentials on structured grids with the method of local corrections
- A fast algorithm for fractional Helmholtz equation with application to electromagnetic waves propagation
- Scaling to the stars -- a linearly scaling elliptic solver for \(p\)-multigrid
- A source term method for Poisson problems with a discontinuous diffusion coefficient
- Lattice Green’s Functions for High-Order Finite Difference Stencils
- Sparse grid-based adaptive noise reduction strategy for particle-in-cell schemes
- FFTs and three-dimensional Poisson solvers for hypercubes
- Efficient numerical algorithms based on difference potentials for chemotaxis systems in 3D
- Hybrid numerical method for the Allen-Cahn equation on nonuniform grids
- Fast multipole preconditioners for sparse matrices arising from elliptic equations
- An iterative method for elliptic problems with rapidly oscillating coefficients
- An efficient Poisson solver for complex embedded boundary domains using the multi-grid and fast multipole methods
- A performance comparison of continuous and discontinuous Galerkin methods with fast multigrid solvers
- High-order adaptive mesh refinement multigrid Poisson solver in any dimension
- Computing homogenized coefficients \textit{via} multiscale representation and hierarchical hybrid grids
- Geometric multigrid method for solving Poisson's equation on octree grids with irregular boundaries
- A geometric multigrid library for quadtree/octree AMR grids coupled to MPI-AMRVAC
- Fast immersed interface Poisson solver for 3D unbounded problems around arbitrary geometries
- A regularization method for solving the Poisson equation for mixed unbounded-periodic domains
- An efficient extrapolation full multigrid method for elliptic problems in two and three dimensions
- A Multilevel Algebraic Error Estimator and the Corresponding Iterative Solver with $p$-Robust Behavior
- Finite difference preconditioning for compact scheme discretizations of the Poisson equation with variable coefficients
Uses Software
This page was built for publication: FFT, FMM, or multigrid? A comparative study of state-of-the-art Poisson solvers for uniform and nonuniform grids in the unit cube
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2815697)
