Research for practical use of fast algorithms for computer algebra and software development

计算机代数和软件开发快速算法的实际应用研究

基本信息

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

来源：
https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-14580365/
关键词：
computer algebra asymptotically fast algorithm Strassen-Winograd algorithm representation of math formula modular arithmetic BLAS vector operation SIMD operation 高速アルゴリズム行列乗算代数的数の計算 Risa Asir Dynamic Evaluation 基本線形演算有限体の演

项目摘要

The overall subject of this project is the investigation of an appropriate method for practical use of asymptotically fast algorithms for computer algebra and the development of efficient software, with major emphasis upon the basic operations. More concretely, adopting vectors and matrices as a computing target, we developed efficient software, by making use of various algorithms and programming techniques. First, we investigated the Strassen-type fast algorithm for matrix multiplication, to clarify the conditions and the reason of its fastness. Even with detailed analysis done by counting the number of arithmetic operations, the incredible fastness revealed in some cases cannot be explained completely, however, we noticed instead that computing time is closely related with space complexity. As an experience rule, we have learnt that the fast algorithm takes effect if the multiplication of matrix elements is much costlier than the additive operations, and additive operations do not ch … More ange the sparseness of the expressions and therefore their cost for multiplication. Modular arithmetics is a typical example of this kind. Our experiment strengthened the necessity, we have long been aware of, for the development of efficient library of basic linear operations, like BIAS, for modular arithmetics, which would have a wide variety of applications. Our second topic is the development of this software, called MBLAS. We defined a set of subroutines for linear algebra, in analogy with BLAS, and designed an appropriate interface for various applications, including the application to dense univariate polynomial arithmetics. With modular arithmetics, removal of division is a key to speed-up, especially for the case of matrix or vector operations. We have explored several techniques for speedup, such as use of tables, conversionof division by multiplication, use of overflow as a manageable value. Also, we experimented vector processing, using short-vector SIMD instructions for streaming data. Our extensive empirical study indicated that the effect of these techniques heavily depends on the hardware specification. One more knowledge we have obtained is the fact that the fast matrix-multiplication algorithm is not suited for sparse matrices. This is true even with matrix representation tailored for sparse matrices. Throughout this experiment, we noticed that the use of array for vectors and matrices is of almost no effect, as far as symbolic computation is concerned. Investigation of appropriate matrix representation has become the third subject in our project and is left for a topic of future study.Another investigator developed some high-level algorithms and realized efficient software for algebraic computation, besides the maintenance and the improvement of a computer algebra system Risa/Asir as a chief development staff. His work includes the continuous effort for improving the Groebner-basis package, development of algorithm and realization for factorization of multivariate polynomials over finite fields, and modular method for dynamic evaluation. Less

该项目的总体主题是用于实际使用计算机代数的不对称快速算法和开发有效软件的适当方法，重点是基本操作。更具体地说，采用向量和物品作为计算目标，我们通过使用各种算法和编程技术开发了有效的软件。首先，我们研究了用于矩阵乘法的strassen型快速算法，以阐明其牢度的条件和原因。即使通过计算算术操作的数量来进行详细的分析，在某些情况下揭示的令人难以置信的牢度也无法完全解释，但是，我们注意到计算时间与空间复杂性密切相关。作为经验规则，我们了解到，如果矩阵元素的乘法比附加的操作更为昂贵，并且加法操作不可能……更多的是表达式的稀疏性以及它们的乘法成本，那么快速算法就会生效。模块化算术是这种典型的例子。我们的实验增强了必要的特性，我们长期以来一直意识到，用于开发有效的基本线性操作库，例如偏见，用于模块化算术，这些算术将具有多种应用。我们的第二个主题是该软件的开发，称为MBLA。我们用Blas类似地定义了一组线性代数的子例程，并为各种应用设计了适当的接口，包括应用于密集的单变量多项式算术的应用。使用模块化算术，去除分裂是加速的关键，尤其是对于矩阵或向量操作的情况。我们已经探索了几种用于加速的技术，例如使用表，通过乘法来转换除法，将溢出用作可管理的值。此外，我们使用短矢量SIMD指令进行了流数据，我们尝试了矢量处理。我们广泛的实证研究表明，这些技术的效果在很大程度上取决于硬件规范。我们获得的另一个知识是，快速基质 - 培养算法不适合稀疏材料。即使是针对稀疏材料量身定制的矩阵表示，也是如此。通过该实验，就符号计算而言，将阵列用于向量和材料几乎没有影响。对适当的矩阵表示的调查已成为我们项目中的第三个主题，并留给未来的研究主题。另一位研究人员开发了一些高级算法，并实现了代数计算的有效软件，除了维护和改进计算机代数系统RISA/ASIR作为首席开发人员。他的工作包括不断提高Groebner-BASIS软件包的努力，算法的开发以及实现有限领域的多元多项式分解的实现，以及用于动态评估的模块化方法。较少的