Introduction

Pedwar is a collection of four programs for computing Gröbner or Involutive Bases for polynomial ideals over commutative and noncommutative polynomial rings. The programs run under FreeBSD [6] and are intended for informational or educational purposes only; no warranty of any kind is provided.

Installation

Unpack the zip file into a suitable directory.

• The four programs grob, inv, ncgrob and ncinv appear in the top directory, together with their corresponding README files.
• The directory examples contains many examples for use with the programs.
• The directory matrices contains matrices for certain commutative monomial orderings.
• The directory source contains the ANSI C source code for the programs. Note however that in order to re-compile the programs, the AlgLib libraries from MSSRC [11] are required (see www.mssrc.com for more information).

Key Functionality

Commutative Gröbner Bases (grob)

• Implements Buchberger’s Algorithm [2] for computing commutative Gröbner Bases.
• Implements the Gröbner Walk [4] algorithm for converting a Gröbner Basis with respect to one monomial ordering to a Gröbner Basis with respect to another monomial ordering.
• Monomial orderings implemented: Lex, DegLex, DegRevLex, arbitrary matrix orderings.
• Allows the computation of Logged Gröbner Bases.
• Different selection strategies can be used, such as the sugar and the double sugar strategies [8].
• How Buchberger’s criteria [1] are applied can be controlled.
• See the file README-grob in the distribution for further details.

Commutative Involutive Bases (inv)

• Implements the Involutive Basis algorithm for computing Pommaret or Janet Involutive Bases.
• Three different algorithms for computing Involutive Bases are provided (as presented in [12], [3] and [7]).
• Monomial orderings implemented: Lex, DegLex, DegRevLex, arbitrary matrix orderings.
• Options for controlling how the basis is sorted during computation.
• See the file README-inv in the distribution for further details.

Noncommutative Gr¨obner Bases (ncgrob)

• Implements Mora’s Algorithm [10] for computing noncommutative Gröbner Bases.
• Monomial orderings implemented: Lex, DegLex, DegRevLex, Wreath Product.
• Allows the computation of Logged Gröbner Bases.
• Different selection strategies can be used, such as the sugar and the double sugar strategies.
• How Buchberger’s second criterion is applied can be controlled.
• See the file README-ncgrob in the distribution for further details.

Noncommutative Involutive Bases (ncinv)

• Implements the Involutive Basis algorithm for computing noncommutative Involutive Bases for 12 different divisions (see [5] for a description of these divisions).
• Three different algorithms for computing Involutive Bases are provided.
• Monomial orderings implemented: Lex, DegLex, DegRevLex, Wreath Product.
• Options for controlling how the basis is sorted during computation.
• See the file README-ncinv in the distribution for further details.

Examples

1. Commutative Gröbner Bases

• Task: Compute a DegLex Gröbner Basis for the ideal generated by the set of polynomials $F = \{x^2 - 2xy + 3,~2xy + y^2 + 5\}$ over the polynomial ring $\mathbb{Q}[x, y]$.
   
• Input File:
  
  > more examples/test/test2.in
  x; y;
  - 2*x*y + x*x + 3;
  2*x*y + y*y + 5;
  >
   
• Session Output:
  
  > grob -d examples/test/test2.in
  
  *** GROEBNER BASIS PROGRAM ***
  
  Using the DegLex Ordering with dictionary y < x
  
  Polynomials in the input basis:
  x^2 - 2 x y + 3,
  2 x y + y^2 + 5,
  [2 Polynomials]
  
  Computing Groebner Basis...
  Added Polynomial #3 to Basis...
  ...Groebner Basis Computed.
  
  Here is the Groebner Basis:
  x^2 - 2 x y + 3,
  2 x y + y^2 + 5,
  5 y^3 - 10 x + 37 y,
  [3 Polynomials]
  
  Computing the Reduced Groebner Basis...
  ...Reduced Groebner Basis Computed.
  
  Here is the Reduced Groebner Basis:
  x^2 + y^2 + 8,
  2 x y + y^2 + 5,
  5 y^3 - 10 x + 37 y,
  [3 Polynomials]
  
  Writing Reduced Groebner Basis to Disk... Done.
  
  >
   
• Output File:
  
  > more examples/test/test2.deg
  x; y;
  x^2 + y^2 + 8;
  2 * x * y + y^2 + 5;
  5 * y^3 - 10 * x + 37 * y;
  >

2. Commutative Gröbner Walk

• Task: Using the Gröbner Walk [4], compute a Lex Gröbner Basis for the ideal generated by the set of polynomials $F = \{y(z - t) - x + a,~ z(t - x) - y + a,~ t(x - y) - z + a,~ x(y - z) - t + a\}$ over the polynomial ring $\mathbb{Q}[x, y, z, t, a]$. Start the walk with a DegRevLex Gröbner Basis for $F$.
   
