Up | Next | Prev | PrevTail | Tail |

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. An involutive basis of polynomial ideal is nothing but a special form of a redundant Gröbner basis. The construction of involutive bases reduces the problem of solving polynomial systems to simple linear algebra.

Authors: A.Yu. Zharkov and Yu.A. Blinkov.

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 [?]. An involutive basis of polynomial ideal is nothing but a special form of a
redundant Gröbner basis. The construction of involutive bases reduces the problem of
solving polynomial systems to simple linear algebra.

The INVBASE package ^{13}
calculates involutive bases of polynomial ideals using an algorithm described in [?]
which may be considered as an alternative to the well-known Buchberger algorithm [?].
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öbner bases of generic ideals in the total-degree term ordering
established in [?]. 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öbner 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öbner 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öbner bases. Anyway, we recommend using the GROEBNER package
with the result of the conversion algorithm as input in order either to check the
Gröbner bases property or to transform the result into a lexicographical Gröbner
basis.

The following term order modes are available:

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

Example 1.

The operator INV TORDER 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 INV TORDER may be omitted. In this case the default variable order is used.

To compute the involutive basis of ideal generated by the set of polynomials {p_{1},...,p_{m}}
one should type the command

The coefficients of polynomials p

The value of the INV BASE function is a list of integer polynomials {g

Example 2.

[1] Zharkov A.Yu., Blinkov Yu.A. Involution Approach to Solving Systems of Algebraic Equations. Proceedings of the IMACS ’93, 1993, 11-16.

[2] Buchberger B. Gröbner bases: an Algorithmic Method in Polynomial Ideal Theory. In: (Bose N.K., ed.) Recent Trends in Multidimensional System Theory, Reidel, 1985.

[3] Lazard D. Gröbner Bases, Gaussian Elimination and Resolution of Systems of Algebraic Equations. Proceedings of EUROCAL ’83. Lecture Notes in Computer Science 162, Springer 1983, 146-157.

Up | Next | Prev | PrevTail | Front |