A kernel-independent treecode based on barycentric Lagrange interpolation

DOI10.4208/CICP.OA-2019-0177MaRDI QIDQ5162347zbMATH OpenFDO

Authors Lei Wang, Robert Krasny, Svetlana Tlupova

Publication date 2 November 2021

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

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

zbMATH Keywords

barycentric Lagrange interpolationChebyshev pointsregularized stokesletsscale-invariancetreecode

Mathematics Subject Classification ID

Numerical approximation and computational geometry (primarily algorithms) (65D99) Stokes and related (Oseen, etc.) flows (76D07)

Abstract: A kernel-independent treecode (KITC) is presented for fast summation of particle interactions. The method employs barycentric Lagrange interpolation at Chebyshev points to approximate well-separated particle-cluster interactions. The KITC requires only kernel evaluations, is suitable for non-oscillatory kernels, and it utilizes a scale-invariance property of barycentric Lagrange interpolation. For a given level of accuracy, the treecode reduces the operation count for pairwise interactions from $O(N^2)$ to $O(NlogN)$, where $N$ is the number of particles in the system. The algorithm is demonstrated for systems of regularized Stokeslets and rotlets in 3D, and numerical results show the treecode performance in terms of error, CPU time, and memory consumption. The KITC is a relatively simple algorithm with low memory consumption, and this enables a straightforward OpenMP parallelization.

Recommendations

• A kernel-independent treecode for general Rotne-Prager-Yamakawa tensor
• A treecode based on barycentric Hermite interpolation for electrostatic particle interactions
• A Treecode Algorithm for 3D Stokeslets and Stresslets
• A Cartesian treecode for screened Coulomb interactions
• A kernel-independent adaptive fast multipole algorithm in two and three dimensions

Cites work

• \(K\)-means clustering for optimal partitioning and dynamic load balancing of parallel hierarchical \(N\)-body simulations
• A boundary element regularized Stokeslet method applied to cilia- and flagella-driven flow
• A Cartesian treecode for screened Coulomb interactions
• A fast adaptive multipole algorithm in three dimensions
• A fast algorithm for particle simulations
• A fast algorithm for vortex blob interactions
• A fast multipole method for the Rotne-Prager-Yamakawa tensor and its applications
• A Fourier-series-based kernel-independent fast multipole method
• A Generalized Fast Multipole Method for Nonoscillatory Kernels
• A kernel independent fast multipole algorithm for radial basis functions
• A kernel-independent adaptive fast multipole algorithm in two and three dimensions
• A method for computing nearly singular integrals
• A new version of the fast multipole method for screened Coulomb interactions in three dimensions
• A parallel adaptive treecode algorithm for evolution of elastically stressed solids
• A particle method and adaptive treecode for vortex sheet motion in three-dimensional flow
• A study of bacterial flagellar bundling
• A Treecode Algorithm for 3D Stokeslets and Stresslets
• A treecode based on barycentric Hermite interpolation for electrostatic particle interactions
• A treecode-accelerated boundary integral Poisson-Boltzmann solver for electrostatics of solvated biomolecules
• Algorithm 967
• An Accelerated Kernel-Independent Fast Multipole Method in One Dimension
• An Implementation of the Fast Multipole Method without Multipoles
• Approximation theory and approximation practice
• ASKIT: approximate skeletonization kernel-independent treecode in high dimensions
• Barycentric Lagrange Interpolation
• Boundary Integral and Singularity Methods for Linearized Viscous Flow
• Boundary integral solutions of coupled Stokes and Darcy flows
• Cauchy fast multipole method for general analytic kernels
• Fast evaluation of multiquadric RBF sums by a Cartesian treecode
• Fast Ewald summation for free-space Stokes potentials
• scientific article; zbMATH DE number 41859 (Why is no real title available?)
• scientific article; zbMATH DE number 46317 (Why is no real title available?)
• scientific article; zbMATH DE number 2052773 (Why is no real title available?)
• Introduction to hierarchical matrices with applications.
• Lagrangian Interpolation at the Chebyshev Points xn,     cos (  /n),   = 0(1)n; some Unnoted Advantages
• Linear integral equations
• Modeling slender bodies with the method of regularized Stokeslets
• Modeling the dynamics of an elastic rod with intrinsic curvature and twist using a regularized Stokes formulation
• Multilevel approximation of boundary integral operators
• Multilevel matrix multiplication and fast solution of integral equations
• Nearly singular integrals in 3D Stokes flow
• On the fast matrix multiplication in the boundary element method by panel clustering
• Regularized single and double layer integrals in 3D Stokes flow
• Task-Based FMM for Multicore Architectures
• The black-box fast multipole method
• The method of regularized stokeslets
• The method of regularized Stokeslets in three dimensions:  Analysis, validation, and application to helical swimming
• The numerical stability of barycentric Lagrange interpolation
• The numerical stability of evaluation schemes for polynomials based on the Lagrange interpolation form
• The stability of barycentric interpolation at the Chebyshev points of the second kind
• Yet another fast multipole method without multipoles -- pseudoparticle multipole method

Cited in

(21)

• Treecode-accelerated Green iteration for Kohn-Sham density functional theory
• Fast multipole method for 3-D Poisson-Boltzmann equation in layered electrolyte-dielectric media
• A domain decomposition solution of the Stokes-Darcy system in 3D based on boundary integrals
• A treecode based on barycentric Hermite interpolation for electrostatic particle interactions
• A Cartesian FMM-accelerated Galerkin boundary integral Poisson-Boltzmann solver
• Relativistic space-charge field calculation by interpolation-based treecode
• A Treecode for Accurate Force Calculations
• A kernel-independent treecode for general Rotne-Prager-Yamakawa tensor
• A fast summation tree code for Matérn kernel
• The Effect of Global Smoothness on the Accuracy of Treecodes
• A hybrid stochastic interpolation and compression method for kernel matrices
• A GPU-parallelized interpolation-based fast multipole method for the relativistic space-charge field calculation
• A GPU-accelerated fast multipole method based on barycentric Lagrange interpolation and dual tree traversal
• A locking-free and accurate collocation method for nearly incompressible and incompressible plane elasticity
• On the stability of an in-line formation of hydrodynamically interacting flapping plates
• A treecode algorithm for the Poisson equation in a general domain with unstructured grids
• Numerical experiments using the barycentric Lagrange treecode to compute correlated random displacements for Brownian dynamics simulations
• A stable matrix version of the 2D fast multipole method
• The FARSIGHT Vlasov-Poisson code
• A cubed sphere fast multipole method
• High order regularization of nearly singular surface integrals

Describes a project that uses

Uses Software

• tabipb
• ASKIT
• TABI
• Algorithm 967
• Chebfun
• ScalFMM

This page was built for publication: A kernel-independent treecode based on barycentric Lagrange interpolation

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