Fast Algorithms for Special Functions

用计算机对物理现象进行数值模拟的重要性怎么强调也不过分。这种计算已经成为科学研究和工业应用的基本工具。这些模拟的计算机代码通常由基本构件组成，包括执行涉及所谓“特殊功能”的计算的算法。广义地说，特殊函数只不过是不能用基本运算（例如，加减和平方根的计算）来表示的函数，这些函数在数学计算中经常出现，因此有必要命名。该项目旨在为一类特殊函数建立更有效和全面的库，这些函数是二阶微分方程的解。这些特殊函数的主要用途之一是表示模拟物理现象的更为复杂的方程的解。更准确地说，这个项目寻求开发快速算法的特殊函数族满足二阶微分方程，其系数是非振荡的。没有可行的O(1)算法来评估许多这样的族。此外，对于相应的特殊函数变换的渐近最优算法仅在少数情况下可用，其中许多算法不容易适用于并行计算环境。考虑到在天文学和地球物理学中广泛应用的大规模特殊函数变换，特别是大规模球谐变换的许多应用，这是不幸的。在这个项目中要发展的方法是基于这样一个事实，即基本上所有二阶微分方程的非振荡系数都承认非振荡相函数。这不仅为二阶微分方程定义的特殊函数的O(1)求值提供了一种机制，而且还暗示了相关的特殊函数变换是傅里叶积分算子。将现代蝴蝶算法与特殊函数的O(1)求值算法相结合，可以在渐近最优时间内应用这种算子。这种方法的主要优点之一是它非常适合并行计算环境和大规模计算。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

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.