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:
f1(x1,...,xn) = 0,..., fs(x1,...,xn) = 0,
h1(x1,...,xn) <> 0,..., hs'(x1,...,xn) <> 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:
f1=f2=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([(x1+2x2+3x3)(5x2-7x3)]) is better than
GeometricSolve([5x1x2-7x1x3+10x22+x2x3-21x32]).
GeometricSolve([x1+x23,x22+x17+x35+1]) should be
replaced by GeometricSolve([x22+(-x23)7+x35+1]).
GeometricSolve([(x1-x2)T-1,x22+x17+7]) must be rewritten
GeometricSolve([x22+x17+7],[x1-x2]).
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 xi;
- 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]1(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 y1,...,yn be new variables, defined by
y=M-1(x-b), and fiy be the expression of fi
with respect to the yj, and let p be the projection map from
V to the affine space spanned by y1,...,yr the following
properties hold:
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 LATEX by
HEVEA and HACHA.