Cyclic nroots
ì ï ï ï í ï ï ï î 
x_{1}+x_{2}+···+x_{n} = 0 
x_{1}x_{2}+ x_{2} x_{3} + ···+x_{n}x_{1} = 0 
· · · 
x_{1}··· x_{n1}+ x_{2}··· x_{n}+···+x_{n}x_{1}··· x_{n2} =
0 
x_{1}x_{2}··· x_{n} = 1 

A simplified formulation is obtained in terms of n1 equations
in n1 new variables by
dividing the kth polynomial by x_{n}^{k} for k=1,..., n.
The new variables are y_{i}=x_{i}/x_{n}, i=1, ..., n1, and
the system:

y_{1}+y_{2}+··· + y_{n1} + 1 
= 
0, 


y_{1} y_{2}+ y_{2} y_{3} + ···+ y_{1} 
= 
0, 


· · · 

y_{1}··· y_{n1}+ y_{2}··· y_{n1}+···+ y_{1}··· y_{n2} 
= 
0 


y_{1} y_{2}··· y_{n1} 
= 
x_{n}^{n}.


References for this problem can be found in [2].
Characteristics:
 Dimension 0 for n=1,2,3,5,6,7.
 Positivedimensional variety for n=4,8.
 Degree known for n£ 8.
n 
1 
2 
3 
4 
5 
6 
7 
8 
degree 
1 
2 
6 
16 
70 
156 
924 
1152 
Degree £ (
)
(see [5]).
Example 1:proc(n)
local i,j,k,kk,polys,factor;
polys := array(1..n);
for i from 1 to n1 do # poly
polys[i] := 0;
for j from 1 to n do # start var
factor := 1;
for k from j to j+i1 do
if k <= n then factor := factor * x[k];
else kk := kn; factor := factor * x[kk]; fi;
od;
polys[i] := polys[i] + factor;
od;
od;
polys[n] := 1;
for i from 1 to n do polys[n] := polys[n] * x[i]; od;
polys[n] := polys[n]  1;
convert(polys,list);
end:
Problem: Bound the number of roots.
· Solution by I.Z Emeris, INRIA, Projet SAGA,
2004 Route des Lucioles,BP 93, 06902 SophiaAntipolis (France),
emeris@sophia.inria.fr, (5 May 1995)
Mixed volumes bound the number of isolated roots.
The results concern the LiftPrune algorithm by
Emiris and Canny (1995) [4].
Its public implementation is accessible at
ftp://www.inria.fr/saga/emiris.

#isolated 
mixed 
LiftPrune 
n 
roots 
volume 
CPU time 
3 
6 
6 
0s 
4 
0 
16 
0s 
5 
70 
70 
0s 
6 
156 
156 
2s 
7 
924 
924 
27s 
8 
1152 
2560 
4m 19s = 259s 
9 
unknown 
11016 
40m 59s = 2459s 
10 
unknown 
35940 
4h 50m 14s = 17414s 
11 
unknown 
184756 
38h 26m 44s = 138404s 
Table 1: LiftPrune executed on a DEC Alpha 3300.
Problem: Compute a resultant matrix.
· Solution by I.Z Emeris, INRIA, Projet SAFIR, 2004 Route des Lucioles,BP
93, 06902 SophiaAntipolis (France),
emeris@sophia.inria.fr, 5 May 1995
Sparse resultants essentially produce multiplication tables and
reduce the solution of zerodimensional problems to an eigencomputation.
Some preliminaty results on a SUN Sparc 20 follow for the
simplified formulation.
deg R stands for the total degree of the sparse resultant
in the input coefficients, M is the resultant matrix computed
by the incremental algorithm [4], column ``greedy''
gives the dimension of the resultant matrix constructed by the greedy
algorithm [3].
n 
deg R 
dim M 
rank M 
greedy 
time 
4 
6 
6 
5 
7 
0s 
5 
20 
26 
26 
32 
0s 
6 
66 
102 
102 
176 
3s 
7 
270 
685 
627 
³ 1273 
1508s 
Table 2: The incremental and greedy algorithms.
References
 [1]

D. Bini and B. Mourrain.
Polynomial test suite.
1996.
 [2]

G. Björck and R. Fröberg.
A faster way to count the solutions of inhomogeneous systems of
algebraic equations, with applications to cyclic nroots.
J. Symbolic Computation, 12:329336, 1991.
 [3]

J. Canny and P. Pedersen.
An algorithm for the Newton resultant.
Technical Report 1394, Comp. Science Dept., Cornell University,
1993.
 [4]

I.Z. Emiris and J.F. Canny.
Efficient incremental algorithms for the sparse resultant and the
mixed volume.
J. Symbolic Computation, 20(2):117149, August 1995.
 [5]

L. Pottier.
Bounds for degree of the ncyclic system.
INRIA SophiaAntipolis, Manuscript, 1995.