Efficient Algorithms and System Interface for Scientific Computation

点击翻译按钮获取中文摘要

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.