Multipoint polynomial evaluation and interpolation are fundamental for modern
symbolic and numerical computing. The known algorithms solve both problems over
any field of constants in nearly linear arithmetic time, but the cost grows to
quadratic for numerical solution. We fix this discrepancy: our new numerical
algorithms run in nearly linear arithmetic time. At first we restate our goals
as the multiplication of an n-by-n Vandermonde matrix by a vector and the
solution of a Vandermonde linear system of n equations. Then we transform the
matrix into a Cauchy structured matrix with some special features. By
exploiting them, we approximate the matrix by a generalized hierarchically
semiseparable matrix, which is a structured matrix of a different class.
Finally we accelerate our solution to the original problems by applying Fast
Multipole Method to the latter matrix. Our resulting numerical algorithms run
in nearly optimal arithmetic time when they perform the above fundamental
computations with polynomials, Vandermonde matrices, transposed Vandermonde
matrices, and a large class of Cauchy and Cauchy-like matrices. Some of our
techniques may be of independent interest.

本文提出了一种新的数字算法，该算法使用快速多极法来加速多点多项式求值和插值问题的解决，以实现近乎线性的时间。

用 Cauchy 矩阵和多项式进行快速近似计算

Fast Approximate Computations with Cauchy Matrices and Polynomials

The approximate computation of all gravitational forces between $N$
interacting particles via the fast multipole method (FMM) can be made as
accurate as direct summation, but requires less than $\mathcal{O}(N)$
operations. FMM groups particles into spatially bounded cells and uses
cell-cell interactions to approximate the force at any position within the sink
cell by a Taylor expansion obtained from the multipole expansion of the source
cell. By employing a novel estimate for the errors incurred in this process, I
minimise the computational effort required for a given accuracy and obtain a
well-behaved distribution of force errors. For relative force errors of
$\sim10^{-7}$, the computational costs exhibit an empirical scaling of $\propto
N^{0.87}$. My implementation (running on a 16 core node) out-performs a
GPU-based direct summation with comparable force errors for $N\gtrsim10^5$.

通过快速多极子方法（FMM）精确计算 N 个相互作用粒子之间的所有引力，所需的操作少于 O（N），同时利用空间有限约束性将粒子分组到细胞中，并通过细胞 - 细胞相互作用，使用源细胞的多极展开来近似汇聚细胞内的力。通过引入一种新的误差估计方式来最小化所需的计算和获得一个良好的力误差分布。相对于力误差约为 10-7，我的实现（在 16 个核心节点上运行）在 N≈105 时表现出 O (N) 的计算成本，超过了基于 GPU 的直接求和。