parallelGBC – parallel Gröbner basis computation

Introduction

More than two years ago I created the public github repository of my project parallelGBC which is the implementation of a parallel (and) distributed algorithm to compute Gröbner bases. If you have no idea what Gröbner bases are, you can use one of the following resources to find out more:

For those of you who are (now) familiar with Gröbner bases, I’d like to introduce my implementation to you. I hope that I will talk more about algorithm details in later posts. At the moment you will find some of my papers and presentations online:

  • Parallel Reduction of Matrices in Gröbner Bases Computations:
    paper (SpringerLink) ‐ (slides)
  • A modified parallel F4 algorithm for shared and distributed memory architectures:
    paper (EPiC) ‐ (slides)

First example & setup

Assume you want to compute the Gröbner basis of the following input system over the finite field with 32003 elements (𝔽32003) using the degree reverse lexicographic term ordering (… I know you need to do this daily):

x1+x2+x3
x1 · x2+x1 · x3+x2 · x3
x1 · x2 · x3-1

Step 1, get parallelGBC working on your machine:

# git clone https://github.com/svrnm/parallelGBC 
# cd parallelGBC 
# make 

Since it might happen that the previous step fails, I have to tell you some requirements to install parallellGBC.

There should be a package for each requirement for your preferred Linux distribution. From this point on I assume you have a working environment and after step 1, you can continue with step 2:

# ./test/test-f4.bin input/cyclic3.txt 1 0 1 
x[1] + x[2] + x[3], x[2]^2 + x[2]*x[3] + x[3]^2, x[3]^3 + 32002*1

And you are done? Wasn’t that easy? Maybe I have to explain what happened. Fortunately we chose an example (Cyclic 3) which is already included in the list of examples (subfolder input/) and furthermore the term ordering and coefficient field were also chosen wisely, since they are predefined in the source code for test-f4.bin. And unfortunately this was not very difficult, so we only used one processor to compute the solution.

Another example: This will take some time

For the next example, let’s still assume we want to compute our Gröbner basis using the degree reverse lexicographic term ordering over the finite field with 32003 elements. But we need to write our own input file. The format is the following:

  • Indeterminants like x1,…xn are translated to x[1],…,x[n]
  • More complex terms like x14 · x22 · x3 are written as
    x[1]^4 * x[2]^2 * x[3]
  • Finally you can multiply (*) your terms with constants and write a polynomial using addition (+) and subtraction (-)
  • Polynomials are separated by comma

Using the format as defined above you can write our first example in a file:

x[1]+x[2]+x[3], x[1]*x[2]+x[1]*x[3]+x[2]*x[3], x[1]*x[2]*x[3]-1

Cyclic N, where N is a natural number, are often used for benchmarking Gröbner basis computations since you can just increase the difficulty by increasing the index of N. A first interesting example is Cyclic 9. To compute the Gröbner basis for this input system using four processors without seeing the result but with some more verbosity, do the following:

./test/test-f4.bin input/cyclic9.txt 4 127 0

Depending on your machine’s computing power this may take some time (e.g. 2049 seconds using four Opteron™ 6172 processor cores) and will tell you that there are 1344 polynomials in the resulting Gröbner basis. So, gladly we didn’t output the result to our terminal! If you’d like to store and use the result you can change the parameters again to 4 0 1, which means “use four processors, no verbosity and print the Gröbner basis”.

To be continued …

Now you know how to compute Gröbner bases over a fixed finite field using a fixed term ordering. In the next article, I will explain how you can change these two parameters and answer some questions, like how to enable simplify, disable the sugar cube strategy and anything else you always wanted to know about parallelGBC

Leave a Comment

Your email address will not be published. Required fields are marked *