Fast algorithms for spherical harmonic expansions. III (Q995237)

The butterfly algorithm was introduced by \textit{E. Michielsson} and \textit{A. Boag} [IEEE Trans. Antennas Propag., 44, No. 8, 1086--1093 (1996)] and by \textit{M. O'Neil}, \textit{F. Woolfe} and \textit{V. Rokhkin} [Appl. Comput. Harmon. Anal. 28, No. 2, 203--226 (2010; Zbl 1191.65016)]. The present paper uses the butterfly method in order to accelerate spherical harmonic transforms. This method does not require the use of extended precision arithmetic in order to attain accuracy very close to the machine precision, not even in its precomputations, unlike the alternative approach taken in its predecessor [J. Comput. Phys. 227, No. 8, 4260--4279 (2008; Zbl 1147.65111)].