next | previous | forward | backward | up | top | index | toc | Macaulay2 web site
PHCpack :: mixedVolume

mixedVolume -- computes mixed volume of a polynomial system



The mixed volume of a polynomial system S:={f1,…,fn} is defined as follows: Let P1,…,Pn be the Newton polytopes of f1,…,fn, i.e., Pi is the convex hull of the exponents of the monomials in the support of fi. The mixed volume of S is

1≤h≤n1≤i1…≤ih≤n (-1)n-hVn(Pi1+…+Pih),

where Vn 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;

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)

o6 = 8
i7 : (mv,sv) = mixedVolume(f,StableMixedVolume=>true)

o7 = (8, 10)

o7 : Sequence
i8 : (mv,q,qsols) = mixedVolume(f,StartSystem=>true);
i9 : q --let's take a look at the start system:

                               3 5                          2                          2
o9 = {(- .205377 - .978683*ii)x y  + (.943327 - .331864*ii)x y, (.673112 + .739541*ii)x  - .911067 - .412259*ii}

o9 : List
i10 : qsols --and its solutions:

o10 = {{.979319-.202321*ii, .930645-.365923*ii}, {-.979319+.202321*ii, .916812+.399319*ii}, {.979319-.202321*ii, .365923+.930645*ii}, {-.979319+.202321*ii, -.399319+.916812*ii}, {.979319-.202321*ii, -.930645+.365923*ii}, {-.979319+.202321*ii, -.916812-.399319*ii}, {.979319-.202321*ii, -.365923-.930645*ii}, {-.979319+.202321*ii, .399319-.916812*ii}}

o10 : List

Note that only those solutions with nonzero components are shown, even if StableMixedVolume 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.

See also

Ways to use mixedVolume :