A fast solver for Poisson problems on infinite regular lattices

DOI10.1016/J.CAM.2013.09.003zbMATH Open1294.65104OpenAlexW2005861355MaRDI QIDQ2252191FDOQ2252191

Authors A. Gillman, P. G. Martinsson 

Publication date 16 July 2014

Published in Journal of Computational and Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

Poisson equationdiscrete potential theoryfast multipole methodregular latticeslattice Green's functionlattice equations

Mathematics Subject Classification ID

Laplace operator, Helmholtz equation (reduced wave equation), Poisson equation (35J05) Boundary element methods for boundary value problems involving PDEs (65N38)

Abstract: The Fast Multipole Method (FMM) provides a highly efficient computational tool for solving constant coefficient partial differential equations (e.g. the Poisson equation) on infinite domains. The solution to such an equation is given as the convolution between a fundamental solution and the given data function, and the FMM is used to rapidly evaluate the sum resulting upon discretization of the integral. This paper describes an analogous procedure for rapidly solving elliptic extit{difference} equations on infinite lattices. In particular, a fast summation technique for a discrete equivalent of the continuum fundamental solution is constructed. The asymptotic complexity of the proposed method is $O(N_{msource})$, where $N_{msource}$ is the number of points subject to body loads. This is in contrast to FFT based methods which solve a lattice Poisson problem at a cost $O(N_{Omega}log{N}_{Omega})$ independent of $N_{msource}$, where $Omega$ is an artificial rectangular box containing the loaded points and $N_{Omega}$ is the number of points in $Omega$.

Recommendations

• A fast Poisson solver
• scientific article; zbMATH DE number 1271382
• scientific article; zbMATH DE number 3963140
• scientific article; zbMATH DE number 3852367
• Fast Poisson solvers for spectral methods
• Fast parallel solution of the Poisson equation on irregular domains
• A fast Poisson solver for complex geometries
• Fast Poisson-based solvers for linear and nonlinear PDEs
• scientific article; zbMATH DE number 3994972
• Fast algorithm for the three-dimensional Poisson equation in infinite domains

Cites Work

• scientific article; zbMATH DE number 46317 (Why is no real title available?)
• scientific article; zbMATH DE number 1064576 (Why is no real title available?)
• scientific article; zbMATH DE number 1069612 (Why is no real title available?)
• A Fast Adaptive Multipole Algorithm for Particle Simulations
• A Generalized Fast Multipole Method for Nonoscillatory Kernels
• A Multigrid Tutorial, Second Edition
• A fast algorithm for particle simulations
• A kernel-independent adaptive fast multipole algorithm in two and three dimensions
• A wideband fast multipole method for the Helmholtz equation in three dimensions
• An Accelerated Kernel-Independent Fast Multipole Method in One Dimension
• An Implementation of the Fast Multipole Method without Multipoles
• Asymptotic expansions of lattice Green's functions
• Boundary algebraic equations for lattice problems
• Difference equations of polyharmonic type
• Discrete potential theory
• Effective properties of the octet-truss lattice material
• Efficient Algorithms for Computing a Strong Rank-Revealing QR Factorization
• Fast and accurate numerical methods for solving elliptic difference equations defined on lattices
• Macroscopic elastic properties of regular lattices
• Mechanical behavior of a three-dimensional truss material
• New method for simulating fracture using an elastically uniform random geometry lattice
• On interpolation and integration in finite-dimensional spaces of bounded functions
• On the Compression of Low Rank Matrices
• The Numerical Solution of Integral Equations of the Second Kind
• Yet another fast multipole method without multipoles -- pseudoparticle multipole method

Cited In (14)

• FLUPS: a Fourier-based library of unbounded Poisson solvers
• A 2D immersed interface vortex particle-mesh method
• A fast method for imposing periodic boundary conditions on arbitrarily-shaped lattices in two dimensions
• FFT, FMM, or multigrid? A comparative study of state-of-the-art Poisson solvers for uniform and nonuniform grids in the unit cube
• A fast multi-resolution lattice Green's function method for elliptic difference equations
• Multi-resolution lattice Green's function method for incompressible flows
• A fast lattice Green's function method for solving viscous incompressible flows on unbounded domains
• Lattice Green’s Functions for High-Order Finite Difference Stencils
• A parallel fast multipole method for elliptic difference equations
• Fast and accurate numerical methods for solving elliptic difference equations defined on lattices
• A vortex particle-mesh method for subsonic compressible flows
• Fast immersed interface Poisson solver for 3D unbounded problems around arbitrary geometries
• A fast immersed boundary method for external incompressible viscous flows using lattice Green's functions
• A new fast-multipole accelerated Poisson solver in two dimensions

This page was built for publication: A fast solver for Poisson problems on infinite regular lattices

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