The monomial set of a polynomial \(f\) is the set of monomials with nonzero coefficient in \(f\), and is denoted by \(\mathrm{Mon}(f)\). For \(K \subseteq k[x_1, \cdots , x_n]\), we define as

Input: \(L\), \(G = \{ f_1, \cdots , f_t \} \) (two finite sets of polynomials)

Output: \(H\) (a finite set of polynomial containing \(L\))

• \(H := L\)

• \(done := \mathrm{LM}(H)\)

• while \(done \ne \mathrm{Mon}(H)\):

  • \(x^\beta := \max _{{\lt}} (\mathrm{Mon}(H) \, \backslash \, done)\)

  • \(done := done \cup \{ x^\beta \} \)

  • if \(\exists g \in G\) such that \(\mathrm{LM}(g) \mid x^\beta \):

    • \(g :=\) one such choice of \(g\)

    • \(H := H \cup \left\{ \frac{x^\beta }{\mathrm{LM}(g)} g \right\} \)

  return \(H\)

The algorithm above with input \(L\) and \(G\) terminates and obtains as an output a set of polynomials \(H\) satisfying the following two properties:

1. \(L \subseteq H\), and

2. whenever \(x^\beta \) is a monomial in some \(f \in H\), and for some \(g \in G\) its leading monomial \(\mathrm{LM}(g)\) divides \(x^\beta \), then \(\frac{x^\beta }{\mathrm{LM}(g)} g \in H\).

Input: \(F = \{ f_1, \cdots , f_s \} \) (a generating set of polynomials of an ideal)

Output: \(G\) (a Gröbner basis of the ideal, containing \(F\))

• \(G := F\)

• \(t := s\)

• \(B := \{ \{ i, j\} \mid 1 \le i {\lt} j \le s\} \)

• while \(B \ne \emptyset \):

  • \(B' := \textrm{a nonempty subset of } B\)

  • \(B := B \, \backslash \, B'\)

  • \(L := \left\{ \frac{\mathrm{lcm}(\mathrm{LM}(f_i), \mathrm{LM}(f_j))}{\mathrm{LT}(f_i)} f_i \mid \{ i, j\} \in B' \right\} \)

  • \(H := SymbolicPreprocessing(L, G)\)

  • \(M := (\mathrm{coeff}(h_k, x^{\alpha _\ell }))_{k, \ell }\)
    (the matrix of coefficients of H; \(x^{\alpha _\ell }\) sorted under monomial order)

  • \(N := \textrm{row reduced echelon form of } M\)

  • \(N^+ := \{ n \in \mathrm{rows}(N) \mid \mathrm{LM}(n) \notin \left\langle \mathrm{LM}(\mathrm{rows}(N)) \right\rangle \} \)

  • for \(n \in N^+\):

    • \(t := t + 1\)

    • \(f_t := \textrm{the polynomial form of } n\)

    • \(G := G \cup \{ f_t\} \)

    • \(B := B \cup \{ \{ i, t\} \mid 1 \le i {\lt} t\} \)

  return \(G\)