Efficient Algorithms and System Interface for Scientific Computation

本项目主要集中在三个相关领域：(1)无缺项p-ary提升-建立了一种在GCD(最大公约数)和因式分解等多元多项式运算中恢复最终结果的更快算法。当所涉及的多项式是稀疏的，只包含所有可能项中的几个时，提升方法是最有效的。(2)函数求值优化及应用-通过应用递归关系，加快闭式公式中函数的重复求值速度。嵌套递归链将通过符号计算得到，并用于以规则的间隔提高公式的求值速度。将在交互式图形可视化中进行应用。(3)分布式科学系统的接口-寻求建立一个有效和标准化的协议来连接不同的自治系统进行科学计算。这样的协议对于建立分布式的“问题解决环境”是必要的。通过利用稀疏性和求解线性方程组，将研究项(1)的p-进提升过程。我们会研究这方面的可行性。算法将被指定、实施和应用。对于区域(2)，将实现为一个或多个变量的函数自动生成递归链(CR)，并测试其速度和有效性。我们将研究CRS的数值性质。该技术将被应用于加快数学函数的交互式图形可视化。对于区域(3)，将设计一种有效的协议(称为MP)。C语言中的库将支持该协议。

This project focuses on three related areas: (1) No-missing-term p-adic lifting --- Establishing a faster algorithm for recovering final results in multivariate polynomial operations such as GCD (Greatest Common Divisor) and factoring. The lifting method is most effective when the polynomials involved are sparse, containing just a few of all possible terms. (2) Function Evaluation Optimization and Applications --- Speeding up the repeated evaluation of functions in closed- form formulas through the application of recurrence relations. Nested recurrences called ``chain of recurrences'' will be derived by symbolic computation and applied to increase the evaluation speed of formulas at regular intervals. Application in interactive graphical visualization will be made. (3) Interfacing Distributed Scientific Systems --- Seeking to establish an efficient and standardized protocol to connect different autonomous systems for scientific computation. Such a protocol is necessary to build distributed ``problem solving environments''. By exploiting sparseness and solving systems of linear equations, the p-adic lifting procedure of item (1) will be investigated. Feasibility will be studied. Algorithms will be specified, implemented and applied. For area (2), automatic generation of chain of recurrences (CR) for functions of one or more variables will be implemented, and tested for speed and effectiveness. The numeric properties of CRs will be studied. The technique will be applied to speed up interactive graphical visualization of mathematical functions. For area (3), an efficient and protocol(called MP) will be designed. Libraries in C will support the protocol.