reduce-historical/r36/doc/INVBASE.TEX

\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\,<mode>,\{x_1,...,x_n\} $$
where $<mode>$ 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}