# mixedVolume -- computes mixed volume of a polynomial system

## Synopsis

• Usage:
mv = mixedVolume(S)
(mv,sv) = mixedVolume(S,StableMixedVolume => true)
(mv,q,qsols) = mixedVolume(S,StartSystem => true)
(mv,sv,q,qsols) = mixedVolume(S,StableMixedVolume => true,StartSystem => true)
• Inputs:
• S, a list, whose entries are the polynomials of a square system
• Optional inputs:
• 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
• Consequences:
• Writes the system to temporary files

• Invokes the command phc -m (with option 4)

• Stores output of phc in temporary file

• Parses and outputs the solutions.

## Description

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.