• Input File:
  
  > more examples/posso/posso07.in
  x; y; z; t; a;
  y*(z - t) - x + a;
  z*(t - x) - y + a;
  t*(x - y) - z + a;
  x*(y - z) - t + a;
  >
   
• Session Output:
  
  > grob -wrl examples/posso/posso07.in
  
  *** GROEBNER WALK PROGRAM ***
  
  Using the dictionary a < t < z < y < x
  
  *** PART A: COMPUTE A DEGREVLEX GROEBNER BASIS ***
  
  Polynomials in the input basis:
  y z - y t - x + a,
  -1 x z + z t - y + a,
  x t - y t - z + a,
  x y - x z - t + a,
  [4 Polynomials]
  
  Computing Groebner Basis...
  Added Polynomial #5 to Basis...
  Added Polynomial #6 to Basis...
  Added Polynomial #7 to Basis...
  Added Polynomial #8 to Basis...
  Added Polynomial #9 to Basis...
  Added Polynomial #10 to Basis...
  Added Polynomial #11 to Basis...
  Added Polynomial #12 to Basis...
  ...Groebner Basis Computed.
  
  Here is the Groebner Basis:
  y z - y t - x + a,
  -1 x z + z t - y + a,
  x t - y t - z + a,
  x y - x z - t + a,
  y t^2 - z t^2 + z^2 + 2 y t - z a - 2 t a + z - a,
  y^2 t - z t^2 + 2 y t - t^2 - y a + x - a,
  x^2 + y^2 + z^2 + t^2 - x a - y a - z a - t a,
  z^2 t - z t^2 + y^2 + z^2 + z t - y a - z a - t a - x + a,
  3 z t^2 + t^3 - 2 y t a - z t a - t^2 a - y^2 - z^2 - 3 y t + 2 t^2 - x a + 2 y
  a + t a + a^2 - y + a,
  z^3 - t^3 - z^2 a + y t a - z t a + t^2 a + y^2 + z^2 - t^2 + x a - y a - a^2 -
  x + y,
  y^3 - t^3 - y^2 a + t^2 a + y^2 - z^2 - 2 t^2 - y a + z a + 2 t a + y - t,
  12 t^4 - 12 t^3 a + 20 t^3 - 9 y^2 a + 6 z^2 a + 14 y t a - 14 z t a - 11 t^2 a
  + 9 y a^2 - 6 z a^2 - 9 t a^2 - 11 y^2 - 2 z^2 + 6 y t - 6 z t + 7 t^2 - 5 x a +
  4 y a + 9 z a - 4 t a + 2 a^2 + 9 x - 5 y + 9 z + 9 t - 22 a,
  [12 Polynomials]
  
  Computing the Reduced Groebner Basis...
  ...Reduced Groebner Basis Computed.
  
  Here is the Reduced Groebner Basis:
  y z - y t - x + a,
  x z - z t + y - a,
  x t - y t - z + a,
  x y - z t + y - t,
  3 y t^2 + t^3 - 2 y t a - z t a - t^2 a - y^2 + 2 z^2 + 3 y t + 2 t^2 - x a + 2
  y a - 3 z a - 5 t a + a^2 - y + 3 z - 2 a,
  3 y^2 t + t^3 - 2 y t a - z t a - t^2 a - y^2 - z^2 + 3 y t - t^2 - x a - y a +
  t a + a^2 + 3 x - y - 2 a,
  x^2 + y^2 + z^2 + t^2 - x a - y a - z a - t a,
  3 z^2 t + t^3 - 2 y t a - z t a - t^2 a + 2 y^2 + 2 z^2 - 3 y t + 3 z t + 2 t^2
  - x a - y a - 3 z a - 2 t a + a^2 - 3 x - y + 4 a,
  3 z t^2 + t^3 - 2 y t a - z t a - t^2 a - y^2 - z^2 - 3 y t + 2 t^2 - x a + 2 y
  a + t a + a^2 - y + a,
  z^3 - t^3 - z^2 a + y t a - z t a + t^2 a + y^2 + z^2 - t^2 + x a - y a - a^2 -
  x + y,
  y^3 - t^3 - y^2 a + t^2 a + y^2 - z^2 - 2 t^2 - y a + z a + 2 t a + y - t,
  12 t^4 - 12 t^3 a + 20 t^3 - 9 y^2 a + 6 z^2 a + 14 y t a - 14 z t a - 11 t^2 a
  + 9 y a^2 - 6 z a^2 - 9 t a^2 - 11 y^2 - 2 z^2 + 6 y t - 6 z t + 7 t^2 - 5 x a +
  4 y a + 9 z a - 4 t a + 2 a^2 + 9 x - 5 y + 9 z + 9 t - 22 a,
  [12 Polynomials]
  
  *** PART B: GO ON THE WALK TO FIND A LEX GROEBNER BASIS ***
  
  Here are the polynomials in the Source Groebner Basis:
  y z - y t - x + a,
  x z - z t + y - a,
  x t - y t - z + a,
  x y - z t + y - t,
  3 y t^2 - 2 y t a - z t a + t^3 - t^2 a - x a - y^2 + 3 y t + 2 y a + 2 z^2 - 3
  z a + 2 t^2 - 5 t a + a^2 - y + 3 z - 2 a,
  3 y^2 t - 2 y t a - z t a + t^3 - t^2 a - x a - y^2 + 3 y t - y a - z^2 - t^2 +
  t a + a^2 + 3 x - y - 2 a,
  x^2 - x a + y^2 - y a + z^2 - z a + t^2 - t a,
  -2 y t a + 3 z^2 t - z t a + t^3 - t^2 a - x a + 2 y^2 - 3 y t - y a + 2 z^2 + 3
  z t - 3 z a + 2 t^2 - 2 t a + a^2 - 3 x - y + 4 a,
  -2 y t a + 3 z t^2 - z t a + t^3 - t^2 a - x a - y^2 - 3 y t + 2 y a - z^2 + 2 t
  ^2 + t a + a^2 - y + a,
  y t a + z^3 - z^2 a - z t a - t^3 + t^2 a + x a + y^2 - y a + z^2 - t^2 - a^2 -
  x + y,
  y^3 - y^2 a - t^3 + t^2 a + y^2 - y a - z^2 + z a - 2 t^2 + 2 t a + y - t,
  12 t^4 - 12 t^3 a - 9 y^2 a + 14 y t a + 9 y a^2 + 6 z^2 a - 14 z t a - 6 z a^2
  + 20 t^3 - 11 t^2 a - 9 t a^2 - 5 x a - 11 y^2 + 6 y t + 4 y a - 2 z^2 - 6 z t +
  9 z a + 7 t^2 - 4 t a + 2 a^2 + 9 x - 5 y + 9 z + 9 t - 22 a,
  [12 Polynomials]
  
  *** PASS 1 ***
  
  Step 1: Calculating Initials...
  ........Initials Calculated.
  
  Step 2: Computing Groebner Basis of Initials...
  Added Polynomial #13 to Basis...
  Added Polynomial #14 to Basis...
  Added Polynomial #15 to Basis...
  ........Groebner Basis of Initials Computed.
  
  Step 3: Obtaining Lifted Groebner Basis...
  ........Obtained Lifted Groebner Basis of Size 13.
  
  Step 4: Finding Next Step on the Walk...
  ........Next step on Walk: 1, 1/2, 1/2, 1/2, 1/2, (t = 1/2).
  
  *** PASS 2 ***
  
  Step 1: Calculating Initials...
  ........Initials Calculated.
  
  Step 2: Computing Groebner Basis of Initials...
  Added Polynomial #14 to Basis...
  Added Polynomial #15 to Basis...
  Added Polynomial #16 to Basis...
  Added Polynomial #17 to Basis...
  Added Polynomial #18 to Basis...
  Added Polynomial #19 to Basis...
  ........Groebner Basis of Initials Computed.
  
  Step 3: Obtaining Lifted Groebner Basis...
  ........Obtained Lifted Groebner Basis of Size 13.
  
  Step 4: Finding Next Step on the Walk...
  ........Next step on Walk: 1, 0, 0, 0, 0, (t = 1).
  
  *** PASS 3 ***
  
  Step 1: Calculating Initials...
  ........Initials Calculated.
  
  Step 2: Computing Groebner Basis of Initials...
  ........Groebner Basis of Initials Computed.
  
  Step 3: Obtaining Lifted Groebner Basis...
  ........Obtained Lifted Groebner Basis of Size 4.
  
  Step 4: Finding Next Step on the Walk...
  ........No more steps.
  
  Here are the polynomials in the Target Groebner Basis:
  x + y t a + 3 y t - y a - z^3 + z^2 a - 3 z t^2 + 2 z t a - t^2 - t a - a,
  y t^2 + 2 y t + z^2 - z t^2 - z a + z - 2 t a - a,
  y^2 + y t a + 3 y t - 2 y a - z^3 + z^2 t + z^2 a + z^2 - 4 z t^2 + 2 z t a + z
  t - z a - t^2 - 2 t a,
  y z + y t a + 2 y t - y a - z^3 + z^2 a - 3 z t^2 + 2 z t a - t^2 - t a,
  [4 Polynomials]
  
  Writing Target Groebner Basis to Disk... Done.
  
  >
   
