Another preprocessing algorithm for generalized one-dimensional fast multipole method

The fast multipole method (FMM), which is originally an algorithm for fast evaluation of particle interactions, is also effective for accelerating several numerical computations. Yarvin and Rokhlin proposed “generalized” FMM using the singular value decomposition (SVD), which gives the optimum low-rank approximation. Their algorithm reduces the computational costs of the FMM evaluation and frees the FMM from analytical approximation formulae. However, the computational complexity of the preprocessing for an N×N matrix is O(N3) because of the SVD, and it requires orthogonal matrices of the low-rank approximations. In this paper we propose another preprocessing algorithm for the generalized FMM. Our algorithm runs in time O(N2) even with the SVD and releases the low-rank approximations from orthogonal matrices. The triangularization by the QR decomposition with sparsification, which reduces the costs of the FMM more than the diagonalization, is enabled. Although the algorithm by Yarvin and Rokhlin can be accelerated to O(N2) using the QR decomposition, our preprocessing algorithm outperforms it in fast spherical filter, fast polynomial interpolation and fast Legendre transform.