Skip to content
/ bjb Public

Utility for computing boolean Groebner bases with involutive Janet algorithm

License

Notifications You must be signed in to change notification settings

mzinin/bjb

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

20 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

BJB

This in an C++ implementation of involutive algorithm based on Janet-like monomial division. The input of bjb util is the initial boolean basis in GNV format, the output is the corresponding boolean Gröbner basis.

Getting Started

Prerequisites

To compile this project one would need:

  • C++ compiler with C++14 support (tested ones are GCC and MSVC)
  • CMake >= 3.5.0

Build

On Linux:

cd ./build
cmake ..
make

On Windows do the following:

cd ./build
cmake ..

and open bjb.sln with Visual Studio.

Usage

The bjb utility should be run in the following way:

./bjb [options] <file_name.gnv>

The supported option are:

Short key Long key Description
-h --help print help message and exit
-v --version print version and exit
-s --collect-statistics collect and print out statistics
-a --print-answer print out constructed Gröbner basis

bjb will read the content on the GNV file and build a boolean Gröbner basis for the initial basis. If and only if the GNV file contains the correct answer, the output message The answer is CORRECT of The answer is WRONG has meaning.

Get a boolean Gröbner basis

To get the whole answer, i.e. a boolean Gröbner basis, do not forget to add -a key:

$ ./bjb -a life4.gnv
[0] = x2*x3*x4 + x0*x3 + x1*x3 + x0*x4 + x1*x4 + x2*x4
[1] = x1*x3*x4 + x0*x3 + x2*x3 + x0*x4 + x1*x4 + x2*x4
[2] = x0*x3*x4 + x1*x3 + x2*x3 + x0*x4 + x1*x4 + x2*x4
[3] = x1*x2*x4 + x0*x1 + x0*x2 + x0*x4 + x1*x4 + x2*x4 + x4
[4] = x0*x2*x4 + x0*x1 + x1*x2 + x0*x4 + x1*x4 + x2*x4 + x4
[5] = x0*x1*x4 + x0*x2 + x1*x2 + x0*x4 + x1*x4 + x2*x4 + x4
[6] = x1*x2*x3 + x0*x1 + x0*x2 + x0*x3 + x1*x4 + x2*x4 + x3*x4
[7] = x0*x2*x3 + x0*x1 + x1*x2 + x1*x3 + x0*x4 + x2*x4 + x3*x4
[8] = x0*x1*x3 + x0*x2 + x1*x2 + x2*x3 + x0*x4 + x1*x4 + x3*x4
[9] = x0*x1*x2 + x0*x1 + x0*x2 + x1*x2 + x0*x4 + x1*x4 + x2*x4 + x4

        Memory used: 8.5 Mb
 AutoReduction time: 0.00 sec
       Running time: 0.01 sec

The answer is CORRECT

Run a benchmark

That is the default behavior of the utility. Just run it with GNV file and no other options. It will print the time spent and the memory consumed for constructing boolean Gröbner basis:

$ ./bjb life9.gnv
        Memory used: 9.5 Mb
 AutoReduction time: 0.00 sec
       Running time: 4.73 sec

The answer is CORRECT

Get a full statistics:

To get all collected statistics add -s key:

$ ./bjb -s life9.gnv
Non-Multiple Prolongations considered : 5934
Non-Zero Reductions made              : 2427 (40.90%)
Zero Reductions made                  : 3507 (59.10%)

Average Non-Multiple Prolongation length : 30.35
Average Non-Zero Reduction length        : 20.31

Memory used        : 9.5 Mb
AutoReduction time : 0.00 sec
Running time       : 5.11 sec

The answer is CORRECT

Releases

No releases published

Packages

No packages published