mixedVolume -- mixed volume of a polynomial system (invokes "phc -m")

Synopsis

Usage:
mv = mixedVolume(S)
(mv,sv) = mixedVolume(S,stableMV => true)
(mv,q,qsols) = mixedVolume(S,startSystem => true)
(mv,sv,q,qsols) = mixedVolume(S,stableMV => true, startSystem => true)
Inputs:
- S, a list, whose entries are the polynomials of a square system
Optional inputs:
- stableMV => ..., -- mixed volume of a polynomial system (invokes "phc -m")
- startSystem => ..., -- mixed volume of a polynomial system (invokes "phc -m")
Outputs:
- mv, an integer, the mixed volume of the system S
- sv, an integer, the stable mixed volume of the system S
- q, a list, whose entries are polynomials in a random coefficient system, used as a start system for the homotopy
- qSols, a list, whose entries are solutions of the start system q

Description

The mixed volume of a polynomial system S:={f₁,…,f_n} is defined as follows: Let P₁,…,P_n be the Newton polytopes of f₁,…,f_n, i.e., P_i is the convex hull of the exponents of the monomials in the support of f_i. The mixed volume of S is

∑_1≤h≤n ∑_{1≤i₁…≤i_h≤n} (-1)^n-hV_n(P_i₁+…+P_{i_h}),

where V_n denotes the n-dimensional Euclidean volume.

Bernstein’s theorem (D. N. Bernstein,The number of roots of a system of equations, Functional. Anal. Appl 9 (1975), no. 3, 183-185), a generalization of the classical Bezout’s theorem, shows that for a zero-dimensional system, the mixed volume provides an upper bound on the number of complex isolated roots. If the coefficients of the system are sufficiently generic, the mixed volume is a sharp bound.

i1 : R = CC[x,y];

i2 : f = { x^3*y^5 + y^2 + x^2*y, x*y + x^2 - 1};

i3 : I=ideal f

             3 5    2     2   2
o3 = ideal (x y  + x y + y , x  + x*y - 1)

o3 : Ideal of R

i4 : dim I
-- warning: experimental computation over inexact field begun
--          results not reliable (one warning given per session)

o4 = 0

i5 : degree I

o5 = 10

i6 : m = mixedVolume(f) -- counts the number of complex roots in the torus (without zero components)
using temporary files /tmp/M2-5174-1PHCinput and /tmp/M2-5174-1PHCoutput

o6 = 8

i7 : (mv,sv) = mixedVolume(f,stableMV=>true)
using temporary files /tmp/M2-5174-2PHCinput and /tmp/M2-5174-2PHCoutput

o7 = (8, 10)

o7 : Sequence

i8 : (mv,q,qsols) = mixedVolume(f,startSystem=>true);
using temporary files /tmp/M2-5174-3PHCinput and /tmp/M2-5174-3PHCoutput

i9 : q --let's take a look at the start system:

                             3 5                          2                
o9 = {(.728837 - .684688*ii)x y  + (.973828 + .227286*ii)x y + (- .976956 +
     ------------------------------------------------------------------------
                 2                        2
     1.74515*ii)y , (.44653 - .894768*ii)x  + (- .617445 - .786614*ii)x*y +
     ------------------------------------------------------------------------
     1.47976 + 1.34547*ii}

o9 : List

i10 : qsols --and its solutions:

o10 = {{.646817-.392041*ii, .597831+.070632*ii}, {-.537105+.902622*ii,
      -----------------------------------------------------------------------
      .429286-.626667*ii}, {.0288432-.256438*ii, .824626+3.80858*ii},
      -----------------------------------------------------------------------
      {-1.14526+.953079*ii, .771425+.289597*ii}, {-1.15438+.260242*ii,
      -----------------------------------------------------------------------
      -.114404+.885928*ii}, {.82435-1.20233*ii, -.962744+.262992*ii},
      -----------------------------------------------------------------------
      {1.38479-.511964*ii, -.389985-.906534*ii}, {-.0480499+.246829*ii,
      -----------------------------------------------------------------------
      -1.15603-3.78453*ii}}

o10 : List

Note that only those solutions with nonzero components are shown, even if stableMV is true. See the end of the temporary output file for the solutions with zero components.

The method mixedVolume calls an Ada translation of ACM TOMS Algorithm 846: MixedVol: a software package for mixed-volume computation by Tangan Gao, T. Y. Li, Mengnien Wu, ACM TOMS 31(4):555-560, 2005.

Ways to use `mixedVolume` :

mixedVolume(List)

mixedVolume -- mixed volume of a polynomial system (invokes "phc -m")

Synopsis

Description

See also

Ways to use mixedVolume :

Ways to use `mixedVolume` :