Parallel algorithms for successive convolution

DOI10.1007/S10915-020-01359-XzbMATH Open1458.65122arXiv2007.03041OpenAlexW3113300291MaRDI QIDQ2221135FDOQ2221135

Authors: Andrew Christlieb, Pierson T. Guthrey, William Sands, Mathialakan Thavappiragasm 

Publication date: 26 January 2021

Published in: Journal of Scientific Computing (Search for Journal in Brave)

Abstract: In this work, we consider alternative discretizations for PDEs which use expansions involving integral operators to approximate spatial derivatives. These constructions use explicit information within the integral terms, but treat boundary data implicitly, which contributes to the overall speed of the method. This approach is provably unconditionally stable for linear problems and stability has been demonstrated experimentally for nonlinear problems. Additionally, it is matrix-free in the sense that it is not necessary to invert linear systems and iteration is not required for nonlinear terms. Moreover, the scheme employs a fast summation algorithm that yields a method with a computational complexity of $mathcalO(N)$, where $N$ is the number of mesh points along a direction. While much work has been done to explore the theory behind these methods, their practicality in large scale computing environments is a largely unexplored topic. In this work, we explore the performance of these methods by developing a domain decomposition algorithm suitable for distributed memory systems along with shared memory algorithms. As a first pass, we derive an artificial CFL condition that enforces a nearest-neighbor communication pattern and briefly discuss possible generalizations. We also analyze several approaches for implementing the parallel algorithms by optimizing predominant loop structures and maximizing data reuse. Using a hybrid design that employs MPI and Kokkos for the distributed and shared memory components of the algorithms, respectively, we show that our methods are efficient and can sustain an update rate $>1imes10^8$ DOF/node/s. We provide results that demonstrate the scalability and versatility of our algorithms using several different PDE test problems, including a nonlinear example, which employs an adaptive time-stepping rule.

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

Recommendations

• Multidomain local Fourier method for PDEs in complex geometries
• Multigrid Reduction in Time for Nonlinear Parabolic Problems: A Case Study
• Parallel geometric multigrid
• Scheduling of tasks in the parareal algorithm
• Multigrid reduction in time for non-linear hyperbolic equations

zbMATH Keywords

domain decompositionnumerical analysisfast algorithmshigh-performance computingintegral solutionmethod-of-lines-transpose

Mathematics Subject Classification ID

Parallel numerical computation (65Y05) Numerical methods for integral equations (65R20) Method of lines for initial value and initial-boundary value problems involving PDEs (65M20) Multigrid methods; domain decomposition for initial value and initial-boundary value problems involving PDEs (65M55)

Cites Work

• Kernel based high order ``explicit unconditionally stable scheme for nonlinear degenerate advection-diffusion equations
• GMRES: A Generalized Minimal Residual Algorithm for Solving Nonsymmetric Linear Systems
• High Order Weighted Essentially Nonoscillatory Schemes for Convection Dominated Problems
• Strong stability-preserving high-order time discretization methods
• The Numerical Solution of Parabolic and Elliptic Differential Equations
• Fast integral equation methods for Rothe's method applied to the isotropic heat equation
• Alternating direction methods for three space variables
• On the Numerical Integration of $\frac{\partial ^2 u}{\partial x^2 } + \frac{\partial ^2 u}{\partial y^2 } = \frac{\partial u}{\partial t}$ by Implicit Methods
• A fast solver for the Stokes equations with distributed forces in complex geometries.
• High-order unconditionally stable FC-AD solvers for general smooth domains. I: Basic elements
• A spectral FC solver for the compressible Navier-Stokes equations in general domains. I: Explicit time-stepping
• A high-order 3D boundary integral equation solver for elliptic PDEs in smooth domains
• Method of lines transpose: high order L-stable \(\mathcal O(N)\) schemes for parabolic equations using successive convolution
• Method of lines transpose: An implicit solution to the wave equation
• A parallel fast multipole accelerated integral equation scheme for 3D Stokes equations
• Higher Order A-Stable Schemes for the Wave Equation Using a Successive Convolution Approach
• An adaptive Rothe method for the wave equation
• Title not available (Why is that?)
• A WENO-based method of lines transpose approach for Vlasov simulations
• A boundary-integral framework to simulate viscous erosion of a porous medium
• An asymptotic preserving Maxwell solver resulting in the Darwin limit of electrodynamics
• Method of Lines Transpose: Energy Gradient Flows Using Direct Operator Inversion for Phase-Field Models
• Viscous transport in eroding porous media
• High-order, Dispersionless “Fast-Hybrid” Wave Equation Solver. Part I: O(1) Sampling Cost via Incident-Field Windowing and Recentering
• A kernel based high order ``explicit unconditionally stable scheme for time dependent Hamilton-Jacobi equations
• A kernel-based explicit unconditionally stable scheme for Hamilton-Jacobi equations on nonuniform meshes

Cited In (6)

• On-line computation of convolutions
• Multigrid reduction in time for non-linear hyperbolic equations
• A rearrangement minimization problem corresponding top-Laplacian equation
• A systematic design of a parallel program for Dirichlet convolution
• Parallel Cyclic Convolution Based on Recursive Formulations of Block Pseudocirculant Matrices
• Parallel computations for Yau filters

Uses Software

• RAJA
• Kokkos
• MOLT

This page was built for publication: Parallel algorithms for successive convolution

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