  We demonstrate a new, hybrid symbolic-numerical method for the automatic
synthesis of all families of translation operators required for the execution
of the Fast Multipole Method (FMM). Our method is applicable in any
dimensionality and to any translation-invariant kernel. The Fast Multipole
Method, of course, is the leading approach for attaining linear complexity in
the evaluation of long-range (e.g. Coulomb) many-body interactions. Low
complexity in translation operators for the Fast Multipole Method (FMM) is
usually achieved by algorithms specialized for a potential obeying a specific
partial differential equation (PDE). Absent a PDE or specialized algorithms,
Taylor series based FMMs or kernel-independent FMM have been used, at
asymptotically higher expense.
  When symbolically provided with a constant-coefficient elliptic PDE obeyed by
the potential, our algorithm can automatically synthesize translation operators
requiring $\mathrm{O}(p^d)$ operations, where $p$ is the expansion order and
$d$ is dimension, compared with $\mathrm{O}(p^{2d})$ operations in a naive
approach carried out on (Cartesian) Taylor expansions. This is achieved by
using a compression scheme that asymptotically reduces the number of terms in
the Taylor expansion and then operating directly on this ``compressed''
representation. Judicious exploitation of shared subexpressions permits
formation, translation, and evaluation of local and multipole expansions to be
performed in $\mathrm{O}(p^{d})$ operations, while an FFT-based scheme permits
multipole-to-local translations in $\mathrm{O}(p^{d-1}\log(p))$ operations. We
demonstrate computational scaling of code generation and evaluation as well as
numerical accuracy through numerical experiments on a number of potentials from
classical physics.
