\documentstyle [fleqn,11pt]{article} \textheight 708pt \textwidth 485pt \topmargin -25pt \oddsidemargin -10pt \evensidemargin -10pt \parindent 1.8em \newcommand{\cs}{characteristic set~} \newcommand{\css}{characteristic sets~} \newcommand{\Cs}{Characteristic set~} \newcommand{\Css}{Characteristic sets~} \newcommand{\bs}{basic set~} \newcommand{\bss}{basic sets~} \newcommand{\Bs}{Basic set~} \newcommand{\Bss}{Basic sets~} \newcommand{\tf}{triangular form~} \newcommand{\tfs}{triangular forms~} \newcommand{\Tf}{Triangular form~} \newcommand{\Tfs}{Triangular forms~} \newcommand{\as}{ascending set~} \newcommand{\ass}{ascending sets~} \newcommand{\As}{Ascending set~} \newcommand{\Ass}{Ascending sets~} \newcommand{\p}{polynomial~} %\newcommand{\P}{Polynomial~} \newcommand{\Ps}{Polynomials~} \newcommand{\ps}{polynomials~} \newcommand{\g}{geometry~} \newcommand{\G}{Geometry~} \newcommand{\Gs}{Geometries} \newcommand{\gs}{geometries~} \newcommand{\r}{remainder~} \newcommand{\rs}{remainders~} \newcommand{\xx}{x_1, ..., x_n} \newcommand{\yy}{y_1, ..., y_r} \newcommand{\uu}{u_1, ..., u_d} \newcommand{\uy}{u_1, ..., u_d, y_1, ..., y_r} \newcommand{\k}{{\bf K}} \newcommand{\wrt}{with respect to~} \newcommand{\sone}{~~~~~~~~~~~~~~~} \newcommand{\stwo}{~~~~~~~~~~~~~~~~~~~~} \begin{document} ~ \noindent {\Large \bf An Implementation of Characteristic Sets Method in Maple\footnote{This work is supported in part by the Austrian Ministry of Science under ESPRIT Basic Research Action 3125 (MEDLAR).}} ~ \noindent {\small DONGMING WANG \noindent {\em Research Institute for Symbolic Computation, Johannes Kepler University, Linz, Austria and \noindent Institute of Systems Science, Academia Sinica, Beijing, China} ~ \bigskip \noindent {\bf Abstract.} This paper describes a complete implementation of Ritt-Wu's characteristic sets method in Maple system. The implemented algorithms include those with variants for computing characteristic sets of (multivariate) polynomial sets, decomposing polynomial sets into ascending sets and irreducible ascending sets, decomposing algebraic varieties into irreducible components, factorizing polynomials over algebraic number fields and solving systems of polynomial equations. Some modification, generalization of basic algorithms and implementation strategies are discussed. The timing statistics on a set of test problems is given. } \vskip 0.3cm \bigskip \noindent {\large \bf 1. Introduction and Notations} \bigskip \noindent The method of characteristic sets was introduced by J. F. Ritt [5, 6] in the context of his work on differential algebra in the early 1930's and was revitalized and further developed by Wu Wen-ts\"un [11-13] through his recent work on mathematics-mechanization. In addition to be a powerful tool for Wu's general theory and method of mechanical theorem proving, the characteristic set method has proved efficient for solving a wide class of problems in geometry and algebra (see, for example, the series work in [14]). It has been partially implemented by different research groups in China, USA and Austria [1, 3, 4, 14] for geometry theorem proving and solving other related problems. The author has learned that an implementation of this method in Reduce system is undergoing at University of Bath, England. However, to the best of our knowledge neither a complete implementation exists nor a partial implementation has been generally available in current symbolic and algebraic computation systems. In this paper we describe a complete, general-purpose implementation of the characteristic sets method, in considering mainly the zero structure of polynomial sets. This implementation will be included into the Maple system as a package under the name {\sf charsets} and can be considered as a practical basis for designing and implementing other related algorithms. The whole method of characteristic sets as well as its underlying theory has been well developed by Ritt and Wu. It provides extensive contents for dealing with systems of (multivariate) polynomials (as well as differential polynomials). For the present implementation we essentially follow Wu's improved version of the method but use the algorithmic form described in [7] by taking most remarks there into account. The implemented algorithms include those for computing characteristic sets of polynomial sets, decomposing polynomial sets into ascending sets and irreducible ascending sets, decomposing algebraic varieties into irreducible components, factorizing polynomials over algebraic number fields and solving systems of polynomial equations. We have supplied several possible variants of these algorithms in order to make the package more powerful and flexible. Speaking about the completeness of implementation, there ware difficulties concerning the polynomial factorization over successive algebraic extension fileds which is considered to be expensive in general and the determination of finite bases of ideals from their characteristic sets for which no simple and practical method was available. We have overcome these difficulties through the discovery of a new polynomial factorization method and the application of Gr\"obner bases to determine the finite bases. The characteristic sets method has an important application to mechanical theorem proving in geometries. On the basis of this package, the author has also developed a new and more powerful geometry theorem prover which provides again a first complete implementation of Wu's general method. That prover has been treated as part of a geometry problem solver (Geoper) under development and not included into this package. A detailed description of our geometry problem solver will be published elsewhere. In the later sections we shall describe the 15 user level functions, discuss the modification, generalization of some basic and utilized algorithms with our implementation strategies, and present a set of test results for all functions with variants. Before doing these, let us explain first our conventional notations which are similar to those used in [8] in order to avoid the confusion of those used by different authors. In the whole package all input polynomials are in parameters $u_1, ..., u_m$ and variables $x_1, ..., x_n$ with integer or rational coefficients. By a {\em constant} polynomial we shall mean one involving only the parameters. While the order of the variables is fixed, say, \[\stwo x_1\prec x_2\prec\cdots\prec x_n,\] we call the variable with biggest index occurring in a non-constant polynomial $F$ the {\em leading variable} of $F$, denoted as $lvar(F)$. The leading coefficients of a non-constant polynomial $F$ \wrt $lvar(F)$ is called the {\em initial} of $F$, denoted as $ini(F)$. A polynomial $G$ is said to be {\em reduced} \wrt $F$ if the degree of $G$ in $lvar(F)$ is less than the degree of $F$ in $lvar(F)$. A finite set of polynomials $\{A_1, A_2, ..., A_r\}$ is called a {\em quasi-ascending set} or a {\em triangular form} if either $r=1$ and $A_1\neq 0$, or $r>1$ and $lvar(A_1)\prec lvar(A_2)\prec\cdots\prec lvar(A_r)$. A quasi-ascending set $A\!S$ is said an {\em \as} if in the case $r>1$, $A_j$ is reduced with respect to $A_i$ for each pair $j>i$. A quasi-ascending set $A\!S$ is said a {\em weak \as} if in the case $r>1$, the initial of $A_j$ is reduced \wrt $A_i$ for each pair $j>i$. A (weak, quasi-) ascending set is said to be {\em contradictory} if it contains only one constant polynomial. Let $G$ be any non-zero polynomial and $A\!S=\{A_1, ..., A_r\}$ be a non-contradictory (weak, quasi-) ascending set. We can pseudo-divide $G$ successively by $A_r, ..., A_1$, considered as polynomials in their leading variables. The final remainder $R$ will be called the {\em pseudo-remainder} or simply the {\em remainder} of $G$ \wrt $A\!S$. Let $P\!S$ be a finite, non-empty set of non-zero polynomials. The set of all non-zero remainders of polynomials in $P\!S$ \wrt a (weak, quasi-) ascending set $A\!S$ will be called the {\em remainder set} of $P\!S$ \wrt $A\!S$. The set of all common zeros of polynomials in $P\!S$ will be denoted as $Zero(P\!S)$. If $G$ is any other non-zero polynomial, we abbreviate $Zero(P\!S)-Zero(G)$ as $Zero(P\!S/G)$. \bigskip \noindent {\large \bf 2. Description of User Functions} \bigskip \noindent In this section we describe 15 user level functions which provide a greater flexibility of using our package. There are two trivial functions {\sf iniset} and {\sf remset}, of which {\sf iniset} computes the set of all distinct factors of initials of polynomials in a non-contradictory (weak, quasi-) ascending set $A\!S$ and {\sf remset} computes the remainder set of a polynomial set $P\!S$ \wrt $A\!S$. The other 13 non-trivial functions are given below. \medskip \noindent 2.1. {\sf charset} and {\sf mcharset} \medskip \noindent A (weak, quasi-) ascending set $C\!S$ is said a ({\em weak, quasi-}) {\em characteristic set} of a polynomial set $P\!S$ if any polynomials in $C\!S$ is a linear combination of polynomials in $P\!S$ with polynomial coefficients (i.e., $C\!S$ is contained in the ideal generated by polynomials in $P\!S$) and the remainder set of $P\!S$ \wrt $C\!S$ is empty. For a characteristic set $C\!S$ of $P\!S$, we have therefore \[\stwo Zero(C\!S/J)\subset Zero(P\!S)\subset Zero(C\!S),\] where $J$ is the product of initials of polynomials in $C\!S$. A (weak, quasi-) ascending set $C\!S$ is said a {\em modified} ({\em weak, quasi-}) {\em characteristic set} of $P\!S$ if \[\stwo Zero(C\!S/J)\subset Zero(P\!S), ~~Zero(P\!S/F)\subset Zero(C\!S),\] where $J$ is the same as above and $F$ is a non-zero polynomial. The functions {\sf charset} and {\sf mcharset} compute respectively the (weak, quasi-) characteristic set and the modified (weak, quasi-) characteristic set of any polynomial set. In these two functions we have an option of 8 possible so-called {\em medial sets}: {\sf basset}, {\sf wbasset}, {\sf qbasset}, {\sf charsetn}, {\sf wcharsetn}, {\sf qcharsetn}, {\sf trisetc} and {\sf triset}. These medial sets correspond respectively to those computed by the algorithms {\sf BasicSet}, {\sf CharacteristicSetN}, {\sf TriangularSetC} and {\sf TriangularSet} described in [7, 8]. If {\sf basset}, {\sf charsetn} or {\sf trisetc} is chosen, then a characteristic set or modified characteristic set is returned; if {\sf wbasset} or {\sf wcharsetn} is chosen, then a weak characteristic set or modified weak characteristic set is returned; if {\sf qbasset}, {\sf qcharsetn} or {\sf triset} is chosen, then a quasi-characteristic set or modified quasi-characteristic set is returned. The default is {\sf charsetn}. \medskip \noindent 2.2. {\sf charser}, {\sf mcs}, {\sf ecs} and {\sf mecs} \medskip \noindent If a polynomial set $P\!S$ and a sequence of (weak) ascending sets $C\!S_1, ..., C\!S_e$ are such that \[\stwo Zero(P\!S)=\bigcup_{i=1}^e Zero(C\!S_i/J_i),\] where each $J_i$ is the product of initials of polynomials in $C\!S_i$, then $\{C\!S_1, ..., C\!S_e\}$ is called a ({\em weak}) {\em characteristic series} of $P\!S$. If they are such that \[\stwo Zero(P\!S/G)=\bigcup_{i=1}^e Zero(C\!S_i/F_i),\] where each $F_i$ is a polynomial with non-zero remainder \wrt $C\!S_i$, then $\{C\!S_1/F_1, ..., C\!S_e/F_e\}$ is called an {\em extended} ({\em weak}) {\em characteristic series} of $P\!S/G$. Both the functions {\sf charser} and {\sf mcs} compute a (weak) characteristic series of $P\!S$, and so do both the functions {\sf ecs} and {\sf mecs} an extended (weak) characteristic series of $P\!S/G$. The only difference between {\sf charser} and {\sf mcs} (respectively, {\sf ecs} and {\sf mecs}) is that for the latter which is in general fast for large problems, some factors are examined and allowed to be removed during the internal computation of characteristic sets. Since we are unable to say which is the best, both are kept in the package. In these four functions we have an option of 5 medial sets: {\sf basset}, {\sf wbasset}, {\sf charsetn}, {\sf qcharsetn} and {\sf trisetc} of which {\sf charsetn} is again the default. A characteristic series or an extended characteristic series is returned if {\sf basset}, {\sf charsetn} or {\sf trisetc} is chosen, and a weak characteristic series or an modified weak characteristic series is returned if any of the others is chosen. \medskip \noindent 2.3. {\sf triser} and {\sf csolve} \medskip \noindent The function {\sf triser} computes, form a polynomial set $P\!S$, a sequence of ascending, weak or quasi-ascending sets $C\!S_1, ..., C\!S_e$ such that \[\stwo Zero(P\!S)=\bigcup_{i=1}^e Zero(C\!S_i/J_i),\] where each $J_i$ is the product of initials of polynomials in $C\!S_i$. It is designed mainly to prepare a sequence of triangular forms for solving the corresponding system of polynomial equations. The function {\sf csolve} finds all solutions of a system of polynomial equations. It uses basically the function {\sf triser} to prepare a sequence of triangular forms and then solves each triangular form by successive substitution, where the Maple function {\sf solve} is used for the resolution of univariate polynomial equations. \medskip \noindent 2.4. {\sf qics}, {\sf ics} and {\sf eics} \medskip \noindent If all polynomials in the (weak) ascending sets of a characteristic series of $P\!S$ are irreducible, then the (weak) characteristic series is said to be {\em quasi-irreducible}. If all ascending sets of a characteristic series or extended characteristic series of $P\!S$ are irreducible, then the characteristic series or extended characteristic series is said to be {\em irreducible}. The functions {\sf qics}, {\sf ics} and {\sf eics} compute respectively the quasi-irreducible (weak) characteristic series, irreducible characteristic series, and extended irreducible characteristic series of a polynomial set $P\!S$ or $P\!S/G$. In {\sf qics} we have an option of 5 medial sets: {\sf basset}, {\sf wbasset}, {\sf charsetn}, {\sf qcharsetn} and {\sf trisetc} too. A quasi-irreducible weak characteristic series is returned if {\sf wbasset} or {\sf wcharsetn} is chosen, and a quasi-irreducible characteristic series is returned if one of the others is chosen. In {\sf ics} and {\sf eics}, an option of 3 medial sets {\sf basset}, {\sf charsetn} and {\sf trisetc} are allowed. In all three functions {\sf charsetn} is again the default. \medskip \noindent 2.5. {\sf ivd} \medskip \noindent If a polynomial set $P\!S$ and a sequence of polynomial sets $V\!S_1, ..., V\!S_t$ are such that \[\stwo Zero(P\!S)=\bigcup_{i=1}^t Zero(V\!S_i),\] and that the algebraic variety defined $V\!S_i$ is irreducible for all $i$, then the above zero decomposition is called an {\em irreducible decomposition} of the algebraic variety defined by $P\!S$, and $V\!S_1, ..., V\!S_t$ are called the defining sets of irreducible components of the decomposition. The function {\sf ivd} computes the sequence of irredundant defining sets of the irreducible decomposition of the algebraic variety defined by a polynomial set $P\!S$. For this function, we have again an option of 3 medial sets: {\sf basset}, {\sf charsetn} and {\sf trisetc} with {\sf charsetn} as default. \medskip \noindent 2.6. {\sf cfactor} \medskip \noindent Let $A\!S=\{A_1(u_1, ..., u_d, y_1), A_2(u_1, ..., u_d, y_1, y_2), ..., A_r(u_1, ..., u_d, y_1, ..., y_r)\}$ be an irreducible ascending set and $F=F(u_1, ..., u_d, y_1, ..., y_r, y)$ be any polynomial with rational coefficients, of degree in $y$ greater than 1 and with its leading coefficient in $y$ having non-zero remainder \wrt $A\!S$. The function {\sf cfactor} computes the irreducible factorization of $F$ over the algebraic number field ${\bf Q}(u_1, ..., u_d,y_1, ..., y_r)$, where ${\bf Q}$ denotes the rational filed, $u_1, ..., u_d$ are transcendental elements and $y_1, ..., y_r$ are algebraic elements with $y_i$ being an extended zero of $A_i(u_1, ..., u_d, y_1, ...,y_i)$ in ${\bf Q}(u_1, ..., u_d,y_1, ..., y_{i-1})$ for each $i$. \bigskip \noindent {\large \bf 3. Modifications and Strategies} \bigskip \noindent The theory of characteristic sets developed by Ritt and Wu provides a constructive method for dealing with systems of polynomials (as well as differential polynomials). However, form computational aspect many details have to be carefully taken into account for the sake of efficiency. These details were not cared by Ritt at all. It was Wu who recognized the power of Ritt's work and greatly improved this work both in theory and in practice by bringing many new and important ideas. Through the development of our package we have made several further modifications and improvements and adopted a number of implementation strategies. We are not able to list all of them but a few most important ones below of which some were given as remarks in [8]. \bigskip \noindent 3.1. Modification of Pseudo-Division \medskip \noindent The basic operation underlying all characteristic-ste-based algorithms is the pseudo-division of two polynomials $F$ and $G$ \wrt some variable $x$. While dividing $G$ by $F$, one gets a remainder formula of the form \[\stwo I^s\cdot G=Q\cdot F+R,\] where $I$ is the leading coefficient of $F$ in $x$. The integer $s$ is determined to be as smallest so that the formula holds true according to Wu. This is important to reduce the degree and number of terms of the remainder $R$. Now we replace $I^s$ in the above formula by $I_1^{s_1}\cdots I_e^{s_e}$, where $I_1, ..., I_e$ are all irreducible factors of $I$, and choose the smallest $s_1, ..., s_e$ so that the corresponding remainder formula holds still. For this modification the determination of $R$ requires the computation of GCD (greatest common divisor) and takes thus more time at an individual step. As the modification often removes some redundant factors, it can much benefit further computations, in particular, if the occurring polynomials become large. We have observed this fact on many large examples. So in our package this modified pseudo-division algorithm is used. \medskip \noindent 3.2. Generalization of Characteristic Sets Algorithm \medskip \noindent Concerning the characteristic sets algorithm, there are several variants. Our implementation of this algorithm is based on a generalization described in [7]. We introduced a notion called {\em medial set} of a polynomial set $P\!S$ which is a (weak, quasi-) ascending set with its rank not higher than that of the basic set of $P\!S$ and in which all polynomials are linear combinations of polynomials in $P\!S$ with polynomial coefficients. Then, the basic set of a polynomial set is special medial set. We proved that in Ritt's original algorithm the basic set can be replaced by any medial set. Besides the basic set itself we have used in our implementation other medial sets including those computed by the algorithms {\sf CharacteristicSetN}, {\sf TriangularSetC}, {\sf TriangularSet} described in [7, 8] and by an algorithms designed for computing the so-called {\em normal} characteristic sets which are necessary for our factorization method to be mentioned below. With the notion of medial set several variants of the characteristic sets computation can be given in an unform manner. \medskip \noindent 3.3. Removing Possible Factors of Intermediate Polynomials \medskip \noindent During the computation of characteristic sets, there will appear necessarily some factors of the initials. These factors should be removed in order to control the expansion of polynomials. While allowing to remove these factor, the computed ascending set by the characteristic sets algorithm is no longer the characteristic set in Ritt's sense but is what we called the modified characteristic set. Then, the polynomials in the modified characteristic set may not be elements in the ideal generated by polynomials in the original set. If we consider only zero structure of these polynomial sets such as the application to polynomial equations solving, the modified characteristic sets are already well suited. If we denote the removed factors by $F_1, ..., F_t$, then we have a zero relation of the form \[\stwo Zero(P\!S)=Zero(C\!S/J)\cup\bigcup_{i=1}^rZero(P\!S_i)\cup \bigcup_{j=1}^tZero(Q\!S_j),~~~~~~~~~~~\] where $J=I_1\cdot\cdot\cdot I_r\cdot F_1\cdots F_t$ and $P\!S_i=P\!S\cup\{I_i\}, Q\!S_j=P\!S\cup\{F_j\}$. In functions {\sf mcharset}, {\sf mcs}, {\sf mecs}, {\sf triser}, {\sf qics}, {\sf ics}, {\sf eics} and {\sf ivd}, we all allow to remove some possible factors. If the option of medial sets is {\sf triset} or {\sf trisetc}, we remove possible factors of the previous initials in the computation of remainder sequence from the newly produced polynomials. Otherwise, we collect all appeared initials during the computation and remove them from the further produced polynomials at certain stage if possible. In all cases, the variables themselves as polynomials are examined and removed if possible. This processing is generally time-consuming and seems non-recommendable for small problems. If the problems are large, then removing of possible factors become very crucial. We have observed that for many problems {\sf charset} yields no result after a long running as Problem 4 shown in Table 1, but {\sf mcharset} can get the results easily. Since we are unable to predicate the computational cost for a given problem, we arrange to remove factors in most of our functions. \medskip \noindent 3.4. Polynomial Factorization \medskip \noindent The polynomial factorization over both rational number field and its algebraic extension fileds is required in our implementation. For that over rational number field, we use the Maple built-in function {\sf factor}. The use of {\sf factor} is either as a strategy for reducing computing expenses, or for computing the quasi-irreducible characteristic series, or as a subfunction for factorizing polynomials over algebraic number fileds. To verify the reducibility of ascending stes, and if reducible, to decompose them (which is needed in the functions {\sf ics}, {\sf eics} and {\sf ivd}), we have to factorize polynomials over successive algebraic extension of rational field which is generally considered as a difficult problem. Except Chou's implementation [1] which can factorize polynomials of degree 2, all other implementations of characteristic sets method do not include this step. The general factorization algorithms are too complicated and not available in Maple. The author has implemented a factorization method presented in [2] which was considered to be suitable for our purpose. Experiments demonstrate that that method is efficient only for factorizing polynomials of degree 2 and 3 while degrees of the minimal polynomials are also not too high. It is still too slow for factorizing polynomials of higher degree. Recently, the author has found another method which can be used for factorizing polynomials of rather high degree and reduces dramatically the difficulty of our factorization problem. This method has been implemented in combine with our early method as the function {\sf cfactor} and used for the irreducible decomposition of ascending sets. A paper to describe the full details of our new method with further experimental results is under preparation [10]. While using polynomial factorization which is expensive in general, we have used some strategies and tried to do so at a proper stage. For example, to verify the reducibility of characteristic set we do the test soon after a medial set is computed in the option of {\sf charsetn} and {\sf trisetc}. Other strategies like factorizing initials and removed factors in some cases are also very helpful to speed up the computation. \medskip \noindent 3.5. Determining the Bases of Ideals from their Characteristic Sets \medskip \noindent In our implemented algorithm for decomposing algebraic varieties into irreducible components we first compute the irreducible characteristic series of the defining polynomial set and then determine the finite bases of ideals with ascending sets in the series as their characteristic sets. For the latter an algorithm based on the Gr\"obner primbasissatz and Gr\"obner bases as described in [9] is implemented, where the Maple function {\sf gbasis} in the {\sf grobner} package is used for the computation of Gr\"obner bases. \medskip \noindent 3.6. Removing Redundant Branches of Decomposition Tree \medskip \noindent As argued in [9], all decomposition algorithms can be viewed as computing a multi-branch decomposition tree. The number of branches of the tree can be hundred and thousand due to the recursive generation of initials and some of these branches are completely redundant. Some strategies must be used in order to avoid redundant computation and to speed up the decomposition. In our implementation we have adopted various strategies for getting an equivalent but simpler tree with an aim at reducing the computing time and space. As most branches of the tree are produced from the recursive generation of initials, we observed that it is often beneficial to decrease both the depth and width of the decomposition tree by adjoining not the initials and the removed factors but all distinct factors of them. Even though this requires extensive polynomial factorization, the computation is not very expensive since the initials and remove factors are usually relatively simple. We cut off some redundant branches during the computation of various characteristic series according to a fact as follows: Let $Q\!S$ and $Q\!S'$ be two polynomial sets associated with two nodes of the decomposition tree of $P\!S$ and $Q\!S\subset Q\!S'$. If the decomposition tree of $Q\!S$ is already computed, then the decomposition tree of $Q\!S'$ as the subtree of $P\!S$ can be cut away. After the characteristic series has been produced, we remove some redundant ascending sets by another fact: For two ascending sets $A\!S_1$ and $A\!S_2$ of which the former is irreducible, if \wrt $A\!S_1$ the remainder set of $A\!S_2$ is empty and the remainder of $J_2$ is non-zero, then $Zero(A\!S_1/J_1)\subset Zero(A\!S_2/J_2)$, where $J_i$ is the product of initials of polynomials in $A\!S_i$ for each $i$, and thus $A\!S_1$ can be removed. For the function {\sf ivd}, we also cut off some redundant branches by the affine dimension theorem in algebraic geometry: The dimension of an irredundant component of a variety should not be less than $n-s$, where $n$ is the number of variables and $s$ is the number of defining polynomials and finally all redundant components by a lemma of Wu [12]. \medskip \noindent 3.7. Optimization of Variable Ordering \medskip \noindent The time for computing characteristic sets and thus all relevant decompositions depends heavily upon the choice of variable ordering. For example, if we order the variables in Problem 2 as $r\prec z\prec y\prec x$, then the characteristic set can be computed within one second. Therefore, the optimization of variable ordering must be considered for some applications such as the decomposition of algebraic varieties. In our implementation, if the variables are given as set, a {\em heuristically} optimal variable ordering in the following sense is used. Let $X$ be a set of variables and $P\!S$ be a set of polynomials in $X$. For any variable $x\in X$ we define {\small \[\Omega(x, P\!S)=\max_{p\in P\!S} deg_x(p),~~ \omega(x, P\!S)=\max\{1, \min_{p\in P\!S} deg_x(p)\},\] \[\Lambda(x, P\!S)={\rm number~of~elements~in}~ \{p\in P\!S|~deg_x(p)=\Omega(x,P\!S)\},\] \[\lambda(x, P\!S)={\rm number~of~elements~in}~\{p\in P\!S|~deg_x(p)=\omega(x,P\!S)\},\] \[\Delta(x, P\!S)=\min_{p\in P\!S, deg_x(p)=\omega(x, P\!S)} Tdeg(lc(p,x)),\] \[\delta(x, P\!S)=\min_{p\in P\!S, deg_x(p)=\omega(x, P\!S)} Term(lc(p,x)),\]} \noindent where $lc(p,x)$ denotes the leading coefficients of $p$ \wrt $x$, $Tdeg(\cdot)$ and $Term(\cdot)$ stand respectively for the total degree and the number of terms. Then, a partial order of the variables \wrt $P\!S$ is introduced as follows: \begin{enumerate} \item If a variable $x\in X$ occurs in one and only one polynomial $p\in P\!S$, then $x$ has its order higher than all others. \item A variable $x$ has its order higher than the variable $y$ if one of the following holds \begin{enumerate} {\small \item $\Omega(x, P\!S)<\Omega(y, P\!S)$; \item $\Omega(x, P\!S)=\Omega(y, P\!S)$ but $\Lambda(x, P\!S)< \Lambda(y, P\!S)$; \item $\Omega(x, P\!S)=\Omega(y, P\!S), \Lambda(x, P\!S)=\Lambda(y, P\!S)$ but $\omega(x, P\!S)<\omega(y, P\!S)$; \item $\Omega(x, P\!S)=\Omega(y, P\!S), \Lambda(x, P\!S)=\Lambda(y, P\!S), \omega(x, P\!S)=\omega(y, P\!S)$ but $\lambda(x, P\!S)>\lambda(y, P\!S)$; \item $\Omega(x, P\!S)=\Omega(y, P\!S), \Lambda(x, P\!S)=\Lambda(y, P\!S), \omega(x, P\!S)=\omega(y, P\!S), \lambda(x, P\!S)=\lambda(y, P\!S)$ but $\Delta(x, P\!S)<\Delta(y,P\!S)$; \item $\Omega(x, P\!S)=\Omega(y, P\!S), \Lambda(x, P\!S)=\Lambda(y, P\!S), \omega(x, P\!S)=\omega(y, P\!S), \lambda(x, P\!S)=\lambda(y, P\!S), \Delta(x, P\!S)=\Delta(y,P\!S)$ but $\delta(x, P\!S)<\delta(y, P\!S)$. } \end{enumerate} \end{enumerate} By this order, the variables in Problem 2 can be optimally reordered as $z\prec x\prec y\prec r$. \bigskip \noindent {\large \bf 4. Test Results and Remarks} \bigskip \noindent Since the functions plus their options in our package constitute many variants, we are unable to give here a long list of test problems due to the page restriction. We shall present some test results by only taking 3 problems with given variable ordering for each function. These problems were chosen in a quite random way but so that they are representative and proper for testing most of our functions. For instance, the problems 1, 2 and 3 are all chosen so that the polynomial factorization over algebraic number fileds is involved. The experiments were made in Maple 4.3 running on an Apollo DN10000 under UNIX operating system. All timings are given in CPU seconds without excluding those for garbage collection. The timing statistics here aims at showing a rough magnitude about the computational cost of each function and does not necessarily reflect its whole behaviour. For the computation for very similar problems may yield much different computing time while 3 test problems cannot say too much at all. In view of this reason we add below some remarks on each function based on our extensive experiments with other problems. \bigskip \centerline{\small Table 1. Timings for {\sf charset} and {\sf mcharset}} \medskip \centerline{ \begin{tabular}{||l||r|r||r|r||r|r||} \hline \hline ~ & \multicolumn{2}{c||}{Problem 2} & \multicolumn{2}{c||}{Problem 3} & \multicolumn{2}{c||}{Problem 4} \\ \hline option & charset & mcharset & charset & mcharset & charset & mcharset \\ \hline basset & $>$1800 & 161.633 & 14.100 & 15.650 & $>$1800 & 540.400 \\ \hline charsetn & 27.116 & 22.733 & 5.067 & 6.067 & $>$1800 & 280.083 \\ \hline trisetc & 21.933 & 34.850 & 4.350 & 6.717 & $>$1800 & $>$1800 \\ \hline wbasset & 714.200 & 30.266 & 6.750 & 6.133 & $>$1800 & $>$1800 \\ \hline wcharsetn & 23.084 & 7.600 & 3.466 & 3.766 & $>$1800 & 1606.883 \\ \hline qbasset & 1.684 & 2.250 & 2.967 & 2.984 & $>$1800 & 105.600 \\ \hline qcharsetn & 1.600 & 2.100 & 1.967 & 2.100 & $>$1800 & 21.184 \\ \hline triset & 1.383 & 2.350 & 2.150 & 4.333 & $>$1800 & 29.817 \\ \hline \hline \end{tabular}} \bigskip \centerline{\small Table 2. Timings for {\sf charser} and {\sf mcs}} \medskip \centerline{ \begin{tabular}{||l||r|r||r|r||r|r||} \hline \hline ~ & \multicolumn{2}{c||}{Problem 1} & \multicolumn{2}{c||}{Problem 2} & \multicolumn{2}{c||}{Problem 3} \\ \hline option & charser & mcs & charser & mcs & charser & mcs \\ \hline basset & 1.383 & 1.550 & $>$1800 & 1751.050 & 48.516 & 64.588 \\ \hline charsetn & 1.017 & 1.283 & 59.616 & 70.966 & 18.850 & 35.734 \\ \hline trisetc & 0.917 & 1.467 & 49.983 & 77.316 & 24.450 & 97.050 \\ \hline wbasset & 3.067 & 1.617 & 1277.667 & 415.517 & 18.050 & 25.950 \\ \hline wcharsetn & 3.766 & 1.467 & 46.967 & 45.250 & 33.133 & 21.517 \\ \hline \hline \end{tabular}} \bigskip \centerline{\small Table 3. Timings for {\sf ecs} and {\sf mecs}} \medskip \centerline{ \begin{tabular}{||l||r|r||r|r||r|r||} \hline \hline ~ & \multicolumn{2}{c||}{Problem 1} & \multicolumn{2}{c||}{Problem 2} & \multicolumn{2}{c||}{Problem 3} \\ \hline option & ecs & mecs & ecs & mecs & ecs & mecs \\ \hline basset & 1.716 & 1.883 & $>$1800 & 816.567 & 48.900 & 53.750 \\ \hline charsetn & 1.367 & 1.500 & 60.750 & 59.784 & 20.217 & 21.133 \\ \hline trisetc & 0.900 & 1.067 & 48.283 & 65.484 & 27.217 & 26.800 \\ \hline wbasset & 3.350 & 4.083 & 821.250 & 230.400 & 17.616 & 18.616 \\ \hline wcharsetn & 3.834 & 3.416 & 44.500 & 33.317 & 32.017 & 14.067 \\ \hline \hline \end{tabular}} \bigskip \centerline{\small Table 4. Timings for {\sf qics} and {\sf eics}} \medskip \centerline{ \begin{tabular}{||l||r|r||r|r||r|r||} \hline \hline ~ & \multicolumn{2}{c||}{Problem 1} & \multicolumn{2}{c||}{Problem 2} & \multicolumn{2}{c||}{Problem 3} \\ \hline option & qics & eics & qics & eics & qics & eics \\ \hline basset & 3.583 & 11.367 & 359.867 & 384.783 & 188.233 & 239.150 \\ \hline charsetn & 2.950 & 10.100 & 65.417 & 80.666 & 109.733 & 107.284 \\ \hline trisetc & 4.417 & 12.717 & 61.850 & 99.583 & 173.800 & 158.000 \\ \hline wbasset & 3.616 & & 111.100 & & 79.916 & \\ \hline wcharsetn & 3.300 & & 36.500 & & 84.250 & \\ \hline \hline \end{tabular}} \bigskip \centerline{\small Table 5. Timings for {\sf ics} and {\sf ivd}} \medskip \centerline{ \begin{tabular}{||l||r|r||r|r||r|r||} \hline \hline ~ & \multicolumn{2}{c||}{Problem 1} & \multicolumn{2}{c||}{Problem 2} & \multicolumn{2}{c||}{Problem 3} \\ \hline option & ics & ivd & ics & ivd & ics & ivd \\ \hline basset & 10.533 & 12.616 & 369.100 & 381.683 & 279.733 & 352.000 \\ \hline charsetn & 12.084 & 12.833 & 92.150 & 95.384 & 162.716 & 228.433 \\ \hline trisetc & 12.950 & 14.983 & 61.334 & 75.650 & 274.150 & 398.583 \\ \hline \hline \end{tabular}} \bigskip \centerline{\small Table 6. Timings for {\sf triser}, {\sf csolve} and {\sf cfactor}} \medskip \centerline{ \begin{tabular}{||l|r|r||} \hline \hline ~ & triser & csolve \\ \hline Problem 1 & 1.667 & 3.434 \\ \hline Problem 2 & 54.117 & $>$1800 \\ \hline Problem 3 & 23.700 & 28.567 \\ \hline \hline \end{tabular}~~~~~~~~~~ \begin{tabular}{||l||r||} \hline \hline ~ & cfactor \\ \hline Problem 5 & 8.150 \\ \hline Problem 6 & 18.750 \\ \hline Problem 7 & 97.300 \\ \hline \hline \end{tabular}} \bigskip \noindent {\bf Remark 1.} For (modified) characteristic sets, the computation in quasi-sense is generally faster than that in other senses, whereas the computation in weak sense is only sometimes faster than that in normal sense. However, the quasi-sense is theoretically weak. For example, in this sense we are unable to compute the characteristic series since the decomposition algorithm can no longer be guaranteed to terminate. Also, the irreducibility of a quasi-ascending set cannot be well defined. In the same sense, the computation is generally fast if the medial set {\sf qcharsetn}, {\sf wcharsetn}, {\sf charsetn}, {\sf triset} or {\sf trisetc} is chosen. It is rather slow while using the medial set {\sf qbasset}, {\sf wbasset} or {\sf basset}. Here, the choice of {\sf basset} is Ritt's original version of the algorithm, that of ({\sf w-, q-}) {\sf charsetn} is the version of Wu, and that of {\sf triset} and {\sf trisetc} is a version proposed by us. \medskip \noindent {\bf Remark 2.} For small problems {\sf charset} is sometimes faster than {\sf mcharset}, but for large ones it is absolutely slow and even yields no result within a reasonable time limit as we mentioned before. Consequently, {\sf mcs} and {\sf mecs} are faster than {\sf charser} and {\sf ecs} for large problems. In general, the output of {\sf mcs} and {\sf mecs} is also more succinct than that of {\sf charser} and {\sf ecs}. The computing time between {\sf charser} and {\sf ecs}, {\sf mcs} and {\sf mecs}, {\sf ics} and {\sf eics} may be different from each other as we used different strategies, but none seems faster than the other. In {\sf eics} we implemented an extended zero decomposition by Wu [13]. It speeds up the computation in most cases but produces some additional conditions which cost time at other stage. Note that the functions {\sf mcs}, {\sf qics} and {\sf icc} implement a similar algorithmic structure, where all three examine and remove some possible factors, and of which {\sf qics} factorizes every polynomial in all ascending sets and {\sf ics} decomposes all ascending sets into irreducible ones. The function {\sf ics} is also used as the main subfunction of {\sf ivd} and partially as a subfunction of {\sf cfactor}. \medskip \noindent {\bf Remark 3.} The function {\sf triser} is designed for getting a sequence of ascending, weak or quasi-ascending sets as soon as possible. It computes the characteristic sets at the beginning in quasi-sense and later in other senses in order to ensure the termination of execution. This function may be faster than others for computing characteristic series and its use can be recommended to prepare a sequence of triangular forms for polynomial equations solving. Actually, the function {\sf csolve} is mainly based on this one. \medskip \noindent {\bf Remark 4.} During the implementation of our package we always keep in mind to attack large problems, where the word {\em large} is said \wrt the computing cost. Several strategies were used for this purpose and are able to reduce both the computing space and time for a number of large problems, but they may in turn increase the cost for small ones. Concerning the adoption of these strategies, we have difficulties to judge before the computation which kind of problems are large. For this issue the author guesses that a careful practical complexity analysis of used algorithms must be first considered. Also, one variant of an algorithm may be faster for some problems but totally slow for others. We have tried to use different algorithms and different variants of one algorithm by examining the sort of inputs according to our own experience. However, this works well only in some cases. The characteristic sets and thus various related zero decompositions are generally not unique. To avoid some redundant or even unpleasant output, we have also arranged to tidy the output in the case the processing is not expensive. \medskip \bigskip \noindent {\large \bf References} {\small \begin{enumerate} \item Chou, S. C., {\em Mechanical Geometry Theorem Proving}, D.\ Reidel Publ.\ Comp., Dordrecht-Boston-Lancaster-Tokyo (1988). \item Hu, S. and Wang, D. M., `Fast Factorization of Polynomials over Rational Number Field or its Extension Fields', {\em Kexue Tongbao} {\bf 31}, 150-156 (1986). \item Ko, H. P., `ALGE-Prover II --- A New Edition of ALGE-Prover', Corp.\ Research and Development Technical Information Series, General Electric, Schenectady, USA (1986). \item Kusche, K., Kutzler, B., Mayr, H., `Implementation of a geometry theorem proving package in Scratchpad II', Proc. EUROCAL'87 (J. Davenport, ed.), 246-257, Springer-Verlag, Heidelberg (1989). \item Ritt, J. F., {\em Differential Equations from the Algebraic Standpoint}, Amer. Math. Soc., New York (1932). \item Ritt, J. F., {\em Differential Algebra}, Amer. Math. Soc., New York (1950). \item Wang, D. M., `A Generalization of Characteristic Sets Algorithm', RISC-Linz Series no. 89-51.0, Johannes Kepler University, Austria (1989). \item Wang, D. M., `Characteristic Sets and Zero Structure of Polynomial Sets', Preprint, RISC-LINZ, Johannes Kepler University, Austria (1989). \item Wang, D. M., `Irreducible Decomposition of Algebraic Varieties via Characteristic Sets and Gr\"obner Bases', Preprint, RISC-LINZ, Johannes Kepler University; Submitted to {\em Computer Aided Geometric Design}, November 1990. \item Wang, D. M., `A Method for Factorizing Polynomials over Algebraic Number Fields', In preparation. \item Wu, W. T., `Basic Principles of Mechanical Theorem Proving in Elementary Geometries', {\em J. Sys. Sci. \& Math. Scis.} {\bf 4}, 207-235 (1984); {\em J. Automated Reasoning} {\bf 2}, 221-252 (1986). \item Wu, W. T., {\em Basic Principles of Mechanical Theorem Proving in Geometries (Part on elementary geometries, in Chinese)}, Science Press, Beijing (1984). \item Wu, W. T., `On Zeros of Algebraic Equations --- An application of Ritt principle', {\em Kexue Tongbao} {\bf 31}, 1-5 (1986). \item {\em Mathematics-Mechanization Research Preprints}, No.~1-5, MM Research Center Academia Sinica, (1987-1990). \end{enumerate} } {\small \bigskip \noindent {\normalsize \bf Appendix. Test Problems} \bigskip \noindent The source of the following test problems: Problems 1-5 are taken respectively from the papers of Wang, Butcher, Wu, Bronstein and Wang. The polynomial in Problem 6 is one needed to be factorized in the irreducible decompositions of Problem 2. Problem 7 is a test example used by the author. \baselineskip 16pt % Ex_1: from Wang (1989) \bigskip \noindent {\bf Problem 1.} $P\!S=\{x_4^2+x_1x_4^2-x_2x_4-x_1x_2x_4+x_1x_2+3x_2, x_1x_4+x_3-x_1x_2, x_3x_4-2x_2^2-x_1x_2-1\}$ with variable ordering $x_1\prec x_2\prec x_3\prec x_4$. \medskip \noindent {\bf Problem 2.} $P\!S=\{p_1, ..., p_8\}$ with variable ordering $b\prec c_2\prec c_3\prec a\prec b_3\prec b_2\prec a_{32}\prec b_1$, where \smallskip \noindent $p_1=b_1+b_2+b_3-a-b,$ \\ $p_2= 2b_2c_2+2b_3c_3-1-b-2b^2+2ab,$ \\ $p_3= 3b_2c_2^2+3b_3c_3^2-a-3ab^2+4b+3b^2+3b^3,$ \\ $p_4= 6b_3a_{32}c_2-a-3ab-6ab^2+4b+6b^2+6b^3,$ \\ $p_5= 4b_2c_2^3+4b_3c_3^3-1-b-10b^2-6b^3-4b^4+4ab+4ab^3,$ \\ $p_6= 8b_3c_3a_{32}c_2-1-3b-14b^2-12b^3-8b^4+4ab+4ab^2+8ab^3,$ \\ $p_7= 12b_3a_{32}c_2^2-1-b-14b^2-18b^3-12b^4+8ab+12ab^2+12ab^3,$ \\ $p_8= 1+7b+26b^2+36b^3+24b^4-8ab-24ab^2-24ab^3.$ \baselineskip 18pt \medskip \noindent {\bf Problem 3.} $\displaystyle{P\!S=\{y^2-p_1, \frac{\partial p_2}{\partial x_1}, \frac{\partial p_2}{\partial x_2},\frac{\partial p_2}{\partial x_3}, \frac{\partial p_2}{\partial x_4},\frac{\partial p_2}{\partial x_5}, \frac{\partial p_2}{\partial x_6},\frac{\partial p_2}{\partial \lambda_1}, \frac{\partial p_2}{\partial \lambda_2},\frac{\partial p_2}{\partial \lambda_3}\}}$ with variable ordering $x_1\prec x_2\prec x_3\prec x_4\prec x_5\prec x_6\prec \lambda_1\prec \lambda_2\prec \lambda_3\prec y$, where $p_1=(x_4+x_5)(x_5+x_6)(x_6+x_4)x_2^2x_1^2x_3^2$, $p_2=p_1+\lambda_1(x_2^2x_6-1)+\lambda_2(x_1^2x_4-1)+\lambda_3(x_3^2x_5-1).$ \baselineskip 16pt % Ex_4: from Bronstein (1986) \medskip \noindent {\bf Problem 4.} $P\!S=\{x^2+y^2+z^2-r^2, xy+z^2-1,xyz-x^2-y^2-z+1\}$ with variable ordering $r\prec x\prec y\prec z$. % Ex5 \medskip \noindent {\bf Problem 5.} $A\!S=\{a^4+a^3+a^2+a+1\}$ and $F=16x^4+8x^3+4x^2+2x+1$. % Ex6 \medskip \noindent {\bf Problem 6.} $A\!S=\{-1+b+6b^2+12b^3\}$ and $F= 745092b-252156+540900c+21032664c^2b^2+2010720b ^2+7117713c^2b-132367c^2+3076830c^3-7843500c^3b^2+2792322c^3 b-3779244bc-10724400b^2c+21225240bc^5+26306208b^2c^5+8257464 c^5-436536c^4+6094008b^2c^4+594432bc^4$. % Ex7 \bigskip \noindent {\bf Problem 7.} $A\!S=\{r^2-2+z^2, -rz+y+4y^2\}$ and $F=-370x^2y-10x^3+60x^2z+4xy-24zy+74rzy+2rzx+37rz-37y+12r^3-24r$ with variable ordering $z\prec y\prec x$. } \end{document}