# 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:
• interactive => ..., default value false, option to switch to the interactive mode of phc -m
• numThreads => ..., default value 0, option to set the number of threads when solving a start system
• StableMixedVolume => ..., default value false, optional input for computation of the stable mixed volume
• StartSystem => ..., default value false, optional input for computation of mixed volume by solving a random coefficient system
• Verbose => ..., default value false, option to specify whether additional output is wanted
• 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:=\{f_1,\dots,f_n\}$ is defined as follows: Let $P_1,\dots,P_n$ be the Newton polytopes of $f_1,\dots,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 $$\sum_{1\leq h\leq n} \sum_{1\leq i_1\dots\leq i_h\leq n} (-1)^{n-h}V_n(P_{i_1}+\dots+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; 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 o9 = {(- .205377 - .978683*ii)x y + (.943327 - .331864*ii)x y, (.673112 + ------------------------------------------------------------------------ 2 .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.