Fast Algorithms for Special Functions

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

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.