Fast memory efficient evaluation of spherical polynomials at scattered points
A method for fast evaluation of spherical polynomials (band-limited functions) at many scattered points on the unit 2-d sphere is presented. The method relies on the sub-exponential localization of the father needlet kernels and their compatibility with spherical harmonics. It is fast, local, memory e±cient, numerically stable and with guaranteed (prescribed) accuracy. The speed is independent of the band limit and depends logarithmically on the precision. The method can be also applied for approximation on the sphere, verification of spherical polynomials and for fast generation of surfaces in computer-aided geometric design. It naturally generalizes to higher dimensions.