2. The standard basis algorithm in SINGULAR

In SINGULAR the standard basis algorithm is implemented as follows:

S := StandardBasis $(\bf G)$

INPUT: G, a set of polynomial vectors $\subset K[x]^r$
OUTPUT: S, a standard base of the submodule generated by G with respect to the given monomial ordering

S := G^h
update (S)
HCtest
T := S
L := initPairs (S)
clear (S)
WHILE $\; L \not= \emptyset\;$ DO

p := (a, b, s) the last element from L
$L := L \backslash \{(a, b, s)\}$
IF the spoly of a and b is not computed yet THEN

s := spoly (a, b)

END

h := LazyNF (p | T)
IF $\; h \not= 0\;$ THEN

HCtest
updatePairs (h)
$S := S \cup \{ h \}$
clear (S)
$T := T \cup \{ h\}$

END

END
S:= completeReduce (S).

Remark 2..1   In cases when either < is a wellordering, or $G \subseteq K[x]$ and $\dim_K K[x]/ \langle G \rangle < \infty$ the standard basis is uniquely determined. Moreover, in this case we can achieve a presentation $(\ast)$ as in 1.12 (2) with $\xi_i \in K[x]$, $h \in K[x]^r$.

During the algorithm the set S is sorted by increasing monomial ordering of the leading terms of the elements with respect to

$$\pmatrix{0 & 0, \ldots, 0\cr 0 & \cr \vdots & A\cr 0 & \cr}.$$

The set T (respectively L) is sorted by increasing (respectively decreasing) monomial ordering of the leading terms of the elements (respectively the S-polynomial of the corresponding pair) with respect to

$$\pmatrix{ 1 & 1, \ldots, 1\cr 0 & \cr \vdots & A\cr 0 & \cr}$$

or

$$\pmatrix{1 & w_1, \ldots, w_n\cr 0 & \cr \vdots & A\cr 0 & } \mbox{ if we use the weighted ecart method}.$$

Now we explain the procedures used in the standard basis algorithm:

Update $(\bf S)$
INPUT: S, a set of polynomial vectors
OUTPUT: S, the set of polynomial vectors after the interreduction

for all $s \in S\;$ DO $\; s :=$ NFBuchberger $(s \mid S \backslash \{s\})$.

HCtest
INPUT: S, a set of polynomials
OUTPUT: a boolean value (does a ``highest corner'' exist?) and, if so, the monomial ``highest corner''

If $G \subseteq K[x]$ (that is r = 1) then it tests if there are $a_i,\, \alpha_i \ge 0$ such that $t^{a_i} x_i^{\alpha_i}$ occur as leading terms in S for all i. If this is true it computes the minimal monomial $x^\alpha$ (with respect to the ordering < in K[x]) which is not in the ideal generated by the leading terms of the elements of S(t = 1). This monomial is called ``highest corner''.

It changes the polynomial arithmetic to cancel all monomials $t^a x^\beta$ with $x^\beta < x^\alpha$ in further computations.

Remark 2..2   Notice that the highest corner $x^\alpha$ is equal to 1 in the case of a wellordering. Therefore, the procedure is called only if x_i < 1 for some i. The highest corner is computed in a combinatorial manner.

1cm

$\bullet$ correspond to leading terms of S(t = 1), $\bf\times$ corresponds to the ``highest corner'' $x^\alpha$.

$\bf L :=$ initPairs $(\bf S)$
INPUT: S, a set of (interreduced) polynomial vectors
OUTPUT: L, the set of critical pairs

It creates the pairset $L = \{(f, g, s) \mid f, g \in S$, s the leading term of spoly$(f,g)\}$. Using the criteria similar to Gebauer-Möller (cf. [GM]) useless pairs are cancelled.

We have two options: usually the criteria are applied for the pairs $\{(f(t=1),\; g(t=1)) \mid f, g \in S\},$ that is in K[x]. In the option sugar crit we apply it to L using the idea of [GMNRT].

Clear $(\bf S)$
INPUT and OUTPUT: S, a set of polynomial vectors

Deletes f from S if $L(g) \mid t^\alpha L(f)$ for some $\alpha$ and $g\in S$.

Update $(\bf h)$
INPUT and OUTPUT: h, a polynomial vector

IF    sugar     THEN RETURN END
IF    t|h     THEN

choose $\alpha$ maximal such that $t^\alpha\vert h$
$h := {h\over t^\alpha}$

END

UpdatePairs $(\bf h)$
INPUT: h, a polynomial vector
S, a set of polynomial vectors
OUTPUT: L, the set of critical pairs from S and h

It updates the pairset L.
$L := L \cup \{(f, h, s) \mid f \in S$, s the leading term of spoly$(f, h)\}$.
The criteria to cancel useless pairs are used as in initPairs.

h := LazyNF $((\bf a, b, s) \mid T)$
INPUT: s, a polynomial vector to reduce
(a,b), the critical pair from which s is the spoly
T, a set of polynomials with which to reduce
OUTPUT: h, the reduced polynomial vector

h := s
WHILE exist $f \in T$ such that $L(f) \mid t^\alpha L(h)$ for some $\alpha\;$ DO

choose the first possible f with respect to the ordering in T such that $\alpha$ is minimal.
IF $\;\alpha > 0\;$ THEN

IF the position of (a, b, h) in L is not the last one THEN
$L:= L \cup \{(a, b, h)\}$
RETURN 0
END
$T := T \cup \{ h\}$
NFupdate pairs (h)

END
h:= spoly $(t^\alpha h, f)$
update (h)
IF degree (h) > degree(s)     and
the position of (a, b, h) in L is not the last one THEN

$L:= L \cup \{(a, b, h)\}$
RETURN 0

END

END

NFupdatePairs $(\bf h)$
INPUT: h, a polynomial vector
S, a set of polynomial vectors
OUTPUT: L the set of some critical pairs from S and h

IF NOT more pairs THEN RETURN END
$L := L \cup \{(f, h, s) \mid f \in S,\; \deg_t L(f) \le \deg_t L(h),\; s$ the leading term of spoly$(f, h)\}$
The criteria to cancel useless pairs are used as in initPairs.

Remark 2..3   The option morePairs (= more pairs in NFupdatePairs) has the effect of keeping some useless pairs in order to have better candidates for reduction. The leading idea is to keep (some of) those pairs which could not be discarded if we had used Lazard's method. In the case of a non-wellordering this has turned out to be useful, since it can help in not creating polynomials with too long tails during the normal form computation.

$\bf S :=$ completeReduce $(\bf S)$
INPUT and OUTPUT: S, a set of polynomial vectors

IF < is a wellordering or $(S \subseteq K[x]$ and $\dim_K K[x]/ \langle S \rangle < \infty)$
THEN

S:= S(t=1)
FOR all $s \in S$ DO

s := redtail (s|S)

END

ELSE

FOR all $s \in S$ DO

s := redtail (s|S)

END
S := S(t = 1)

END

$\bf s :=$ redtail $(\bf s\vert S)$
INPUT and OUTPUT: s, a polynomial vector

reduces the monomial below L(s) with elements from S as long as possible.