1 Definitions
The multiset consisting of the maximal variable of \(p\), repeated according to its degree. Its cardinality is the degree in that variable; constants and zero have the empty multiset.
The rank of a polynomial \(p\) is the pair \((mainVar(p), |mainDegree(p)|)\) ordered lexicographically.
\(q\) is reduced with respect to \(p\) if \(q = 0\), or \(p\) has a main variable and the degree of \(q\) in that variable is strictly less than the degree of \(p\) in the same variable.
\(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 nonconstant polynomial \(p\) is the initial with respect to its class. The initial of zero is zero, and the initial of a nonzero constant is one.
The product of initials of a set of polynomials.
A Triangular Set is a finite ordered sequence of non-zero polynomials with strictly increasing classes.
The rank of a Triangular 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 Triangular 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 init(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 Triangular Set is an Ascending Set if every element is reduced with respect to its predecessors. This is the standard (Ritt) ascending-set predicate.
A Triangular 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, parameterized by an ascending-set predicate. 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.
Update \(BS\) using \(BS.takeConcat(B)\), retaining a prefix and appending \(B\).
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\) using an explicitly supplied ascending-set predicate.
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_0 ++ RS ++ BS\) and go to step 2.
Termination is guaranteed by the well-ordering of orders.
Decomposes the zero set of a polynomial list into a union of zero sets of triangular sets, using an explicitly supplied ascending-set predicate. The algorithm recursively computes the characteristic set \(CS\) and adds branches for the initials of \(CS\).