Research on Vector and Parallel Processing of Computer Algebra Algorithms and Distributed and Cooperative Processing
Research on Vector and Parallel Processing of Computer Algebra Algorithms and Distributed and Cooperative Processing
批准号:
07680337
负责人:
MURAO Hirokazu
金额:
$1.41万
依托单位:
依托单位国家:
日本
项目类别:
Grant-in-Aid for Scientific Research (C)
财政年份:
1995
资助国家:
日本
项目状态:
已结题
起止时间:
1995 至 1996
中文摘要
本研究项目的总体主题是向量和/或并行处理在计算代数中的应用。它有望使我们通过充分利用高性能计算机在符号和代数计算方面的优越计算能力和丰富的资源,在实践中进行极致规模的符号计算。以下是主要研究成果的简要说明1。对有限域上多项式不同次数分解的最新算法进行了深入的研究,该算法可以看作是解决大型高次多项式问题的一种分解方法。其结果是找到了一种简单的改进方法。此外,通过注意到算法中明显的代数无关性,研究者开发了一种新的并行处理算法,并考虑了通信延迟。这项工作的结果在ISSAC‘96和Publ…上公布在过程中有更多的细节。对作者几年前提出的稀疏多元多项式插值新算法进行了重新回顾和研究,使其描述和分析更加完整。本论文发表在《符号计算杂志》的《并行符号计算》专刊上。近年来,对整数GCD计算这一经典问题的研究开始活跃起来,主要针对其并行处理,并提出了一些新的算法。在这个项目中,研究者在RISA/ASIR中实现了其中的一些算法,以验证它们的性能有了很大的提高。将这种实现进一步应用于求解代数方程组的Grobner基计算,我们观察到用于求解实际大规模问题的计算时间减少了6-8%。此外,RISA/ASIR的研究小组利用我们的新实现及其分布式处理技术,成功地计算了一个与Grobner基计算有关的超大规模问题,该问题在国际上从未完成过。在他们的论文中,报告了新的实现,以及他们从中间多项式中去掉整数部分的想法,这对成功做出了很大贡献。如今,在处理大型多项式时,使用渐近快速的多项式运算算法是实用的和必要的,这已经成为一种共识。在这个项目中,一些算法是经验实现的,将在这里列出的计算中使用。通过这一发展和实证研究,调查者学习了各种实现技术,以达到实际效率。通过对已有的渐近快速算法进行优化,提出了一种新的多项式多点求值的快速算法,该算法可用于各种多项式的计算,如不同次因式分解。同时,在考虑通信延迟的情况下,考虑了算法的并行化。关于这项工作的一篇论文已经提交并被接受在PASCO‘97上提交,它在KLIC上的并行处理的实现正在进行中。对于分布式和协作处理,使用了开发人员在本项目期间实现的最小但足够的RISA/ASIR功能,研究人员没有做进一步的开发,因为他已经认识到,在这个时间点上,进一步的数学研究和并行算法的开发将比软件开发更重要。较少
英文摘要
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
期刊论文(15)
专著(0)
科研奖励(0)
会议论文
登录
查看更多内容
村瀬裕一: "多項式因数分解へのスーパーコンピュータの応用" 第4回数式処理学会大会('95.6月5日〜7日@奈良女子大). (口頭発表).
Yuichi Murase:“超级计算机在多项式分解中的应用”数学处理学会第四届会议(95 年 6 月 5 日至 7 日@奈良女子大学)(口头报告)。
DOI:
--
发表时间:
期刊:
影响因子:
--
作者:
[]
通讯作者:
村尾裕一: "Risa/Asivの整数GCD計算の改良" ワークショップ「数式処理システムとその応用」(愛媛大学工学部,平成8年3月). (口頭発表).
Yuichi Murao:“Risa/Asiv 的整数 GCD 计算的改进”研讨会“公式处理系统及其应用”(爱媛大学工学院,1996 年 3 月)(口头报告)。
DOI:
--
发表时间:
期刊:
影响因子:
--
作者:
[]
通讯作者:
村尾裕一: "多項式演算の並列高速アルゴリズムと並列DDFアルゴリズムへの応用" 京都大学数理解析研究所 短期共同研究 「Researches Algorithms for Coputer Algebra」 集会,講究録用原稿. (準備中).
村尾佑一:“多项式运算在并行高速算法和并行DDF算法中的应用”京都大学数学科学研究所短期联合研究“计算机代数的研究算法”会议,讲稿手稿(准备中)。
DOI:
--
发表时间:
期刊:
影响因子:
--
作者:
[]
通讯作者:
村尾,藤瀬: "並列処理の多項式計算への応用(解説論文)" 数式処理. Vol.5,No.1. 2-17 (1996)
Murao,Fujise:“并行处理在多项式计算中的应用(解释性论文)”《数学处理》第 5 卷,第 1 期(1996 年)。
DOI:
--
发表时间:
期刊:
影响因子:
--
作者:
[]
通讯作者:
Fujise,T.and Murao,H.: "Parallel Distinct Degree Factorization Algorithm" Roc.ISSAC'96. 18-25 (1996)
Fujise,T. 和 Murao,H.:“并行不同程度分解算法”Roc.ISSAC96。
DOI:
--
发表时间:
期刊:
影响因子:
--
作者:
[]
通讯作者:
共 15 条
Research on data-parallel integer processing with high-precision and high-performance
-
批准号:26330144
-
项目类别:Grant-in-Aid for Scientific Research (C)
-
资助金额:$2.0万
-
财政年份:2014
-
负责人:MURAO Hirokazu
-
依托单位:
Research on multi-core oriented parallel algorithms and implementation techniques for seminumerical processing
-
批准号:22500011
-
项目类别:Grant-in-Aid for Scientific Research (C)
-
资助金额:$1.91万
-
财政年份:2010
-
负责人:MURAO Hirokazu
-
依托单位:
Research for practical use of fast algorithms for computer algebra and software development
-
批准号:14580365
-
项目类别:Grant-in-Aid for Scientific Research (C)
-
资助金额:$1.6万
-
财政年份:2002
-
负责人:MURAO Hirokazu
-
依托单位:
Computer Algebra and Supercomputing
-
批准号:05680266
-
项目类别:Grant-in-Aid for General Scientific Research (C)
-
资助金额:$1.28万
-
财政年份:1993
-
负责人:MURAO Hirokazu
-
依托单位:
海外基金