An Attempt to Enhance Buchberger's Algorithm by Using Remainder Sequences and GCD Operation
An Attempt to Enhance Buchberger's Algorithm by Using Remainder Sequences and GCD Operation
复制标题
DOI：
10.1109/synasc49474.2019.00014
复制
发表时间：
2019-09
期刊：
影响因子：
--
通讯作者：
Tateaki Sasaki
中科院分区：
文献类型：
--
作者：
Tateaki Sasaki
针对词典序(Lex序)Groebner基，提出了一种改进Buchberger算法的新方法。其思想是将多项式附加到输入系统中，通过计算输入多项式的多项式余项序列(PRSS)并通过GCD运算使其接近基元来生成要附加的多项式。为此，我们首先限制输入系统满足三个合理条件(我们称这样的系统为“健康的”)，并计算冗余的PRSS，使得变量消去的余数不是三角形的，而是矩形的；我们称相应的PRSS为“矩形PRSS(RectPRSS)”；有关rectPRSS的详细信息，请参见2.a.Lex阶Groebner基的最低阶元可以从RectPR的最后一组余数和GCD运算中计算出来；见[20]。我们通过计算相互相似余数的前导系数的矩形PRSS，并将降阶后的前导系数转换为给定理想中的多项式，来生成其他要附加的多项式。通过这些，我们也能够计算Groebner基的第二个最低元素。这项研究目前正在进行中。我们的方法看起来很有前途，但它包含了许多问题，无论是理论上的还是计算上的，所以我们开始了我们的研究。
This paper proposes a new method of enhancing Buchberger's algorithm for the lexicographic order (LEX-order) Groebner bases. The idea is to append polynomials to the input system, where we generate polynomials to be appended by computing PRSs (polynomial remainder sequences) of input polynomials and making them close to basis elements by the GCD operation. In order to do so, we first restrict the input system to satisfy three reasonable conditions (we call such systems "healthy"), and we compute redundant PRSs so that the variable-eliminated remainders are not in a triangular form but in a rectangular form; we call the corresponding PRSs "rectangular PRSs (rectPRSs)"; see 2. A for details of rectPRSs. The lowest order element of the LEX-order Groebner basis can be computed from the last set of remainders of rectPRSs and the GCD operation; see [20]. We generate other polynomials to be appended by computing rectPRSs of leading coefficients of mutually similar remainders and converting the order-reduced leading coefficient to a polynomial in the given ideal. By these we are able to compute the second-lowest element of the Groebner basis, too. The research is on-going now. Our method seems promising but it contains many problems, theoretical as well as computational, so we open our research.