Getting Started with Kronecker 0.166-9

Grégoire Lecerf
Laboratoire de mathématiques, LAMA - UMR 8100
Université de Versailles St-Quentin-en-Yvelines
45, avenue des Etats-Unis
78035 Versailles, France

Kronecker is a package for MAGMA to solve polynomial systems of equations. It is the result of a long term research by many people organised around the TERA project.

The present package has been designed by M. Giusti, G. Lecerf and B. Salvy. It is written in Magma by G. Lecerf and also contains contributions of E. Schost and L. Lehmann.

In order to use Kronecker you need a version of Magma at least 2.9-2.

What is "spec"?

In this document "spec" denotes the spec file for loading the Kronecker package. You need to know the full path directory where it is located. For instance if you are at MEDICIS this is "/usr/local/kronecker/spec". Note that this installation must be architecture dependent.

1 How to Solve your System?

Assume you have a system of s polynomial equations and s' inequations in n variables over a field K either of characteristic 0 or big enough:

f₁(x₁,...,x_n) = 0,..., f_s(x₁,...,x_n) = 0,

h₁(x₁,...,x_n) <> 0,..., h_s'(x₁,...,x_n) <> 0,

The resolution is achieved by issuing the following commands:

AttachSpec("spec");
R<x1,...,xn>:=
  BlackboxPolynomialAlgebra(k,n);

x1:=Var(x1);
  ...
xn:=Var(xn);

f1:=...;
  ...
fs:=...;

h1:=...;
  ...
hs':=...;

lf:=GeometricSolve(
  [f1,...,fs],
  [h1,...,hs']
);

Example: Solving the system called cyclic 3:

f₁=f₂=0, x<> 0, y<> 0, z<> 0.

AttachSpec("spec");

R<y,z>:=
  BlackboxPolynomialAlgebra(Rationals(),2);
y:=Var(y);
z:=Var(z);

x:=-y-z;
f1:=y*(x+z)+z*x;
f2:=y*(z*x)-1;

lf:=GeometricSolve([f1,f2],[x,y,z]);

Verbose Levels: the following instruction will make Kronecker verbose:

KroneckerSetVerbose();

The verbosity level can be specified through an integer between 0 and 5.

Now the variable lf contains the solution of the system: it is a sequence of sequences of Lifting Fibers. Each fiber corresponds to an equidimensional component of the variety solution of the system.

The command PrintLF(lf) pretty prints the resolution, DegreeLF(lf) and DimensionLF(lf) return respectively the degree (the sum of the degrees of the irreducible components) and the dimension (the maximum of the dimension of the irreducible components) of the variety described by lf. The command VerifyLF(lf) returns a boolean telling whether lf is correct or not.

2 Optimization of the Input

In order to get good performances with Kronecker it it important to take care about some simple rules concerning the input system.

Write your system with as less arithmetic operations as possible. In particular if your polynomials are not expanded do not expand them. The complexity of the resolution process is linear in the size of your input system (in term of its evaluation complexity).
Avoid linear equations and eliminate all the linear variables.
Do not use Rabinovitch's trick to deal with inequations.
Give Kronecker all the inequations you know about your system.
Often it is better to give the polynomials in the increasing degree order.

GeometricSolve([(x₁+2x₂+3x₃)(5x₂-7x₃)]) is better than GeometricSolve([5x₁x₂-7x₁x₃+10x₂²+x₂x₃-21x₃²]).
GeometricSolve([x₁+x₂³,x₂²+x₁⁷+x₃⁵+1]) should be replaced by GeometricSolve([x₂²+(-x₂³)⁷+x₃⁵+1]).
GeometricSolve([(x₁-x₂)T-1,x₂²+x₁⁷+7]) must be rewritten GeometricSolve([x₂²+x₁⁷+7],[x₁-x₂]).

As an experimental tool, a fast way to solve your system with Kronecker is to use the python script kroptimize.

3 Dimension Zero

We now describe the meaning of a zero dimensional lifting fiber. Let lf be a fiber of a zero equidimensional variety. Basically it is a record containing the following fields:

PrimitiveElement, denoted by u, is a linear form in the input variables x_i;
MinimalPolynomial, denoted by Q, is a sequence of univariate polynomials over K;
Denominator, denoted by P, is a sequence of univariate polynomials over K;
Parametrization, denoted by W, is a sequence sequences of n univariate polynomials over K;

The set of points described by lf is composed of the points

(W[i]₁(u)/P[i](u),...,W[i]_n(u)/P[i](u)),

for all the possible values of i and all the roots u of Q[i](u)=0. Note that P[i] is prime with Q[i] so that the denominator does not vanish over the roots of Q[i].
Example (continued):

> [ DegreeLF(z) : z in lf];
[ 6, 0, 0 ]
> lf0:=lf[1][1];
> lf0`PrimitiveElement;
y + 2*z
> lf0`MinimalPolynomial;
[
   T^6 + 27
]
> lf0`Denominator;
[
   6*T^5
]
> lf0`Parametrization;
[
    [
        -18*T^3,
        9*T^3 - 81
    ]
]

The system has 6 isolated solutions.

4 Positive Dimension

Let lf be a lifting fiber of a positive dimensional component V of dimension r, some more fields are significative:

ChangeOfVariables`LinearPart, denoted by M, is a square n × n matrix over K;
ChangeOfVariables`AffinePart, denoted by b, is a vector of size n over K.
MagicPoint, denoted by p, is a sequence of r element in K;

Let y₁,...,y_n be new variables, defined by y=M^-1(x-b), and f_i^y be the expression of f_i with respect to the y_j, and let p be the projection map from V to the affine space spanned by y₁,...,y_r the following properties hold:

V is an isolated subvariety of the variety solution of the f_i.
No irreducible component of V is included in the hypersurface defined by the product of the h_i.
y₁,...,y_r are free with respect to the variety V, or equivalently p is surjective. The variables y_r+1,...,y_n are integral over y₁,...,y_r, or equivalently p is finite. The y_i are said to be a Noether position for V.
y₁=p₁,...,y_r=p_r defines a (geometrically) smooth fiber V_p=p^-1(p) of V.
The primitive element u separates the points of the fiber V_p and the product of the elements of Q is its minimal polynomial.
V_p is the union of the following parametrizations, for all the possible values of i:
Q[i](u)=0,

P[i](u)y_r+1=W[i]₁(u), ..., P[i](u)y_n=W[i]_n(u).

The resolution contains a few other fields, consult the reference manual of Kronecker to know more about it.

5 MathML Interface

> KroneckerSetMathMLVerbose();
> lf:=GeometricSolve(equations);
Serving Magma HTTP on port 8000 ...

Then you can use your favorite MathML browser with url: http://localhost:8000/index.html. Use the reload button in order to follow your computations. Once finished, do not forget to kill the web server using the shell command pkill mml4mgm for instance.

Go to the Kronecker home page

This document was translated from L^AT_EX by H^EV^EA and H^AC^HA.