Fast Algorithms for Special Functions

University Of California-Davis, Davis CA

Investigators

Abstract

The importance of the numerical simulation of physical phenomena by computers cannot be overstated. Such computations have become an essential tool both in scientific research and in industrial applications. The computer codes for these simulations are usually constructed from basic building blocks, including algorithms that carry out calculations involving so-called "special functions." Broadly speaking, special functions are nothing more than functions which cannot be expressed in terms of elementary operations (e.g., addition, subtraction, and the computation of square roots) and which arise frequently enough in mathematical calculations to warrant a name. This project seeks to build more efficient and comprehensive libraries for a class of special functions which are solutions of equations known as second order differential equations. One of the principal uses of these special functions is in representing the solutions of much more complicated equations which model physical phenomena. To be more precise, this project seeks to develop fast algorithms for families of special function satisfying second order differential equations whose coefficients are nonoscillatory. There are no viable O(1) algorithms for evaluating many such families. Moreover, only in a few cases are asymptotically optimal algorithms for the corresponding special function transforms available, and many of those are not readily applicable in parallel computing environments. This is unfortunate given the many applications of extremely large-scale special function transforms, especially large-scale spherical harmonic transforms, which are widely used in astronomy and geophysics. The methods to be developed in this project are based on the fact that essentially all second order differential equations with nonoscillatory coefficients admit nonoscillatory phase functions. This not only provides a mechanism for the O(1) evaluation of special functions defined by second order differential equations, it also implies that the associated special function transforms are Fourier integral operators. Such operators can be applied in asymptotically optimal time by combining modern butterfly algorithms with algorithms for the O(1) evaluation of special functions. One of the key advantages of this methodology is that it is well-suited to parallel computing environments and large-scale computations. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.