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

这个项目的总体主题是研究一种适合于计算机代数的渐近快速算法的实用方法，并开发高效的软件，主要侧重于基本运算。更具体地说，以向量和矩阵为计算对象，利用各种算法和编程技术，开发了高效的软件。首先，我们研究了Strassen型矩阵乘法的快速算法，阐明了其快速的条件和原因。即使通过计算算术运算的数量进行了详细的分析，在某些情况下显示的令人难以置信的速度也不能完全解释，然而，我们注意到计算时间与空间复杂性密切相关。作为一个经验法则，我们了解到，如果矩阵元素的乘法比加法运算的成本高得多，并且加法运算不会改变…，则快速算法有效表达式的稀疏性更大，因此它们的乘法成本也更高。模算术就是这类算法的一个典型例子。我们的实验加强了我们早就意识到的，为模算术开发高效的基本线性运算库的必要性，如BIAS，这将有广泛的应用。我们的第二个主题是这个软件的开发，称为MBLAS。我们类似于BLAS，定义了一组用于线性代数的子例程，并为各种应用设计了合适的接口，包括应用于稠密一元多项式算术。对于模算术，除法是加速的关键，特别是在矩阵或向量运算的情况下。我们探索了几种加速技术，如使用表、乘法除法转换、使用溢出作为可管理的值。此外，我们还试验了向量处理，使用短向量SIMD指令对流数据进行处理。我们广泛的实证研究表明，这些技术的效果在很大程度上取决于硬件规格。我们得到的另一个知识是，快速矩阵乘法算法不适用于稀疏矩阵。即使对于为稀疏矩阵量身定做的矩阵表示也是如此。在整个实验中，我们注意到，就符号计算而言，使用数组来表示向量和矩阵几乎没有任何效果。除了对计算机代数系统RISA/ASIR进行维护和改进外，另一位研究人员开发了一些高级算法，并实现了高效的代数计算软件。他的工作包括不断改进Groebner基包，开发有限域上多元多项式因式分解的算法和实现，以及动态求值的模方法。较少

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