• Output File:
  
  > more examples/posso/posso07.lex
  x; y; z; t; a;
  x + y * t * a + 3 * y * t - y * a - z^3 + z^2 * a - 3 * z * t^2 + 2 * z * t * a
  - t^2 - t * a - a;
  y * t^2 + 2 * y * t + z^2 - z * t^2 - z * a + z - 2 * t * a - a;
  y^2 + y * t * a + 3 * y * t - 2 * y * a - z^3 + z^2 * t + z^2 * a + z^2 - 4 * z
  * t^2 + 2 * z * t * a + z * t - z * a - t^2 - 2 * t * a;
  y * z + y * t * a + 2 * y * t - y * a - z^3 + z^2 * a - 3 * z * t^2 + 2 * z * t
  * a - t^2 - t * a;
  >

3. Commutative Janet Bases

• Task: Compute a DegRevLex Janet Basis for the ideal generated by the set of polynomials $F = \{xy - z,~2x + yz + z\}$ over the polynomial ring $\mathbb{Q}[x, y, z]$.
   
• Input File:
  
  > more examples/test/test1.in
  x; y; z;
  x*y - z;
  2*x + y*z + z;
  >
   
• Session Output:
  
  > inv examples/test/test1.in
  
  *** JANET BASIS PROGRAM ***
  
  Using the DegRevLex Ordering with dictionary z < y < x
  
  Polynomials in the input basis:
  x y - z,
  y z + 2 x + z,
  [2 Polynomials]
  
  Computing an Involutive Basis...
  Added a first polynomial to G...
  Added a polynomial to G (2)...
  Added a polynomial to G (3)..
  Added a polynomial to G (4)..
  ...Involutive Basis Computed.
  
  Here is the Involutive Basis (Multiplicative Variables in brackets):
  y z + 2 x + z (x y z),
  2 x^2 z + x z^2 + z^3 (x z),
  x y - z (x y),
  2 x^2 + x z + z^2 (x),
  [4 Polynomials]
  
  Computing the Reduced Groebner Basis...
  ...Reduced Groebner Basis Computed.
  
  Here is the Reduced Groebner Basis:
  y z + 2 x + z,
  x y - z,
  2 x^2 + x z + z^2,
  [3 Polynomials]
  
  Writing Reduced Groebner Basis to Disk... Done.
  Writing Involutive Basis to Disk... Done.
  
  >
   
