Computer Algebra and Supercomputing

计算机代数和超级计算

基本信息

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

项目摘要

The overall subject of this research project is the application of supercomputers to computational algebra. The major research results are described briefly in the following.・A new modular algorithm which uses the Chinese remainder algorithm for sparse multivariate polynomial interpolation is developed, which determines unknown polynomials from their numeric values produced by efficient data-parallel processing on supercomputers. Also, its brief analysis and comparison with other algorithms are done. To evaluate its practical efficiency, the algorithm was fully implemented and tested in REDUCE,and the effort of its parallelization using C and KLIC,was made.・The new algorithm, recently developed by the investigator, for solving a system of algebraic equations was implemented on Risa/Asir, to clarify problems and appropriate methods to be used, in applying vector or parallel processing to the algorithm. It turned out that in the case of large-scale systems of equations, the computing met … More hod considered suffers from a very large amount of data to be transferred between a computer algebra system and a supercomputer each other, and therefore, requires an efficient device for interprocess communication. In this experiment, the Grobner-basis package of Risa/Asir was much improved to become the most efficient package in the world, enabling to perform maximal-scale computations.・Various algorithms for polynomial factorization are investigated theoretically and empirically. The significant findings of the experiment with a supercomputer are the facts that vector processing is substantially effective, and that among others, the Zassenhaus algorithm is generally most efficient and useful. The vectorized programs run so fast that they can factor polynomials of such high degrees as having never been tried, within a reasonable amount of time. Further investigation has been being continued to clarify how high-degree polynomial we can factorize using the state-of-the-art supercomputers. This has led to a deeper understanding of the algorithms, and brought a new algorithm.・The mechanism for network-transparent interprocess communication in Risa/Asir was slightly extended, and it was tested and evaluated very briefly, for its future use or generalization in combining the computer algebra system and supercomputing environments. Less

本研究项目的总体主题是超级计算机在计算代数中的应用，主要研究成果简述如下。・开发了一种新的模块化算法，该算法使用中国余数算法进行稀疏多元多项式插值，用于确定未知多项式。通过超级计算机上的数据并行处理产生的数值，还对其进行了简要分析并与其他算法进行了比较，以评估其实际效率，该算法在REDUCE，以及使用 C 和 KLIC 进行并行化的努力。・研究人员最近开发的用于求解代数方程组的新算法在 Risa/Asir 上实现，以澄清问题和要使用的适当方法，在将矢量或并行处理应用于算法时，事实证明，在大规模方程组的情况下，所考虑的计算会受到计算机代数系统和计算机之间传输的大量数据的影响。一个超级计算机之间相互通信，因此需要一个高效的进程间通信设备。在这个实验中，Risa/Asir 的 Grobner-basis 软件包得到了很大的改进，成为世界上最高效的软件包，能够执行最大规模的各种计算。多项式因式分解算法经过理论研究和实证研究，超级计算机实验的重要发现是矢量处理非常有效，其中 Zassenhaus 算法通常是最有效和有用的。矢量化程序运行速度如此之快，以至于它们可以在合理的时间内对从未尝试过的高次多项式进行因式分解。我们正在继续进一步研究，以阐明我们如何使用状态来对高次多项式进行因式分解。这导致了对算法的更深入的理解，并带来了新的算法。・Risa/Asir 中的网络透明进程间通信机制被稍微扩展，并且对其进行了非常简单的测试和评估，因为它的未来使用或计算机代数系统和超级计算环境相结合的概括。