@@ -1,172 +1,172 @@ -\documentstyle[12pt]{article} -\textwidth 155mm -\textheight 225mm -\topmargin -10mm -\oddsidemargin 7mm -\evensidemargin 7mm -\pagestyle{empty} -\begin{document} -\def \bg #1 {\begin{tabular}{{#1}}} -\def \nd {\end{tabular}} -\begin{center} -{\large \bf INVBASE: A Package for Computing Involutive Bases} -\vskip 0.7cm -\noindent -A.Yu.Zharkov, Yu.A.Blinkov\\ -Saratov University\\ -Astrakhanskaya 83\\ -410071 Saratov\\ -Russia\\ -Email: postmaster@scnit.saratov.su\\ -\end{center} -\vspace{0.3cm} -\vskip 0.5cm -\section{Introduction} -Involutive bases are a new tool for solving problems in connection with -multivariate polynomials, such as solving systems of polynomial equations -and analyzing polynomial ideals, see \cite{Lille}. An involutive basis of -polynomial ideal is nothing but a special form of a redundant Gr\"obner -basis. The construction of involutive bases reduces the problem of solving -polynomial systems to simple linear algebra.\\ -The INVBASE package -\footnote{The REDUCE implementation has been supported by -the Konrad-Zuse-Zentrum Berlin} -calculates involutive bases of polynomial ideals -using an algorithm described in \cite{Lille} -which may be considered as an alternative to -the well-known Buchberger algorithm \cite{Buch}. -The package can be used over -a variety of different coefficient domains, and for different variable -and term orderings.\\ -The algorithm implemented in the INVBASE package is proved -to be valid for any zero-dimensional ideal (finite number of solutions) -as well as for positive-dimensional ideals in generic form. However, -the algorithm does not terminate for ``sparse'' positive-dimensional systems. -In order to stop the process we use the maximum degree -bound for the Gr\"obner bases of generic ideals in the total-degree -term ordering established in \cite{Laz}. -In this case, it is reasonable -to call the GROEBNER package with the answer of INVBASE as input -information in order to compute the reduced Gr\"obner basis under the -same variable and term ordering.\\ -Though the INVBASE package supports computing involutive bases in any -admissible term ordering, -it is reasonable to compute them only for the total-degree term -orderings. The package includes a special algorithm for conversion -of total-degree involutive bases into the triangular bases -in the lexicographical term ordering that is desirable for -finding solutions. Normally the sum of timings for these two -computations is much less than the timing for direct computation -of the lexicographical involutive bases. As a rule, the result -of the conversion algorithm is a reduced Gr\"obner basis in the -lexicographical term ordering. However, because of some gaps in -the current version of the algorithm, -there may be rare situations when the resulting triangular set -does not possess the formal property of Gr\"obner bases. -Anyway, we recommend using the GROEBNER package with the result -of the conversion algorithm as input in order either to check -the Gr\"obner bases property or to transform the result into a -lexicographical Gr\"obner basis. -\section{The Basic Operators} -\subsection{Term Ordering} -The following term order modes are available: -$$ REVGRADLEX,\; GRADLEX,\; LEX $$ -These modes have the same meaning as for the GROEBNER package.\\ -All orderings are based on an ordering among the variables. -For each pair of variables an order relation $>$ must be defined, -e.g. $x>y$. The term ordering mode as well as the order of variables -are set by the operator -$$ INVTORDER\,,\{x_1,...,x_n\} $$ -where $$ is one of the term order modes listed above. -The notion of $\{x_1,...,x_n\}$ as a list of variables -at the same time means $x_1>...>x_n$. -\vskip 0.1cm -\noindent -{\bf Example 1.} -$$ INVTORDER\>\,REVGRADLEX,\{x,y,z\} $$ -sets the reverse graduated term ordering based on the variable -order $x>y>z$.\\ -The operator $INVTORDER$ may be omitted. The default term order mode -is $REV\-GRADLEX$ and the default decreasing variable order is -alphabetical (or, more generally, the default REDUCE kernel order). -Furthermore, the list of variables in the $INVTORDER$ may be omitted. -In this case the default variable order is used. -\subsection{Computing Involutive Bases} -To compute the involutive basis of ideal generated by the set of -polynomials $\{p_1,...,p_m\}$ one should type the command -$$ INVBASE \> \{p_1,...,p_m\} $$ -where $p_i$ are polynomials in variables listed in the -$INVTORDER$ operator. If some kernels in $p_i$ were not listed -previously in the $INVTORDER$ operator they are considered as -parameters, i.e. they are considered part of the coefficients of -polynomials. If $INVTORDER$ was omitted, all the kernels -in $p_i$ are considered as variables with the default REDUCE -kernel order.\\ -The coefficients of polynomials $p_i$ may be integers as well as -rational numbers (or, accordingly, polynomials and rational functions -in the parametric case). The computations modulo prime numbers are -also available. For this purpose one should type the REDUCE commands -$$ ON \> MODULAR;\> SETMOD \> p; $$ -where $p$ is a prime number.\\ -The value of the $INVBASE$ function is a list of integer polynomials -$\{g_1,...,g_n\}$ representing an involutive basis of a given ideal.\\ -\newpage -\noindent -{\bf Example 2.} -\begin{eqnarray*} -& & INVTORDER \> REVGRADLEX,\{x,y,z\}; \\ -& & g:= INVBASE \> \{4*x**2 + x*y**2 - z + 1/4,\> - 2*x + y**2*z + 1/2,\> \\ -& & x**2*z - 1/2*x - y**2 \}; -\end{eqnarray*} -The resulting involutive basis in the reverse graduate ordering is -\begin{eqnarray*} -g := \{& & 8*x*y*z^3 - 2*x*y*z^2 + 4*y^3 - \\ -& & 4*y*z^2 + 16*x*y + 17*y*z - 4*y,\\ -& & 8*y^4 - 8*x*z^2 - 256*y^2 + 2*x*z + 64*z^2 - 96*x + 20*z - 9,\\ -& & 2*y^3*z + 4*x*y + y,\\ -& & 8*x*z^3 - 2*x*z^2 + 4*y^2 - 4*z^2 + 16*x + 17*z - 4,\\ -& & - 4*y*z^3 - 8*y^3 + 6*x*y*z + y*z^2 - 36*x*y - 8*y,\\ -& & 4*x*y^2 + 32*y^2 - 8*z^2 + 12*x - 2*z + 1,\\ -& & 2*y^2*z + 4*x + 1,\\ -& & - 4*z^3 - 8*y^2 + 6*x*z + z^2 - 36*x - 8,\\ -& & 8*x^2 - 16*y^2 + 4*z^2 - 6*x - z \quad \} -\end{eqnarray*} -To convert it into a lexicographical Gr\"obner basis one should type -$$ h:=INVLEX\>g; $$ -The result is -\begin{eqnarray*} -h :=\{& &3976*x + 37104*z^6 - 600*z^5 + 2111*z^4 + \\ -& & 122062*z^3 + 232833*z^2 - 680336*z + 288814,\\ -& & 1988*y^2 - 76752*z^6 + 1272*z^5 - 4197*z^4 - \\ -& & 251555*z^3 - 481837*z^2 + 1407741*z - 595666,\\ -& & 16*z^7 - 8*z^6 + z^5 + 52*z^4 + - 75*z^3 - 342*z^2 + 266*z - 60 \quad \} -\end{eqnarray*} -In the case of ``sparse'' positive-dimensioned system -when the involutive basis in the sense of \cite{Lille} does not exist, -you get the error message $$ *****\> MAXIMUM \> DEGREE \> BOUND \> -EXCEEDED $$ The resulting list of polynomials which is not an involutive -basis is stored in the share variable INVTEMPBASIS. In this case -it is reasonable to call the GROEBNER package with the value of -INVTEMPBASIS as input under the same variable and term ordering. - -\begin{thebibliography}{99} - -\bibitem{Lille} -Zharkov A.Yu., Blinkov Yu.A. Involution Approach to Solving Systems -of Algebraic Equations. Proceedings of the IMACS '93, 1993, 11-16. - -\bibitem{Buch} -Buchberger B. Gr\"obner bases: an Algorithmic Method in Polynomial -Ideal Theory. In: (Bose N.K., ed.) Recent Trends in Multidimensional -System Theory, Reidel, 1985. - -\bibitem{Laz} -Lazard D. Gr\"obner Bases, Gaussian Elimination and Resolution of -Systems of Algebraic Equations. Proceedings of EUROCAL '83. -Lecture Notes in Computer Science 162, Springer 1983, 146-157. - -\end{thebibliography} - -\end{document} +\documentstyle[12pt]{article} +\textwidth 155mm +\textheight 225mm +\topmargin -10mm +\oddsidemargin 7mm +\evensidemargin 7mm +\pagestyle{empty} +\begin{document} +\def \bg #1 {\begin{tabular}{{#1}}} +\def \nd {\end{tabular}} +\begin{center} +{\large \bf INVBASE: A Package for Computing Involutive Bases} +\vskip 0.7cm +\noindent +A.Yu.Zharkov, Yu.A.Blinkov\\ +Saratov University\\ +Astrakhanskaya 83\\ +410071 Saratov\\ +Russia\\ +Email: postmaster@scnit.saratov.su\\ +\end{center} +\vspace{0.3cm} +\vskip 0.5cm +\section{Introduction} +Involutive bases are a new tool for solving problems in connection with +multivariate polynomials, such as solving systems of polynomial equations +and analyzing polynomial ideals, see \cite{Lille}. An involutive basis of +polynomial ideal is nothing but a special form of a redundant Gr\"obner +basis. The construction of involutive bases reduces the problem of solving +polynomial systems to simple linear algebra.\\ +The INVBASE package +\footnote{The REDUCE implementation has been supported by +the Konrad-Zuse-Zentrum Berlin} +calculates involutive bases of polynomial ideals +using an algorithm described in \cite{Lille} +which may be considered as an alternative to +the well-known Buchberger algorithm \cite{Buch}. +The package can be used over +a variety of different coefficient domains, and for different variable +and term orderings.\\ +The algorithm implemented in the INVBASE package is proved +to be valid for any zero-dimensional ideal (finite number of solutions) +as well as for positive-dimensional ideals in generic form. However, +the algorithm does not terminate for ``sparse'' positive-dimensional systems. +In order to stop the process we use the maximum degree +bound for the Gr\"obner bases of generic ideals in the total-degree +term ordering established in \cite{Laz}. +In this case, it is reasonable +to call the GROEBNER package with the answer of INVBASE as input +information in order to compute the reduced Gr\"obner basis under the +same variable and term ordering.\\ +Though the INVBASE package supports computing involutive bases in any +admissible term ordering, +it is reasonable to compute them only for the total-degree term +orderings. The package includes a special algorithm for conversion +of total-degree involutive bases into the triangular bases +in the lexicographical term ordering that is desirable for +finding solutions. Normally the sum of timings for these two +computations is much less than the timing for direct computation +of the lexicographical involutive bases. As a rule, the result +of the conversion algorithm is a reduced Gr\"obner basis in the +lexicographical term ordering. However, because of some gaps in +the current version of the algorithm, +there may be rare situations when the resulting triangular set +does not possess the formal property of Gr\"obner bases. +Anyway, we recommend using the GROEBNER package with the result +of the conversion algorithm as input in order either to check +the Gr\"obner bases property or to transform the result into a +lexicographical Gr\"obner basis. +\section{The Basic Operators} +\subsection{Term Ordering} +The following term order modes are available: +$$ REVGRADLEX,\; GRADLEX,\; LEX $$ +These modes have the same meaning as for the GROEBNER package.\\ +All orderings are based on an ordering among the variables. +For each pair of variables an order relation $>$ must be defined, +e.g. $x>y$. The term ordering mode as well as the order of variables +are set by the operator +$$ INVTORDER\,,\{x_1,...,x_n\} $$ +where $$ is one of the term order modes listed above. +The notion of $\{x_1,...,x_n\}$ as a list of variables +at the same time means $x_1>...>x_n$. +\vskip 0.1cm +\noindent +{\bf Example 1.} +$$ INVTORDER\>\,REVGRADLEX,\{x,y,z\} $$ +sets the reverse graduated term ordering based on the variable +order $x>y>z$.\\ +The operator $INVTORDER$ may be omitted. The default term order mode +is $REV\-GRADLEX$ and the default decreasing variable order is +alphabetical (or, more generally, the default REDUCE kernel order). +Furthermore, the list of variables in the $INVTORDER$ may be omitted. +In this case the default variable order is used. +\subsection{Computing Involutive Bases} +To compute the involutive basis of ideal generated by the set of +polynomials $\{p_1,...,p_m\}$ one should type the command +$$ INVBASE \> \{p_1,...,p_m\} $$ +where $p_i$ are polynomials in variables listed in the +$INVTORDER$ operator. If some kernels in $p_i$ were not listed +previously in the $INVTORDER$ operator they are considered as +parameters, i.e. they are considered part of the coefficients of +polynomials. If $INVTORDER$ was omitted, all the kernels +in $p_i$ are considered as variables with the default REDUCE +kernel order.\\ +The coefficients of polynomials $p_i$ may be integers as well as +rational numbers (or, accordingly, polynomials and rational functions +in the parametric case). The computations modulo prime numbers are +also available. For this purpose one should type the REDUCE commands +$$ ON \> MODULAR;\> SETMOD \> p; $$ +where $p$ is a prime number.\\ +The value of the $INVBASE$ function is a list of integer polynomials +$\{g_1,...,g_n\}$ representing an involutive basis of a given ideal.\\ +\newpage +\noindent +{\bf Example 2.} +\begin{eqnarray*} +& & INVTORDER \> REVGRADLEX,\{x,y,z\}; \\ +& & g:= INVBASE \> \{4*x**2 + x*y**2 - z + 1/4,\> + 2*x + y**2*z + 1/2,\> \\ +& & x**2*z - 1/2*x - y**2 \}; +\end{eqnarray*} +The resulting involutive basis in the reverse graduate ordering is +\begin{eqnarray*} +g := \{& & 8*x*y*z^3 - 2*x*y*z^2 + 4*y^3 - \\ +& & 4*y*z^2 + 16*x*y + 17*y*z - 4*y,\\ +& & 8*y^4 - 8*x*z^2 - 256*y^2 + 2*x*z + 64*z^2 - 96*x + 20*z - 9,\\ +& & 2*y^3*z + 4*x*y + y,\\ +& & 8*x*z^3 - 2*x*z^2 + 4*y^2 - 4*z^2 + 16*x + 17*z - 4,\\ +& & - 4*y*z^3 - 8*y^3 + 6*x*y*z + y*z^2 - 36*x*y - 8*y,\\ +& & 4*x*y^2 + 32*y^2 - 8*z^2 + 12*x - 2*z + 1,\\ +& & 2*y^2*z + 4*x + 1,\\ +& & - 4*z^3 - 8*y^2 + 6*x*z + z^2 - 36*x - 8,\\ +& & 8*x^2 - 16*y^2 + 4*z^2 - 6*x - z \quad \} +\end{eqnarray*} +To convert it into a lexicographical Gr\"obner basis one should type +$$ h:=INVLEX\>g; $$ +The result is +\begin{eqnarray*} +h :=\{& &3976*x + 37104*z^6 - 600*z^5 + 2111*z^4 + \\ +& & 122062*z^3 + 232833*z^2 - 680336*z + 288814,\\ +& & 1988*y^2 - 76752*z^6 + 1272*z^5 - 4197*z^4 - \\ +& & 251555*z^3 - 481837*z^2 + 1407741*z - 595666,\\ +& & 16*z^7 - 8*z^6 + z^5 + 52*z^4 + + 75*z^3 - 342*z^2 + 266*z - 60 \quad \} +\end{eqnarray*} +In the case of ``sparse'' positive-dimensioned system +when the involutive basis in the sense of \cite{Lille} does not exist, +you get the error message $$ *****\> MAXIMUM \> DEGREE \> BOUND \> +EXCEEDED $$ The resulting list of polynomials which is not an involutive +basis is stored in the share variable INVTEMPBASIS. In this case +it is reasonable to call the GROEBNER package with the value of +INVTEMPBASIS as input under the same variable and term ordering. + +\begin{thebibliography}{99} + +\bibitem{Lille} +Zharkov A.Yu., Blinkov Yu.A. Involution Approach to Solving Systems +of Algebraic Equations. Proceedings of the IMACS '93, 1993, 11-16. + +\bibitem{Buch} +Buchberger B. Gr\"obner bases: an Algorithmic Method in Polynomial +Ideal Theory. In: (Bose N.K., ed.) Recent Trends in Multidimensional +System Theory, Reidel, 1985. + +\bibitem{Laz} +Lazard D. Gr\"obner Bases, Gaussian Elimination and Resolution of +Systems of Algebraic Equations. Proceedings of EUROCAL '83. +Lecture Notes in Computer Science 162, Springer 1983, 146-157. + +\end{thebibliography} + +\end{document}