Papers › A faster multipole Legendre-Chebyshev transform
A faster multipole Legendre-Chebyshev transform
Mikael Mortensen
The archive published only this paper's code-link row. Authors, date and abstract are from arXiv's metadata (CC0), read from the Kaggle arXiv metadata snapshot of 2026-09-12 where its title matched the archive's; the title is the archive's.
This paper describes a fast algorithm for transforming Legendre coefficients into Chebyshev coefficients, and vice versa. The algorithm is based on the fast multipole method and is similar to the approach described by Alpert and Rokhlin [SIAM J. Sci. Comput., 12 (1991)]. The main difference is that we utilise a modal Galerkin approach with Chebyshev basis functions instead of a nodal approach with a Lagrange basis. Part of the algorithm is a novel method that facilitates faster spreading of intermediate results through neighbouring levels of hierarchical matrices. This enhancement leads to a method that is approximately 20% faster to execute, due to less floating point operations. We also describe an efficient initialization algorithm that for the Lagrange basis is roughly 5 times faster than the original method for large input arrays. The described method has both a planning and execution stage that asymptotically require O(N) flops. The algorithm is simple enough that it can be implemented in 100 lines of vectorized Python code. Moreover, its efficiency is such that a single-threaded C implementation can transform 1000,000 coefficients in approximately 20 milliseconds on a new MacBook Pro M3, representing about 3 times the execution time of a well-planned (single-threaded) type 2 discrete cosine transform from FFTW (www.fftw.org). Planning for the 1000,000 coefficients requires approximately 50 milliseconds.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections