File r38/doc/manual2/invbase.tex artifact 82731d72bc part of check-in 3af273af29


\chapter[INVBASE: Involutive Bases]%
        {INVBASE: A package for computing involutive bases}
\label{INVBASE}
\typeout{{INVBASE: A package for computing involutive bases}}

{\footnotesize
\begin{center}
A.Yu.Zharkov, Yu.A.Blinkov\\
Saratov University\\
Astrakhanskaya 83\\
410071 Saratov, Russia\\[0.05in]
e--mail: postmaster@scnit.saratov.su
\end{center}
}

\ttindex{INVBASE}

Involutive bases are a new tool for solving problems in connection
with multivariate polynomials, such as solving systems of polynomial
equations and analysing polynomial ideals.  An involutive basis of
polynomial ideal is 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 can be seen as an alternative to Buchberger's
algorithm.

\section{The Basic Operators}
\subsection{Term Ordering}
The term order modes available
are\ttindex{REVGRADLEX}\ttindex{GRADLEX}\ttindex{LEX}
{\tt REVGRADLEX}, {\tt GRADLEX} and {\tt 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 $\gg$ must be defined.
The term ordering mode as well as the order of variables
are set by the operator\ttindex{INVTORDER}
{\tt INVTORDER} {\it mode},$\{x_1,...,x_n\}$
where {\it 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\gg \ldots \gg x_n$.

\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
\ttindex{INVBASE}

\noindent{\tt INVBASE} $\{p_1,...,p_m\} $

where $p_i$ are polynomials in variables listed in the
{\tt INVTORDER} operator. If some kernels in $p_i$ were not listed
previously in the {\tt INVTORDER} operator they are considered as
parameters, {\em i.e.\ }they are considered part of the coefficients of
polynomials.  If {\tt 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
\begin{verbatim}
ON MODULAR; SETMOD p;
\end{verbatim}
where $p$ is a prime number.
The value of the \f{INVBASE} function is a list of integer polynomials
$\{g_1,...,g_n\}$ representing an involutive basis of a given ideal.

\begin{verbatim}
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};

             3          2      3        2
g := {8*x*y*z  - 2*x*y*z  + 4*y  - 4*y*z  + 16*x*y + 17*y*z - 4*y,

         4        2        2               2
      8*y  - 8*x*z  - 256*y  + 2*x*z + 64*z  - 96*x + 20*z - 9,

         3
      2*y *z + 4*x*y + y,

           3        2      2      2
      8*x*z  - 2*x*z  + 4*y  - 4*z  + 16*x + 17*z - 4,

              3      3                2
       - 4*y*z  - 8*y  + 6*x*y*z + y*z  - 36*x*y - 8*y,

           2       2      2
      4*x*y  + 32*y  - 8*z  + 12*x - 2*z + 1,

         2
      2*y *z + 4*x + 1,

            3      2            2
       - 4*z  - 8*y  + 6*x*z + z  - 36*x - 8,

         2       2      2
      8*x  - 16*y  + 4*z  - 6*x - z}
\end{verbatim}

To convert it into a lexicographical Gr\"obner basis one should type
\begin{verbatim}
h := INVLEX g;

                      6        5         4           3
h := {3976*x + 37104*z  - 600*z  + 2111*z  + 122062*z

                 2
       + 232833*z  - 680336*z + 288814,

            2          6         5         4           3
      1988*y  - 76752*z  + 1272*z  - 4197*z  - 251555*z

                 2
       - 481837*z  + 1407741*z - 595666,

          7      6    5       4       3        2
      16*z  - 8*z  + z  + 52*z  + 75*z  - 342*z  + 266*z

       - 60}
\end{verbatim}



REDUCE Historical
REDUCE Sourceforge Project | Historical SVN Repository | GitHub Mirror | SourceHut Mirror | NotABug Mirror | Chisel Mirror | Chisel RSS ]