• Output Files:
  
  > more examples/test/test1.drl.inv
  x; y; z;
  y * z + 2 * x + z; (x y z);
  2 * x^2 * z + x * z^2 + z^3; (x z);
  x * y - z; (x y);
  2 * x^2 + x * z + z^2; (x);
  > more examples/test/test1.drl
  x; y; z;
  y * z + 2 * x + z;
  x * y - z;
  2 * x^2 + x * z + z^2;
  >

4. Commutative Pommaret Bases

• Task: Compute a DegRevLex Pommaret Basis for the ideal generated by the set of polynomials $F = \{-x^3 + x^2y - x^2 - xy^2 + x + y^3 - y^2 - y + 1,~ x^2 - 2xy + 3y^2 - 2y - 1\}$ over the polynomial ring $\mathbb{Q}[x, y]$.
   
• Input File:
  
  > more examples/posso/posso12.in
  x; y;
  -x^3 + x^2*y - x^2 - x*y^2 + x + y^3 - y^2 - y + 1;
  x^2 - 2*x*y + 3*y^2 - 2*y - 1;
  >
   
• Session Output:
  
  > inv -s2 examples/posso/posso12.in
  
  *** POMMARET BASIS PROGRAM ***
  
  Using the DegRevLex Ordering with dictionary y < x
  
  Polynomials in the input basis:
  -1 x^3 + x^2 y - x y^2 + y^3 - x^2 - y^2 + x - y + 1,
  x^2 - 2 x y + 3 y^2 - 2 y - 1,
  [2 Polynomials]
  
  Computing an Involutive Basis...
  Added a first polynomial to G...
  Added a polynomial to G (2)...
  Added a polynomial to G (3)..
  Discarded a polynomial from G (2)...
  Added a polynomial to G (3)...
  Added a polynomial to G (4)..
  ...Involutive Basis Computed.
  
  Here is the Involutive Basis:
  y^3 - x y - y,
  x^2 y^2 - x y^2 + 2 x y - 2 y^2 + 2 y,
  x^2 y - 2 x y^2 + 3 x y - 2 y^2 + 2 y,
  x^2 - 2 x y + 3 y^2 - 2 y - 1,
  [4 Polynomials]
  
  Computing the Reduced Groebner Basis...
  ...Reduced Groebner Basis Computed.
  
  Here is the Reduced Groebner Basis:
  y^3 - x y - y,
  x^2 - 2 x y + 3 y^2 - 2 y - 1,
  [2 Polynomials]
  
  Writing Reduced Groebner Basis to Disk... Done.
  Writing Involutive Basis to Disk... Done.
  
  >
   
