Fast multipole methods for approximating a function from sampling values
type: Item
instance of: scholarly article
title: Fast multipole methods for approximating a function from sampling values
zbMATH Open document ID: 1421.65004
author: G. D. Liu
author: Shuhuang Xiang
published in: Numerical Algorithms
publication date: 2017-11-24T00:00:00Z
review text: In the paper, two fast multipole methods for approximating a given function by means of barycentric Lagrange interpolation and barycentric rational interpolation on \(N\) interpolation points at \(M\) sampling points are described. The set of interpolation points represents the source domain for interpolation, the set of sampling points represents the target domain. Compared to the numerical complexity \(O(NM)\) of the direct calculation of these interpolants, the complexity of the proposed methods is reduced to \(O(\max\{N,M\})\). Both methods are described in detail including the convergence analysis. A efficiency and accuracy of the two multipole methods is demonstrated on several examples. The comparison of maximum relative errors between the two suggested methods and the direct evaluation of barycentric Lagrange interpolation and barycentric rational interpolation is presented. The suggested methods can be used in many applications such as differentiation, integration, rootfinding, statistics, etc.
reviewed by: Ivana Linkeová
Mathematics Subject Classification ID: 65D05
Mathematics Subject Classification ID: 65D15
Mathematics Subject Classification ID: 31C20
zbMATH DE Number: 6812488
zbMATH Keywords: barycentric interpolation
zbMATH Keywords: Lagrange interpolation
zbMATH Keywords: rational barycentric interpolation
zbMATH Keywords: arithmetic operations
zbMATH Keywords: fast multipole method
describes a project that uses: Chebfun
describes a project that uses: RECFMM
MaRDI profile type: Publication
full work available at URL: s11075-017-0279-z
OpenAlex ID: W2586197211
cites work: Q5558293
cites work: Statistical application of barycentric rational interpolants: an alternative to splines
cites work: Exponential convergence of a linear rational interpolant between transformed Chebyshev points
cites work: Rational functions for guaranteed and experimentally well-conditioned global interpolation
cites work: Q5316348
cites work: Convergence rates of derivatives of a family of barycentric rational interpolants
cites work: Barycentric Lagrange Interpolation
cites work: Computing Zeros on a Real Interval through Chebyshev Expansion and Polynomial Rootfinding
cites work: Finding the zeros of a univariate equation: Proxy rootfinders, Chebyshev interpolation, and the companion matrix
cites work: A Fast Adaptive Multipole Algorithm for Particle Simulations
cites work: Fast Algorithms for Polynomial Interpolation, Integration, and Differentiation
cites work: Barycentric rational interpolation with no poles and high rates of approximation
cites work: Implementing Clenshaw-Curtis quadrature, I methodology and experience
cites work: THE COLLEAGUE MATRIX, A CHEBYSHEV ANALOGUE OF THE COMPANION MATRIX
cites work: A fast algorithm for particle simulations
cites work: Q4356574
cites work: Chebfun and numerical quadrature
cites work: The numerical stability of barycentric Lagrange interpolation
cites work: Linear barycentric rational quadrature
cites work: An Accelerated Kernel-Independent Fast Multipole Method in One Dimension
cites work: Lagrangian Interpolation at the Chebyshev Points xn, cos ( /n), = 0(1)n; some Unnoted Advantages
cites work: Q3126399
cites work: Die Lage der Nullstellen eines Polynoms. IV
cites work: Method of Lagrangian curvilinear interpolation
cites work: Is Gauss Quadrature Better than Clenshaw–Curtis?
cites work: Q4904857
cites work: Explicit barycentric weights for polynomial interpolation in the roots or extrema of classical orthogonal polynomials
cites work: On the convergence rates of Legendre approximation
cites work: On Interpolation Approximation: Convergence Rates for Polynomial Interpolation for Functions of Limited Regularity
cites work: Error bounds for approximation in Chebyshev points
cites work: An Improved Fast Multipole Algorithm for Potential Fields on the Line
cites work: <scp>REC</scp>FMM: Recursive Parallelization of the Adaptive Fast Multipole Method for Coulomb and Screened Coulomb Interactions
DOI: 10.1007/S11075-017-0279-Z
description: scientific article; zbMATH DE number 6812488