Fast Fourier Transforms for Spherical Gauss-Laguerre Basis Functions

Abstract

Spherical Gauss-Laguerre (SGL) basis functions, i.e., normalized functions of the type $L_{n-l-1}^{(l+1/2)}(r^2)r^l{Y}_{lm}(\vartheta ,\phi )$, $|m|\le l<n\in \mathbb{N}$, $L_{n-l-1}^{(l+1/2)}$ being a generalized Laguerre polynomial, $Y_{lm}$ a spherical harmonic, constitute an orthonormal basis of the space $L^2$ on ${\mathbb{R}}^3$ with Gaussian weight $\exp (-r^2)$. These basis functions are used extensively, e.g., in biomolecular dynamic simulations. However, to the present, there is no reliable algorithm available to compute the Fourier coefficients of a function with respect to the SGL basis functions in a fast way. This paper presents such generalized FFTs. We start out from an SGL sampling theorem that permits an exact computation of the SGL Fourier expansion of bandlimited functions. By a separation-of-variables approach and the employment of a fast spherical Fourier transform, we then unveil a general class of fast SGL Fourier transforms. All of these algorithms have an asymptotic complexity of $\mathcal{O}(B^4)$, $B$ being the respective bandlimit, while the number of sample points on ${\mathbb{R}}^3$ scales with $B^3$. This clearly improves the naive bound of $\mathcal{O}(B^7)$. At the same time, our approach results in fast inverse transforms with the same asymptotic complexity as the forward transforms. We demonstrate the practical suitability of our algorithms in a numerical experiment. Notably, this is one of the first performances of generalized FFTs on a non-compact domain. We conclude with a discussion, including the layout of a true $\mathcal{O}(B^3{\log }^{2}B)$ fast SGL Fourier transform and inverse, and an outlook on future developments.