Let f_{1},...,f_{n} and g be polynomials in Q[x_{1},...,x_{n}], such that the system f_{1}=...=f_{n}=0 and g ¹ 0 has only a finite number of solutions. Following a long series of theoretical papers, G. Lecerf, M. Giusti and B. Salvy propose a new algorithm to obtain a geometric resolution of the zeroset of the system. This algorithm is valid under the hypothesis that the system f_{1},...,f_{n} forms a reduced, regular sequence outside V(g). This talk presents the complexity of the algorithm, details some crucial steps and finally compares the implementation in Magma called Kronecker^{1} to other available softwares. It is based on [3].
n(nL+n 

) O 

(  (dd)^{2}  )  . 
(nL+n 

) O 

(D)O 

(h). 
q(x_{ni+1})=0, 

Q(x_{ni},x_{ni+1})=0, 





The first series of examples consists in n generic polynomials of degree 2, with coefficients of h decimal digits, for various n and h. The systems have then full degree D=2^{n}. This example aims at illustrating the good behaviour of Kronecker regarding the growth of the coefficients. The timings are given in Table 1. The computations were performed on a Compaq Alpha EV6, 500 MHz, 128 Mb.
n h Kronecker Gb Grevlex + Real Solving 4 4 6 s 0.5s +0.5s 4 8 8 s 1s + 1.3s 4 16 11s 2.5s + 3.7s 4 32 21s 7s + 9.3s 5 4 36s 5s + 18s 5 8 50s 17s + 57s 5 16 88s 65s + 180s 5 32 208s 244s + 592s 6 4 260s 209s + >317s 6 8 412s 773s + ¥ 6 16 875s 2999s + ¥ 6 32 2312s 5652s + ¥
Table 1:
Kronecker Magma Grevlex 5h 13.6h
Table 2:
This document was translated from L^{A}T_{E}X by H^{E}V^{E}A.