| 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 [ZB96].
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 26
calculates involutive bases of polynomial ideals using an algorithm described in [ZB96] which
may be considered as an alternative to the well-known Buchberger algorithm [Buc85]. 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 [Laz83]. 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:
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
where \(\langle \)mode\(\rangle \) 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\).
Example 1.
invtorder revgradlex,{x,y,z}
sets the reverse graduated term ordering based on the variable order \(x>y>z\).
The operator invtordermay be omitted. The default term order mode is revgradlexand
the default decreasing variable order is alphabetical (or, more generally, the default REDUCE
kernel order). Furthermore, the list of variables in the invtordermay 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
where \(p_i\) are polynomials in variables listed in the invtorderoperator. If some kernels in \(p_i\) were
not listed previously in the invtorderoperator they are considered as parameters,
i.e. they are considered part of the coefficients of polynomials. If invtorderwas
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 invbasefunction is a list of integer polynomials \(\{g_1,...,g_n\}\) representing an involutive
basis of a given ideal.
Example 2.
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 };
The resulting involutive basis in the reverse graduate ordering is
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}
To convert it into a lexicographical Gröbner basis one should type
h:=invlex g;
The result is
6 5 4
h := {3976*x + 37104*z - 600*z + 2111*z
3 2
+ 122062*z + 232833*z - 680336*z + 288814
,
2 6 5 4
1988*y - 76752*z + 1272*z - 4197*z
3 2
- 251555*z - 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}
In the case of “sparse” positive-dimensioned system when the involutive basis in the sense of [ZB96] 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 invtempbasisas input under the same variable and term ordering.
| Up | Next | Prev | PrevTail | Front |
Hosted by