标题： 基于符号微分代数的快速多极方法的效率提升 显示英文标题

标题： Boosting the Efficiency of the Differential Algebra-based Fast Multipole Method Using Symbolic Differential Algebra

摘要： 快速多极子方法（FMM）以与粒子数量成线性关系的效率计算粒子之间的相互作用。 该方法通过根据粒子的空间分布对粒子进行分组，并通过级数展开近似远处区域的相互作用。 微分代数（DA），也称为截断幂级数代数（TPSA），计算函数在给定点的泰勒展开，并允许用户像处理数值一样方便地操作泰勒展开。 这使其成为在FMM中构建展开的便捷而强大的工具。 然而，基于DA的FMM算子通常相比基于其他数学框架（如笛卡尔张量或球面谐波）的实现效率较低。 为了解决这个问题，我们开发了一个用于符号DA计算的C++库，使能够推导出基于DA的FMM算子的显式表达式。 这些符号表达式随后用于生成高度优化的代码，消除了数值DA包中固有的冗余计算。 对于单独的FMM算子，这种方法实现了20到50倍的速度提升。 我们进一步评估了增强型DA-FMM的数值性能，并将其与两种最先进的FMM实现pyfmmlib和无迹笛卡尔张量基FMM进行了比较，针对库仑势。 对于相对误差在$10^{-7}$或更高的情况下，增强型DA-FMM始终优于这两种替代方案。 显示英文摘要

摘要： The Fast Multipole Method (FMM) computes pairwise interactions between particles with an efficiency that scales linearly with the number of particles. The method works by grouping particles based on their spatial distribution and approximating interactions with distant regions through series expansions. Differential Algebra (DA), also known as Truncated Power Series Algebra (TPSA), computes the Taylor expansion of a function at a given point and allows users to manipulate Taylor expansions as easily as numerical values in computation. This makes it a convenient and powerful tool for constructing expansions in FMM. However, DA-based FMM operators typically suffer from lower efficiency compared to implementations based on other mathematical frameworks, such as Cartesian tensors or spherical harmonics. To address this, we developed a C++ library for symbolic DA computation, enabling the derivation of explicit expressions for DA-based FMM operators. These symbolic expressions are then used to generate highly optimized code that eliminates the redundant computations inherent in numerical DA packages. For individual FMM operators, this approach achieves a speedup of 20- to 50-fold. We further evaluate the numerical performance of the enhanced DA-FMM and benchmark it against two state-of-the-art FMM implementations, pyfmmlib and the traceless Cartesian tensor-based FMM, for the Coulomb potential. For relative errors on the order of $10^{-7}$ or higher, the enhanced DA-FMM consistently outperforms both alternatives.