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
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-07680337/
• 关键词: computer algebra; parallel processing; polynomial factorization; integer GCD; algebraic equation system; asymptotically fast algorithm; polynomial interpolation; multipoint polynomial evaluation; 並列処理(タスク並列); 整数GCD計算; 並列アルゴリズム

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

这个研究项目的总体主题是向量和/或并行处理在计算代数中的应用。它将使我们能够充分利用高性能计算机在符号计算和代数计算方面的上级计算能力和丰富的资源，在实际中进行大规模的符号计算。以下是主要研究成果的简要说明。本文对有限域上多项式异次因式分解的最新算法及其复杂性进行了深入的研究，该算法可以看作是求解高次多项式大规模问题的一种分解方法。此外，由于算法中存在明显的代数独立性，研究者提出了一种新的并行处理算法，并考虑了通信延迟。这项工作的结果已在ISSAC'96上发表， ...更多信息 在诉讼程序中占有一席之地。稀疏多元多项式插值的新算法，由研究者几年前开发的，重新审视和检查，使其描述和分析更完整。论文发表在Journal of Symbolic Computation的并行符号计算特刊上.近年来，对整数GCD计算这一经典问题的研究已十分活跃，主要针对其并行处理，并发表了一些新的算法。在这个项目中，研究人员在Risa/Asir中实现了其中的一些算法，以验证它们大大提高的性能。这种实现进一步适用于Grobner基础计算求解代数方程组的系统，我们观察到6-8%的计算时间减少解决一个现实的大规模问题。此外，Risa/Asir的研究小组已经成功地计算了一个非常大规模的Grobner基计算问题，这是迄今为止世界上从未完成的，使用我们的新实现和他们的分布式处理技术。在他们的论文中，据报道，我们的新实现，沿着他们从中间多项式中删除整数内容的想法，对成功做出了很大贡献。目前，在处理大规模多项式时，使用多项式运算的渐近快速算法是切实可行和必要的，这已成为一个共识。在这个项目中，一些算法是根据经验实现的，用于这里列出的计算。通过这一发展和实证研究，研究者学会了各种实现技术，以达到实际效率。通过对已有的渐近快速算法进行优化，提出了一种新的多项式多点求值的快速算法，该算法可用于不同次数因子分解等多项式计算。同时，考虑到通信延迟，考虑了其并行化。关于这项工作的论文已提交PASCO'97并被接受，其在KLIC中的并行处理的实现正在进行中。至于分布式和协同处理，使用了开发人员在本项目期间实现的Risa/Asir的最小但足够的功能，研究者没有做进一步的说明。因为他已经认识到，进一步的数学研究和并行算法的开发将比此时的软件开发重要得多。少

项目成果

村瀬裕一: "多項式因数分解へのスーパーコンピュータの応用" 第4回数式処理学会大会('95.6月5日〜7日@奈良女子大). (口頭発表).

Yuichi Murase：“超级计算机在多项式分解中的应用”数学处理学会第四届会议（95 年 6 月 5 日至 7 日@奈良女子大学）（口头报告）。

村尾裕一: "Risa/Asivの整数GCD計算の改良" ワークショップ「数式処理システムとその応用」(愛媛大学工学部,平成8年3月). (口頭発表).

Yuichi Murao：“Risa/Asiv 的整数 GCD 计算的改进”研讨会“公式处理系统及其应用”（爱媛大学工学院，1996 年 3 月）（口头报告）。

村尾裕一: "多項式演算の並列高速アルゴリズムと並列DDFアルゴリズムへの応用" 京都大学数理解析研究所 短期共同研究 「Researches Algorithms for Coputer Algebra」 集会,講究録用原稿. (準備中).

村尾佑一：“多项式运算在并行高速算法和并行DDF算法中的应用”京都大学数学科学研究所短期联合研究“计算机代数的研究算法”会议，讲稿手稿（准备中）。

村尾,藤瀬: "並列処理の多項式計算への応用(解説論文)" 数式処理. Vol.5,No.1. 2-17 (1996)

Murao，Fujise：“并行处理在多项式计算中的应用（解释性论文）”《数学处理》第 5 卷，第 1 期（1996 年）。

Fujise,T.and Murao,H.: "Parallel Distinct Degree Factorization Algorithm" Roc.ISSAC'96. 18-25 (1996)

Fujise,T. 和 Murao,H.：“并行不同程度分解算法”Roc.ISSAC96。