A fast solver for Poisson problems on infinite regular lattices

DOI10.1016/J.CAM.2013.09.003zbMATH Open1294.65104arXiv1105.3505OpenAlexW2005861355MaRDI 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)

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$.

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

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

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)

Cites Work

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

Cited In (12)

• FLUPS: a Fourier-based library of unbounded Poisson solvers
• A 2D immersed interface vortex particle-mesh method
• 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
• 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)