• Output Files:
  
  > more examples/posso/posso12.drl.inv
  x; y;
  y^3 - x * y - y;
  x^2 * y^2 - x * y^2 + 2 * x * y - 2 * y^2 + 2 * y;
  x^2 * y - 2 * x * y^2 + 3 * x * y - 2 * y^2 + 2 * y;
  x^2 - 2 * x * y + 3 * y^2 - 2 * y - 1;
  > more examples/posso/posso12.drl
  x; y;
  y^3 - x * y - y;
  x^2 - 2 * x * y + 3 * y^2 - 2 * y - 1;
  >

5. Noncommutative Gröbner Bases

• Task: Compute a noncommutative DegLex Gröbner Basis for the ideal generated by the set of polynomials $F = \{Aa - 1,~ aA - 1,~ Bb - 1,~ bB - 1,~ a^3 - 1,~ b^2 - 1,~ (ab)^2 - 1\}$ over the polynomial ring $\mathbb{Q}\langle B, A, b, a\rangle$. Note: this corresponds to the computation of a complete rewrite system for the group $S_3$ using the Knuth-Bendix critical pairs completion algorithm [9] (the input set of polynomials corresponds to a monoid rewrite system for the group presentation $S_3 = \langle b, a \mid a^3, b^2, (ab)^2\rangle$).
   
• Input File:
  
  > more examples/rws/s3.in
  B; A; b; a;
  A*a - 1;
  a*A - 1;
  B*b - 1;
  b*B - 1;
  a^3 - 1;
  b^2 - 1;
  (a*b)^2 - 1;
  >
   
• Session Output:
  
  > ncgrob -d examples/rws/s3.in
  
  *** NONCOMMUTATIVE GROEBNER BASIS PROGRAM ***
  
  Using the DegLex Ordering with ordering a < b < A < B
  
  Polynomials in the input basis:
  A a - 1,
  a A - 1,
  B b - 1,
  b B - 1,
  a^3 - 1,
  b^2 - 1,
  a b a b - 1,
  [7 Polynomials]
  
  Computing Groebner Basis...
  Added Polynomial #8 to Basis...
  Added Polynomial #9 to Basis...
  Added Polynomial #10 to Basis...
  Added Polynomial #11 to Basis...
  Added Polynomial #12 to Basis...
  Added Polynomial #13 to Basis...
  Added Polynomial #14 to Basis...
  Added Polynomial #15 to Basis...
  Added Polynomial #16 to Basis...
  ...Groebner Basis Computed.
  
  Here is the Groebner Basis:
  A a - 1,
  a A - 1,
  B b - 1,
  b B - 1,
  a^3 - 1,
  b^2 - 1,
  a b a b - 1,
  B - b,
  a^2 - A,
  A^2 - a,
  a b a - b,
  b a b - A,
  A b a - a b,
  a b A - b a,
  b A - a b,
  A b - b a,
  [16 Polynomials]
  
  Computing the Reduced Groebner Basis...
  ...Reduced Groebner Basis Computed.
  
  Here is the Reduced Groebner Basis:
  A a - 1,
  a A - 1,
  b^2 - 1,
  B - b,
  a^2 - A,
  A^2 - a,
  a b a - b,
  b a b - A,
  b A - a b,
  A b - b a,
  [10 Polynomials]
  
  Writing Reduced Groebner Basis to Disk... Done.
  
  >
   
• Output File:
  
  > more examples/rws/s3.deg
  B; A; b; a;
  A*a - 1;
  a*A - 1;
  b^2 - 1;
  B - b;
  a^2 - A;
  A^2 - a;
  a*b*a - b;
  b*a*b - A;
  b*A - a*b;
  A*b - b*a;
  >

6. Logged Noncommutative Gröbner Bases

• Task: Compute a logged noncommutative Wreath Product Gröbner Basis for the ideal generated by the set of polynomials $F = \{aA - 1,~ Aa - 1,~ bB - 1,~ Bb - 1,~ a^3 - b^2\}$ over the polynomial ring $\mathbb{Q}\langle A, a, B, b\rangle$.
   
