Efficient Algorithms and System Interface for Scientific Computation

该项目侧重于三个相关领域：(1)无缺失项p进提升——建立一种更快的算法，用于恢复多变量多项式运算（如GCD（最大公约数）和因子分解）的最终结果。当涉及的多项式是稀疏的，只包含所有可能项中的几个项时，提升方法是最有效的。(2)函数求值优化与应用——通过递归关系的应用，加快了封闭形式公式中函数的重复求值。将通过符号计算推导出称为“递归链”的嵌套递归，并应用于定期提高公式的计算速度。在交互式图形可视化中的应用。(3)连接分布式科学系统——寻求建立一个高效和标准化的协议，以连接不同的自主系统进行科学计算。这样的协议对于构建分布式的“问题解决环境”是必要的。利用稀疏性和求解线性方程组，研究项(1)的p进提升过程。可行性将进行研究。算法将被指定，实现和应用。对于区域(2)，将实现一个或多个变量函数的递归链（CR）的自动生成，并测试其速度和有效性。cr的数值性质将被研究。该技术将被应用于加速数学函数的交互式图形可视化。对于区域(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.