Computing gröbner bases within linear algebra and its implementation
Computing gröbner bases within linear algebra and its implementation
复制标题
计算线性代数中的 gröbner 基及其实现
DOI：
10.1145/1823931.1823951
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
A. Suzuki
中科院分区：
文献类型：
--
作者：
A. Suzuki
The concept of Gröbner bases and the algorithm to compute them were introduced by Buchberger and the algorithm consists of computation of S-polynomials and one of monomial reductions. Since it has applications across a wide range of computer algebra, many optimizations have been studied and developed [6, 10, 7, 1]. In [4], Faugère introduced a new efficient algorithm F4 to compute Gröbner bases by use of linear algebra in order to achieve simultaneous monomial reductions. A method to solve systems of algebraic equations by use of linear algebra were also studied by Lazard in [8]. Also by appropriate choices of term orders for given ideals, we may compute Gröbner basis for it efficiently. Mora-Robbiano [9] and Caboara [2] studied several method to find suitable term orders. We introduce a new method to compute Gröbner bases of ideals on polynomial rings by use of sparse linear algebra. It implicitly processes both of the computations of S-polynomials and the one of monomial reductions in a single linear space simultaneously. Thus, with this method, we can expect to use a great variety of techniques including parallelism used by computation in linear algebras, in order to get Gröbner bases. Moreover our algorithm includes an indicator to choose an appropriate term order for an efficient computation of Gröbner basis for a given system of polynomials. The term order changes dynamically during the computation. If we need the Gröbner basis with respect to a given term order, we can use a method for change of order, e.g., Gröbner walk [3], FGLM [5], and Hilbert driven [12]. We choose PARI/GP to implement the algorithms in this paper in order to demonstrate that it is not difficult to implement Gröbner bases computation to a system which has neither S-polynomials nor monomial reductions. You can download the file from our page. 3 This file has three main routines, (1) groebner basis la, (2) groebner basis la opt, and (3) groebner basis la mat. The first one is a naive implementation of our algorithm, the second is optimized version. Furthermore, we give the experimental version (3) omitting routine for computation of row echelon form. In these main algorithms input polynomials are converted to vectors in a direct product of Q just before of computation, the computed vectors are converted to output polynomials at the end of the routines, and most of all computations are processed within linear algebra.
DOI：
10.1145/143242.143362
发表时间：
1992-08
期刊：
--
影响因子：
--
作者：
M. Noro;T. Takeshima
通讯作者：
M. Noro;T. Takeshima