• Input File:
  
  > more examples/wreath/wreath2.in
  A; a; B; b;
  a*A-1;
  A*a-1;
  b*B-1;
  B*b-1;
  a^3 - b^2;
  >
   
• Session Output:
  
  > ncgrob -q -w examples/wreath/wreath2.in
  
  *** NONCOMMUTATIVE GROEBNER BASIS PROGRAM ***
  
  Using the Wreath Product Ordering with ordering b < B < a < A
  
  Polynomials in the input basis:
  a A - 1,
  A a - 1,
  b B - 1,
  B b - 1,
  a^3 - b^2,
  [5 Polynomials]
  
  Computing Groebner Basis...
  Added Polynomial #6 to Basis...
  Added Polynomial #7 to Basis...
  Added Polynomial #8 to Basis...
  Added Polynomial #9 to Basis...
  Added Polynomial #10 to Basis...
  Added Polynomial #11 to Basis...
  Added Polynomial #12 to Basis...
  Added Polynomial #13 to Basis...
  Added Polynomial #14 to Basis...
  Added Polynomial #15 to Basis...
  Added Polynomial #16 to Basis...
  Added Polynomial #17 to Basis...
  Added Polynomial #18 to Basis...
  ...Groebner Basis Computed.
  
  Here is the Groebner Basis:
  a A - 1,
  A a - 1,
  b B - 1,
  B b - 1,
  a^3 - b^2,
  b^2 a - a b^2,
  A b^2 - a^2,
  b^2 A - a^2,
  B a b^2 - b a,
  A b - a^2 B,
  b A - B a^2,
  A - a^2 B^2,
  B a^2 b - b a^2 B,
  B^2 a^2 - a^2 B^2,
  B a b - b a B,
  a^2 B^2 a - 1,
  B a^2 - b a^2 B^2,
  B a - b a B^2,
  [18 Polynomials]
  
  Computing the Reduced Groebner Basis...
  ...Reduced Groebner Basis Computed.
  
  Here is the Reduced Groebner Basis:
  b B - 1,
  B b - 1,
  a^3 - b^2,
  b^2 a - a b^2,
  A - a^2 B^2,
  B a - b a B^2,
  [6 Polynomials]
  
  Writing Reduced Groebner Basis to Disk... Done.
  Writing Quotients to Disk... Done.
  
  >
   
• Output Files:
  
  > more examples/wreath/wreath2.wp
  A; a; B; b;
  b*B - 1;
  B*b - 1;
  a^3 - b^2;
  b^2*a - a*b^2;
  A - a^2*B^2;
  B*a - b*a*B^2;
  > more examples/wreath/wreath2.wp.q
  F1; F2; F3; F4; F5; A; a; B; b;
  F3;
  F4;
  F5;
  -F5*a + a*F5;
  -A*F5*B^2 - A*b*F3*B - A*F3 + F2*a^2*B^2;
  B*F5*a*B^2 - B*a*F5*B^2 - B*a*b*F3*B - B*a*F3 + F4*b*a*B^2;
  >

7. Noncommutative Involutive Bases 1

• Task: Using the DegLex monomial ordering and the Left involutive division [5], compute a noncommutative Involutive Basis for the ideal generated by the set of polynomials $F = \{x^2 - 2xy + 3,~2xy + y^2 + 5\}$ over the polynomial ring $\mathbb{Q}\langle x, y\rangle$.
   
• Input File:
  
  > more examples/test/test2.in
  x; y;
  - 2*x*y + x*x + 3;
  2*x*y + y*y + 5;
  >
   
• Session Output:
  
  > ncinv -d examples/test/test2.in
  
  *** NONCOMMUTATIVE INVOLUTIVE BASIS PROGRAM (GLOBAL DIVISION) ***
  
  Using the DegLex Ordering with ordering y < x
  
  Polynomials in the input basis:
  x^2 - 2 x y + 3,
  2 x y + y^2 + 5,
  [2 Polynomials]
  
  Computing an Involutive Basis...
  Added a first polynomial to G...
  Added a polynomial to G (2)...
  Added a polynomial to G (3)...
  Added a polynomial to G (4)...
  Added a polynomial to G (5)...
  Discarded a polynomial from G (4)...
  Discarded a polynomial from G (3)...
  Added a polynomial to G (4)...
  Added a polynomial to G (5)...
  Added a polynomial to G (6)...
  Discarded a polynomial from G (5)...
  Discarded a polynomial from G (4)...
  Added a polynomial to G (5)...
  Added a polynomial to G (6)...
  Added a polynomial to G (7)...
  Discarded a polynomial from G (6)...
  Discarded a polynomial from G (5)...
  Discarded a polynomial from G (4)...
  Discarded a polynomial from G (3)...
  Discarded a polynomial from G (2)...
  Discarded a polynomial from G (1)...
  Added a polynomial to G (2)...
  Added a polynomial to G (3)...
  Added a polynomial to G (4)...
  Added a polynomial to G (5)...
  ...Involutive Basis Computed.
  
  Here is the Involutive Basis
  ((Left, Right) Multiplicative Variables in Brackets):
  2 y x + y^2 + 5, (y x, 1),
  2 x y + y^2 + 5, (y x, 1),
  x^2 + y^2 + 8, (y x, 1),
  5 y^3 - 10 x + 37 y, (y x, 1),
  5 x y^2 + 5 x - 6 y, (y x, 1),
  [5 Polynomials]
  
  Computing the Reduced Groebner Basis...
  ...Reduced Groebner Basis Computed.
  
  Here is the Reduced Groebner Basis:
  2 y x + y^2 + 5,
  2 x y + y^2 + 5,
  x^2 + y^2 + 8,
  5 y^3 - 10 x + 37 y,
  [4 Polynomials]
  
  Writing Reduced Groebner Basis to Disk... Done.
  Writing Involutive Basis to Disk... Done.
  
  >
   
