Title | A pommaret division algorithm for computing Grobner bases in boolean rings |
Author(s) | Vladimir P. Gerdt, Mikhail V. Zinn |
Type | Book, Chapter in Book, Conference Proceeding |
Abstract | In this paper an involutive algorithm for construction of Grobner bases in Boolean rings is presented. The algorithm exploits the Pommaret monomial division as an involutive division. In distinction to other approaches and due to special properties of Pommaret division the algorithm allows to perform the Grobner basis computation directly in a Boolean ring which can be defined as the quotient ring F_2[x1,...,xn],1^2+x_1,...,x_n ^2+x_n>. Some related cardinality bounds for Pommaret and Grobner bases are derived. Efficiency of our first implementation of the algorithm is illustrated by a number of serial benchmarks. |
Keywords | boolean ring, groebner basis, involutive algorithm, pommaret division |
ISBN | 978-1-59593-904-3 |
URL |
http://doi.acm.org/10.1145/1390768.1390784 |
Language | English |
Series | ISSAC '08 |
Pages | 95--102 |
Publisher | ACM |
Year | 2010 |
Translation |
No |
Refereed |
No |
Book | A pommaret division algorithm for computing Grobner bases in boolean rings |
Conferencename | ISSAC 2008 The twenty-first international symposium on Symbolic and algebraic computation |