Session S34 - Symbolic and Numerical Computation with Polynomials

Wednesday, July 21, 20:15 ~ 20:45 UTC-3

Mixed volume, mixed area and the cost of sparse homotopy

Gregorio Malajovich

Universidade Federal do Rio de Janeiro, Brasil   -   This email address is being protected from spambots. You need JavaScript enabled to view it.

The {\em Mixed Volume} is a generalization of the ordinary volume. It was originally defined by Minkowski in connection with surface and curvature of convex bodies. It is defined for a $n$-tuple of convex bodies $(\mathcal A_1, \dots, \mathcal A_n)$ in $\mathbb R^n$ by \[ V(\mathcal A_1, \dots, \mathcal A_n) = \frac{1}{n!}\ \frac{\partial^n} {\partial t_1 \partial t_2 \cdots \partial t_n} \ \mathrm{Vol}(t_1 \mathcal A_1 + \cdots + t_n \mathcal A_n) \] where $t_1, \dots, t_n \ge 0$ and the derivative is taken at $t_1=\dots=t_n=0$. \medskip For instance, if $\mathcal A \subseteq \mathbb R^n$ is a convex body with smooth boundary, its {\em surface area} is given by \[ V'(\mathcal A) = \frac{\partial}{\partial \epsilon}_{|\epsilon=0} \mathrm{Vol}(\mathcal A + \epsilon B^n) = n V(\mathcal A, \dots, \mathcal A, B^n) \] where $B^n$ stands for the unit Euclidean $n$-ball. \medskip

The famous theorems by Kushnirenko and Bernstein relate volumes and mixed volumes to the number of roots of sparse polynomial systems. Let $A_1, \dots, A_n \subseteq \mathbb Z^n$ be finite sets and let $\mathcal A_i = \mathrm{Conv(A_i)}$.

{\bf Theorem} [Bernstein, 1975]:{\sl The system of sparse polynomial equations $\mathbf f(\mathbf x)=0$ with \[ f_i(\mathbf x) = \sum_{\mathbf a \in A_i} f_{i\mathbf a} x_1^{a_1} x_2^{a_2} \dots x_n^{a_n} \] and coefficients $f_{i\mathbf a} \in \mathbb C$ has at most \[ n! V(\mathrm{Conv}(A_1), \dots, \mathrm{Conv}(A_n)) \] isolated roots in $(\mathbb C \setminus\{0\})^n$. } \medskip

In this talk, I will relate the cost of solving such a system to the {\em mixed area} of the tuple above, that is to \[ V'(\mathcal A_1, \dots,\mathcal A_n) = \frac{\partial}{\partial \epsilon}_{|\epsilon=0} V(\mathcal A_1+\epsilon B^n, \dots, \mathcal A_n+\epsilon B^n) = \sum_i V(\mathcal A_1, \dots, \stackrel{i\text{-th}}{B^n}, \dots, \mathcal A_n) \] \medskip

The mixed area above is closely related to the mixed area measure defined by Aleksandrov (1939). This is a measure on the unit sphere that depends on $n-1$ convex bodies. It is defined by the property that \[ V(\mathcal A_1, \dots, \mathcal A_{n-1}, \mathcal B) = \frac{1}{n}\int_{S^{n-1}} \lambda_{\mathcal B}(\Theta) \ \mathrm{d} F_{\mathcal A_1, \dots, \mathcal A_{n-1}}(\Theta) \] for every convex body $\mathcal B$ with support function $\lambda_{\mathcal B}$. If we set $\mathcal B$ equal to the unit ball $B^n$, the support function is constant and equal to one. The area $V'$ is just the integral of the area measure $f_{\mathcal A, \dots, \mathcal A}$ while the mixed area $V'(\mathcal A_1, \dots, \mathcal A_n)$ is the average over all subsets of $n-1$ convex bodies of the integral of the appropriate mixed area measure. \bigskip

I claim that there is a randomized algorithm with the following property. Assume that $A_1, \dots, A_n$ are fixed. The algorithm is given as input a system $\mathbf h$ with support $A_1, \dots, A_n$ with all its roots. It is also given as input a target system $\mathbf f$ that we want to solve. It is assumed that neither $\mathbf h$ or $\mathbf f$ belong to a certain real variety. Then, the algorithm produces approximate roots for all the roots of $\mathbf f$ in expected time bounded by \[ O(\mu_{\mathbf f}^2 \kappa_{\mathbf f} + \mu_{\mathbf h}^2 \kappa_{\mathbf h} ) \] plus logarithmic terms. Here $\mu_{\mathbf f}$ stands for the renormalized condition number (to be explained) and $\kappa_{\mathbf f}$ for the inbalance between the absolute value of the coefficients of $\mathbf f$. The previous bound is non-uniform, and some of the cost is hidden in the big-oh. The complet uniform bound depends on the input size and the geomety of the support polytopes. In particular, it depends linearly on their mixed area. More details and references can be found at: \url{https://arxiv.org/abs/2005.01223}

View abstract PDF