• Output Files:
  
  > more examples/test/test2.deg.inv
  x; y;
  2*y*x + y^2 + 5; (y x, 1);
  2*x*y + y^2 + 5; (y x, 1);
  x^2 + y^2 + 8; (y x, 1);
  5*y^3 - 10*x + 37*y; (y x, 1);
  5*x*y^2 + 5*x - 6*y; (y x, 1);
  > more examples/test/test2.deg
  x; y;
  2*y*x + y^2 + 5;
  2*x*y + y^2 + 5;
  x^2 + y^2 + 8;
  5*y^3 - 10*x + 37*y;
  >

8. Noncommutative Involutive Bases 2

• Task: Using the DegRevLex monomial ordering and the Left overlap involutive division [5], compute a noncommutative Involutive Basis for the ideal generated by the set of polynomials $F = \{x^3 + 3xy + y^3,~x + y^2\}$ over the polynomial ring $\mathbb{Q}\langle x, y\rangle$.
   
• Input File:
  
  > more examples/posso/posso14.in
  x; y;
  x^3 + 3*x*y + y^3;
  x + y^2;
  >
   
• Session Output:
  
  > ncinv -s1 examples/posso/posso14.in
  
  *** NONCOMMUTATIVE INVOLUTIVE BASIS PROGRAM (LOCAL DIVISION) ***
  
  Using the DegRevLex Ordering with ordering y < x
  
  Polynomials in the input basis:
  y^3 + x^3 + 3 x y,
  y^2 + x,
  [2 Polynomials]
  
  Computing an Involutive Basis...
  Added a first polynomial to G...
  Added a polynomial to G (2)...
  Added a polynomial to G (3)...
  Discarded a polynomial from G (2)...
  Discarded a polynomial from G (1)...
  Added a polynomial to G (2)...
  Added a polynomial to G (3)...
  ...Involutive Basis Computed.
  
  Here is the Involutive Basis
  ((Left, Right) Multiplicative Variables in Brackets):
  x^3 + 2 y x, (y x, 1),
  y^2 + x, (y x, x),
  x y - y x, (y x, x),
  [3 Polynomials]
  
  Computing the Reduced Groebner Basis...
  ...Reduced Groebner Basis Computed.
  
  Here is the Reduced Groebner Basis:
  x^3 + 2 y x,
  y^2 + x,
  x y - y x,
  [3 Polynomials]
  
  Writing Reduced Groebner Basis to Disk... Done.
  Writing Involutive Basis to Disk... Done.
  
  >
   
• Output Files:
  
  > more examples/posso/posso14.drl.inv
  x; y;
  x^3 + 2*y*x; (y x, 1);
  y^2 + x; (y x, x);
  x*y - y*x; (y x, x);
  > more examples/posso/posso14.drl
  x; y;
  x^3 + 2*y*x;
  y^2 + x;
  x*y - y*x;
  >

9. Noncommutative Involutive Bases 3

• Task: Using the Wreath Product monomial ordering; the Strong Right Overlap involutive division [5]; and thick divisors [5], compute a noncommutative Involutive Basis for the ideal generated by the set of polynomials $F = \{xy - z,~2x + yz + z,~x + yz\}$ over the polynomial ring $\mathbb{Q}\langle x, y, z \rangle$.
   
• Input File:
  
  > more examples/test/test3.in
  x; y; z;
  x*y - z;
  2*x + y*z + z;
  x + y*z;
  >
   
