Cyclic n-roots

cyclic [1]

ì
ï
ï
ï
í
ï
ï
ï
î
x1+x2+···+xn = 0
x1x2+ x2 x3 + ···+xnx1 = 0
·
·
·
x1··· xn-1+ x2··· xn+···+xnx1··· xn-2 = 0
x1x2··· xn = 1

A simplified formulation is obtained in terms of n-1 equations in n-1 new variables by dividing the k-th polynomial by xnk for k=1,..., n. The new variables are yi=xi/xn, i=1, ..., n-1, and the system:

y1+y2+··· + yn-1 + 1 = 0,
y1 y2+ y2 y3 + ···+ y1 = 0,
·
·
·
y1··· yn-1+ y2··· yn-1+···+ y1··· yn-2 = 0
y1 y2··· yn-1 = xn-n.

References for this problem can be found in [2].

Characteristics:




Example 1:
proc(n)
local i,j,k,kk,polys,factor;

  polys := array(1..n);

  for i from 1 to n-1 do		# poly
    polys[i] := 0;
      for j from 1 to n do        # start var
      factor := 1;

      for k from j to j+i-1 do
        if k <= n then factor := factor * x[k];
        else kk := k-n; 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 Sophia-Antipolis (France), emeris@sophia.inria.fr, (5 May 1995)



Mixed volumes bound the number of isolated roots. The results concern the Lift-Prune algorithm by Emiris and Canny (1995) [4]. Its public implementation is accessible at ftp://www.inria.fr/saga/emiris.

  #isolated mixed Lift-Prune
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: Lift-Prune 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 Sophia-Antipolis (France), emeris@sophia.inria.fr, 5 May 1995



Sparse resultants essentially produce multiplication tables and reduce the solution of zero-dimensional 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 n-roots. J. Symbolic Computation, 12:329--336, 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):117--149, August 1995.

[5]
L. Pottier. Bounds for degree of the n-cyclic system. INRIA Sophia-Antipolis, Manuscript, 1995.