Research on Vector and Parallel Processing of Computer Algebra Algorithms and Distributed and Cooperative Processing

计算机代数算法向量并行处理及分布式协同处理研究

基本信息

批准号：
07680337
负责人：
MURAO Hirokazu
金额：
$ 1.41万
依托单位：
The University of Tokyo
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research (C)
财政年份：
1995
资助国家：
日本
起止时间：
1995 至 1996
项目状态：
已结题

项目摘要

The overall subject of this research project is the application of vector and/or parallel processing to computational algebra. It is expected to enable us, by making full use of the superior computing power and rich resources of high-performance computers in symbolic and algebraic computation, to perform ultimate-scale symbolic calculations in practice. The following lists the brief descriptions of the major research results.1. The latest algorithms for distinct degree factorization of polynomials over finite fields, which can be regarded as a break-down method for large-scale problems of polynomials with very high degrees, and their complexities are investigated very deeply. As its result, a simple method for improvement is found. Furthermore, by noticing the obvious algebraic independences in the algorithms, the investigator has developed a new algorithm for parallel processing, taking account of communication latency as well. The result of this work is presented at ISSAC'96 and publ … More iched in the proceedings.2. The new algorithm for sparse multivariate polynomial interpolation, developed by the investigator a few years ago, was revisited and examined to make its description and analysis more complete. The paper of this work was published in the special issue on parallel symbolic computation of Journal of Symbolic Computation.3. In recent yers, research on the classical problem of integer GCD calculation has been activated, aiming mainly at its parallel processing, and a few new algorithms are published. In this project, the investigator implemented some of those algorithms in Risa/Asir, to verify their much-improved performance. This implementation is further applied to the Grobner basis calculation for solving a system of algebraic equations, and we observed 6-8% reduction of computing time for solving a realistic large-scale problem. Furthermore, the research group of Risa/Asir has succeeded in computing a very large scale problem related with Grobner basis calculation, which have never veen completed till then in the world, using our new implementation and their thchnology of distributed processing. In their paper, it is reported that out new implementation, along with their idea for removal of integer contents from the intermediate polynomials, contributed very much to the success.4. Nowadays, it has been becoming a common recognition that the use of the asymptotically fast algorithms for polynomial operations is practical and necessary when treating large scale polynomials. In this project, some of the algorithms are implemented empirically, to be used in the calculations listed here. Through this development and empirical study, the investigator has learned various implementation techniques for attaining practical efficiency.5. By optimizing the exiting asymptotically fast algorithm, the investigator developed a new fast algorithm for polynomial multipoint evaluation, which is used in various polynomial calculations such as distinct degree factorization. At the same time, its parallelization, with communication latency being taken into account, is considered. A paper on this work is submitted and accepted for presentation at PASCO'97, and its implementation in KLIC for parallel processing is in progress.As for distributed and cooperative processing, the minimal but sufficient functions of Risa/Asir, realized by the developer during the term of this project, are used, and no further dovelopment is done by the investigator, because he has recognized that further mathematical studies and development of parallel algorithms will be of much more importance, rather than the sofrware development at this point of time. Less

向矢量和/或并行处理在计算代数中的总体主题，通过充分利用高级高性能计算机的卓越计算能力和丰富的符号和代数计算机的资源在实践中，符号的计算。研究人员也开发了沟通延迟的算法。符号计算的Mbolic计算3。，为了验证其经过改进的性能。与Grobner基础相关成功。4。开发了一种用于多项式多点评估的新快速算法，该评估用于不同程度的分解，并将通信潜伏期置于Anto Octure。由开发人员在该项目期间实现的Risa/Asir使用了，研究人员没有进一步完成，已经认识到，并非平行算法的进一步数学研究和开发将更加宽松，而不是SOFR Warever of the Sofr Warever时间点少