An algorithm for the numerical evaluation of the associated Legendre functions that runs in time independent of degree and order
This work provides a fast and accurate method for evaluating associated Legendre functions over a wide parameter range, which is a key computational bottleneck in applications such as geophysics and signal processing.
The authors present an algorithm for evaluating normalized associated Legendre functions for degrees up to 1,000,000 and all orders, with runtime independent of degree and order. The method uses precomputed piecewise trivariate Chebyshev expansions of logarithms of solutions, supplemented by asymptotic and series expansions, achieving accurate evaluation across the parameter domain.
We describe a method for the numerical evaluation of normalized versions of the associated Legendre functions $P_ν^{-μ}$ and $Q_ν^{-μ}$ of degrees $0 \leq ν\leq 1,000,000$ and orders $-ν\leq μ\leq ν$ on the interval $(-1,1)$. Our algorithm, which runs in time independent of $ν$ and $μ$, is based on the fact that while the associated Legendre functions themselves are extremely expensive to represent via polynomial expansions, the logarithms of certain solutions of the differential equation defining them are not. We exploit this by numerically precomputing the logarithms of carefully chosen solutions of the associated Legendre differential equation and representing them via piecewise trivariate Chebyshev expansions. These precomputed expansions, which allow for the rapid evaluation of the associated Legendre functions over a large swath of parameter domain mentioned above, are supplemented with asymptotic and series expansions in order to cover it entirely. The results of numerical experiments demonstrating the efficacy of our approach are presented, and our code for evaluating the associated Legendre functions is publicly available.