• Session Output:
  
  > ncinv -s2 -e2 -m2 -w examples/test/test3.in
  
  *** NONCOMMUTATIVE INVOLUTIVE BASIS PROGRAM (LOCAL DIVISION) ***
  
  Using the Wreath Product Ordering with ordering z < y < x
  
  Polynomials in the input basis:
  x y - z,
  2 x + y z + z,
  x + y z,
  [3 Polynomials]
  
  Computing an Involutive Basis...
  Added a first polynomial to G...
  Added a polynomial to G (2)...
  Added a polynomial to G (3)...
  Discarded a polynomial from G (2)...
  Discarded a polynomial from G (1)...
  Added a polynomial to G (2)...
  Added a polynomial to G (3)...
  Added a polynomial to G (4)...
  Added a polynomial to G (5)...
  ...Involutive Basis Computed.
  
  Here is the Involutive Basis
  ((Left, Right) Multiplicative Variables in Brackets):
  z^2, (1, z y x),
  y z - z, (y, z y x),
  z y + z, (1, z y x),
  z x, (1, z y x),
  x + z, (y, z y x),
  [5 Polynomials]
  
  Computing the Reduced Groebner Basis...
  ...Reduced Groebner Basis Computed.
  
  Here is the Reduced Groebner Basis:
  z^2,
  y z - z,
  z y + z,
  x + z,
  [4 Polynomials]
  
  Writing Reduced Groebner Basis to Disk... Done.
  Writing Involutive Basis to Disk... Done.
  
  >
   
• Output Files:
  
  > more examples/test/test3.wp.inv
  x; y; z;
  z^2; (1, z y x);
  y*z - z; (y, z y x);
  z*y + z; (1, z y x);
  z*x; (1, z y x);
  x + z; (y, z y x);
  > more examples/test/test3.wp
  x; y; z;
  z^2;
  y*z - z;
  z*y + z;
  x + z;
  >
   

References

[1] B. Buchberger. A Criterion for Detecting Unnecessary Reductions in the Construction of Gröbner Bases. In Symbolic and Algebraic Computation (EUROSAM ’79, Int. Symp., Marseille, 1979), volume 72 of Lecture Notes in Comput. Sci., 3–21. Springer, Berlin (1979).

[2] B. Buchberger. An Algorithmic Criterion for the Solvability of a System of Algebraic Equations. Translation of PhD thesis by M. Abramson and R. Lumbert. In B. Buchberger and F. Winkler, editors, Gröbner Bases and Applications, volume 251 of Proc. London Math. Soc., 535–545. Cambridge University Press (1998).

[3] J. Calmet, M. Hausdorf and W. M. Seiler. A Constructive Introduction to Involution. In R. Akerkar, editor, Proc. Int. Symp. Applications of Computer Algebra – ISACA 2000, 33–50. Allied Publishers, New Delhi (2001).

[4] M. Collart, M. Kalkbrener and D. Mall. Converting Bases with the Gröbner Walk. J. Symbolic Comput. 24 (3-4) (1997) 465–469.
http://dx.doi.org/10.1006/jsco.1996.0145

[5] G. A. Evans. Noncommutative Involutive Bases. (PhD Thesis, University of Wales, Bangor). September 2005.
http://arxiv.org/abs/math/0602140

[6] FreeBSD Operating System.
http://www.freebsd.org

[7] V. P. Gerdt and Yu. A. Blinkov. Involutive Bases of Polynomial Ideals. Math. Comput. Simulation 45 (1998) 519–541

[8] A. Giovini, T. Mora, G. Niedi, L. Robbiano and C. Traverso. “One sugar cube, please” OR Selection Strategies in Buchberger Algorithm. In ISSAC ’91: Proc. Int. Symp. Symbolic and Algebraic Computation, 49–54. ACM Press, New York (1991).
http://dx.doi.org/10.1145/120694.120701

[9] D. E. Knuth and P. B. Bendix. Simple word problems in universal algebras. In Leech, J., ed.: Computational Problems in Abstract Algebra, Pergamon Press (1970) 263–297

[10] T. Mora. Gröbner Bases for non-commutative polynomial rings. In Calmet, J., ed.: AAECC-3: Proc. 3rd Int. Conf. on Algebraic Algorithms and Error-Correcting Codes (Grenoble, France, July 15–19, 1985). Volume 223 of Lecture Notes in Comput. Sci. Springer (1986) 353–362

[11] MSSRC (Multidisciplinary Software Systems Research Corporation).
http://www.mssrc.com

[12] A. Yu. Zharkov and Yu. A. Blinkov. Involution Approach to Investigating Polynomial Systems. Math. Comput. Simulation 42 (4-6) (1996) 323–332.
http://dx.doi.org/10.1016/S0378-4754(96)00006-7