An Accelerated Kernel-Independent Fast Multipole Method in One Dimension

A version of the fast multipole method (FMM) is described for charge distributions on the line. Previously published schemes of this type relied either on analytical representations of the potentials to be evaluated (multipoles, Legendre expansions, Taylor series, etc.) or on tailored representations that were constructed numerically (using, e.g., the singular value decomposition (SVD), artificial charges, etc.). The algorithm of this paper belongs to the second category, utilizing the matrix compression scheme described in [H. Cheng, Z. Gimbutas, P. G. Martinsson, and V. Rokhlin, SIAM J. Sci. Comput. 26 (2005), pp. 1389–1404]. The resulting scheme exhibits substantial improvements in the CPU time requirements. Furthermore, the scheme is applicable to a wide variety of potentials; in this respect, it is similar to the SVD-based FMMs. The performance of the method is illustrated with several numerical examples.