We are developing a library routine set called FLTSS (Fast Legendre Transform with Stable Sampling), with which the spherical harmonics transform can be done in time $O(T^2 \log T)$. This is the first report of developments and applications of the FLTSS.

Our algorithm is based on approximate fast polynomial interpolation using the FMM (Fast Multipole Method). FLTSS provides routines for fast evaluations and expansions of the associated Legendre functions and those derivatives. The evaluation points can be the Gauss points.

We will discuss two topics. The first topic is the performance. The speed-up rate in the floating operation counts reaches 9.1 for $T = 4095$ and $\epsilon = 10^{-6}$. However, our first implementation does not provide such high speed in CPU time, perhaps because of the fine granularity of computations. We are now developing several versions of the code with various schemes of tuning, and the results will be shown in the presentation.

The second topic is the error. Because of the use of the FMM, our algorithm has trade-off between the computational costs and the approximation error. We are evaluating the effects of the errors of the transform on the solutions using shallow water equations and non-divergent flow equations. Our code controls the error with weights about $n$ (i.e. requires lower precision for higher wave numbers), and the effects of the weights on the results will be also discussed.