1 Definitions
The class of a multivariate polynomial \(p\) is the largest variable index appearing in \(p\).
The degree of \(p\) with respect to its class.
The rank of a polynomial \(p\) is the pair \((mainVar(p), deg(p))\) ordered lexicographically.
\(q\) is reduced with respect to \(p\) if the degree of \(q\) in the main variable of \(p\) is strictly less than the main degree of \(p\).
\(q\) is reduced with respect to a polynomial set \(PS\) if it is reduced with respect to all elements of \(PS\).
The initial of a polynomial \(p\) with respect to a variable \(i\). It is the coefficient of the highest power of \(x_i\) appearing in \(p\).
The initial of a polynomial \(p\) is the initial with respect to its class.
The product of initials of a set of polynomials.
A Triangulated Set is a finite ordered sequence of non-zero polynomials with strictly increasing classes.
The rank of a Triangulated Set is a lexicographic sequence of ranks of its polynomials. More intuitively, \(S {\lt} T\) if one of the following two occurs:
There exists some \(k {\lt} S.length\) such that \(S_0 \sim T_0, S_1 \sim T_1, ..., S_{k-1} \sim T_{k-1}\), while \(S_k {\lt} T_k\).
\(S.length {\gt} T.length\) and \(\forall i {\lt} T.length, S_i \sim T_i\).
"S.takeConcat p" tries to construct a new Triangulated Set by taking a prefix of \(S\) and appending \(p\).
If \(p\) fits naturally at the end of \(S\), it behaves like "S.concat p".
If \(p\) conflicts with some element in \(S\) (in terms of class order), "takeConcat" finds the first element in \(S\) that has a higher or equal class than \(p\), truncates \(S\) before that element, and appends \(p\).
A remainder \(r\) of \(g\) by \(f\) is a polynomial which is reduced with respect to \(f\) and satisfies \(init(f)^s \cdot g = q \cdot f + r\) for some \(s \in \mathbb {N}\) and \(q \in R[X_{\sigma }]\).
A remainder \(r\) of \(g\) by a set \(S\) is a polynomial which is reduced with respect to \(S\) and satisfies \((\prod S_i^{e_i}) \cdot g = \sum q_i \cdot S_i + r\) for some \(\{ e_i\} \) and \(\{ q_i\} \).
Pseudo-division of \(g\) by \(f\) with respect to \(i\).
Returns a triple containing the exponent, the quotient and the remainder.
Pseudo-division of \(g\) by \(f\) with respect to \(mainVar(f)\).
Returns a triple containing the exponent, the quotient and the remainder.
Pseudo-divides \(g\) successively by elements of \(S\). Typically, this involves dividing by \(S_{l-1}\), then \(S_{l-2}\), ..., down to \(S_0\).
Returns a triple containing the exponents, the quotients and the remainder.
A Triangulated Set is an Ascending Set if every element is reduced with respect to its predecessors. Here "reduced" is an abstract predicate.
A Triangulated Set is a Standard Ascending Set if every element is reduced with respect to its predecessors.
A Triangulated Set is a Weak Ascending Set if the initial of every element is reduced with respect to its predecessors.
The interface for algorithms computing Basic Sets. Any instance of this class provides a "basicSet" function that computes a minimal ascending set contained in a given list of polynomials.
Computes the Standard Basic Set of a list of polynomials.
The algorithm works by:
Sort the list and let \(BS = \emptyset \).
Pick the first (minimal) element \(B\) in the list.
Append \(B\) to the tail of the current basic set \(BS\).
Filter the remaining list to keep only elements reduced w.r.t. the new \(BS\) and go to step 2.
Computes the Weak Basic Set of a list of polynomials.
Difference from Standard: The filter condition includes \(mainVar(p) {\gt} mainVar(B)\).
\(CS\) is a characteristic set of \(PS\) if every polynomial in \(PS\), \(0\) is its remainder by \(CS\), and \(Zero(PS) \subseteq Zero(CS)\).
Computes the Characteristic Set of a polynomial list \(l\).
Algorithm:
Set \(l_0 = l\).
Compute \(BS = BasicSet(l)\).
Compute remainders \(RS\) of \(l \setminus BS\) with respect to \(BS\).
If \(RS = \emptyset \), \(BS\) is the characteristic set.
If not, let \(l = l₀ ++ RS ++ BS\) and go to step 2.
Termination is guaranteed by the well-ordering of ranks.
Decomposes the zero set of a polynomial list into a union of zero sets of triangular sets. The algorithm recursively computes the characteristic set \(CS\) and adds branches for the initials of \(CS\).