On Implementing the Symbolic Preprocessing Function over Boolean Polynomial Rings in Gr¨obner Basis Algorithms Using Linear Algebra

SUN Yao,HUANG Zhenyu,LIN Dongdai,WANG Dingkang

Journal of Systems Science & Complexity ›› 2016, Vol. 29 ›› Issue (3) : 789-804.

PDF(219 KB)
PDF(219 KB)
Journal of Systems Science & Complexity ›› 2016, Vol. 29 ›› Issue (3) : 789-804. DOI: 10.1007/s11424-015-4085-1

On Implementing the Symbolic Preprocessing Function over Boolean Polynomial Rings in Gr¨obner Basis Algorithms Using Linear Algebra

  • SUN Yao1 , HUANG Zhenyu1 , LIN Dongdai1 , WANG Dingkang2
Author information +
History +

Abstract

Some techniques using linear algebra was introduced by Faug`ere in F4 to speed up the reduction process during Gr¨obner basis computations. These techniques can also be used in fast implementations of F5 and some other signature-based Gr¨obner basis algorithms. When these techniques are applied, a very important step is constructing matrices from critical pairs and existing polynomials by the Symbolic Preprocessing function (given in F4). Since multiplications of monomials and polynomials are involved in the Symbolic Preprocessing function, this step can be very costly when the number of involved polynomials/monomials is huge. In this paper, multiplications of monomials and polynomials for a Boolean polynomial ring are investigated and a specific method of implementing the Symbolic Preprocessing function over Boolean polynomial rings is reported. Many examples have been tested by using this method, and the experimental data shows that the new method is very efficient.

Key words

Boolean polynomial rings, Gr¨ / obner basis, implementation, linear algebra.

Cite this article

Download Citations
SUN Yao , HUANG Zhenyu , LIN Dongdai , WANG Dingkang. On Implementing the Symbolic Preprocessing Function over Boolean Polynomial Rings in Gr¨obner Basis Algorithms Using Linear Algebra. Journal of Systems Science and Complexity, 2016, 29(3): 789-804 https://doi.org/10.1007/s11424-015-4085-1
PDF(219 KB)

91

Accesses

0

Citation

Detail

Sections
Recommended

/