ENG 
ESP Session S34 - Symbolic and Numerical Computation with Polynomials
Talks
Wednesday, July 14, 11:00 ~ 11:30 UTC-3
A new algorithm for the equidimensional decomposition of affine varieties given by sparse polynomials
María Isabel Herrero
UBA - CONICET, Argentina - This email address is being protected from spambots. You need JavaScript enabled to view it.
Any algebraic variety can be uniquely decomposed as a finite irredundant union of equidimensional varieties (which are called its equidimensional components). The different known algorithms that compute this decomposition characterize these components in different ways. For example, we can mention the representation of components via equations that define them, via parametric representations, and from the numerical algebraic geometry viewpoint, the representation of components can be done through finite sets of witness points that characterize them.
When considering the sparse structure of the given polynomials defining the original variety, that is, the monomials that appear with non-zero coefficients in these polynomials, algorithms with better performance can be designed. Following this approach, in a previous work with Gabriela Jeronimo and Juan Sabia, we presented a symbolic algorithm that describes the equidimensional decomposition by means of finite witness point supersets for varieties defined by sparse polynomials. This algorithm has a complexity that depends on geometric-combinatorial invariants associated with the set of supports of the polynomials. Unfortunately, the description it computes is precise for generic polynomials with prescribed monomial structure, but in particular cases, the sets of points describing a component may contain extra points from components of higher dimension.
In this talk we will present recent results improving our previous algorithm. We will show new theoretical results based on homotopic deformations that allowed us to design a symbolic algorithm to compute, for a variety given by arbitrary sparse polynomials, a representation of its equidimensional components by means of witness sets with no extra points. The algorithm uses a subroutine we developed that, given a finite set of points in the variety, determines for each point the equidimensional component of the highest dimension that contains it. As our previous algorithm, the complexity of this new procedure is polynomial in the same type of invariants associated with the supports.
Joint work with Gabriela Jeronimo (UBA - CONICET, Argentina) and Juan Sabia (UBA - CONICET, Argentina).
Wednesday, July 14, 13:00 ~ 13:30 UTC-3
Symbolic vs Numerical: Allies or Enemies?
Josué Tonelli-Cueto
Inria Paris & IMJ-PRG, France - This email address is being protected from spambots. You need JavaScript enabled to view it.
In this introductory talk to the special session "Symbolic and Numerical Computation with Polynomials", we will give the motivation behind the session and introduce briefly the different talks of the session.
Joint talk with Matías Bender
Joint work with Matías Bender (Technische Universität Berlin, Germany).
Wednesday, July 14, 13:30 ~ 14:00 UTC-3
Bounds for degrees of syzygies
Carlos D'Andrea
Universitat de Barcelona, Spain - This email address is being protected from spambots. You need JavaScript enabled to view it.
We make explicit the exponential bound on the degrees of the polynomials appearing in the Effective Quillen-Suslin Theorem, and apply it jointly with the Hilbert-Burch Theorem to show that the syzygy module of a sequence of $m$ polynomials in $n$ variables defining a complete intersection ideal of grade two is free, and that a basis of it can be computed with bounded degrees. In the known cases, these bounds improve previous results.
Joint work with Teresa Cortadellas Benitez (Universitat de Barcelona) and Eulalia Montoro (Universitat de Barcelona).
Wednesday, July 14, 14:00 ~ 14:30 UTC-3
Computing efficiently the non-properness set of polynomial maps on the plane
Elias Tsigaridas
Inria Paris, France - This email address is being protected from spambots. You need JavaScript enabled to view it.
We present new mathematical and computational tools to develop a complete and efficient algorithm for computing the set of non-properness of (dominant) polynomial maps in the complex (and the real) plane. The set of non-properness is a subset of the plane where a dominant polynomial map is not proper. The algorithm takes into account the sparsity of polynomials as it depends on their Newton polytopes. As a byproduct it also provides a representation of the set of non-properness as a union of algebraic or semi-algebraic sets, that correspond to edges of the Newton polytopes.
Joint work with Boulos El Hilany (TU Braunschweig, Germany).
Wednesday, July 14, 14:30 ~ 15:00 UTC-3
Distance to the stochastic part of phylogenetic varieties
Marina Garrote-López
Universitat Politècnica de Catalunya, Spain - This email address is being protected from spambots. You need JavaScript enabled to view it.
The main goal of phylogenetic reconstruction is to recover the evolutionary history of a group of living species by using solely the information of their genome. To model evolution, one usually assumes that DNA sequences evolve according to a Markov process on a phylogenetic tree ruled by a model of nucleotide substitutions. This allows to define a distribution at the leaves of the trees and one might be able to obtain polynomial relationships among the probabilities of different characters. The study of these polynomials and the geometry of the algebraic varieties defined by them can be used to reconstruct phylogenetic trees.
However, not all points in these algebraic varieties have biological sense. In this talk, we will discuss the importance of studying the subset of these varieties with biological sense and explore the extent to which restricting to these subsets can provide insight into existent methods of phylogenetic reconstruction. We will analyse the projection into these subsets, which can be seen as an optimization problem and can be solved using nonlinear programming algorithms. As these algorithms do not guarantee a global solution, we use a different approach that allows us to find a global optimum. Numerical algebraic geometry and computational algebra play a fundamental role here. We will show some results on trees evolving under groups-based models and, in particular, we will explore the long-branch attraction phenomenon.
Joint work with Marta Casanellas (Universitat Politècnica de Catalunya) and Jesús Fernández-Sánchez (Universitat Politècnica de Catalunya).
Wednesday, July 14, 15:00 ~ 15:30 UTC-3
Approaching equidistribution through Determinantal Point Processes.
Ujué Etayo
Universidad de Cantabria, Spain - This email address is being protected from spambots. You need JavaScript enabled to view it.
When one works with Riemannian manifolds it can be difficult to give a sequence of point configurations that tends to the uniform distribution in the manifold. Many determinant point processes have this property. In this talk we will explain what a determinant point process is, what properties they have and how we can define "natural" processes of the variety with optimal equidistribution properties.
Wednesday, July 14, 15:30 ~ 16:00 UTC-3
Weak identifiability of differential algebraic equation systems
Gabriela Jeronimo
Universidad de Buenos Aires, Argentina - This email address is being protected from spambots. You need JavaScript enabled to view it.
Mathematical models of biochemical systems often describe the dynamics of the species concentrations by means of autonomous systems of ordinary differential equations given by polynomials or rational functions depending on parameters with unknown values. Parameter structural identifiability mainly addresses the question of deciding whether the parameter values can be uniquely determined from noise-free data on the input-output behaviour of the system. This problem has been broadly studied for several notions of identifiability using a variety of tools and under different perspectives, including Taylor series, Gröbner bases, differential algebra and numerical algebraic geometry based approaches.
In this talk we will introduce a notion of weak identifiability that extends the structural identifiability considered by G. Craciun and C. Pantea (2008), for systems arising from biochemical reaction networks under mass-action kinetics, to the general class of ODE systems with finitely many arbitrary algebraic outputs. More precisely, we consider differential algebraic equation systems of the form \[\Sigma := \left\{ \begin{array}{lll} \dot {\mathbf{x}} & = & \mathbf{F}(\mathbf{x},\theta,\mathbf{u})\\ \mathbf{y} & = & \mathbf{G}(\mathbf{x},\theta,\mathbf{u}) \end{array} \right. \] where $\mathbf{F}$ and $\mathbf{G}$ are two families of rational functions, $\mathbf{x}$, $\mathbf{u}$ and $\mathbf{y}$ are sets of variables representing the states, inputs and outputs of the system respectively, and $\theta$ are the unknown parameters. We adopt a multi-experiment approach, allowing for as many experiments as needed with different initial conditions.
Our notion of weak identifiability requires the injectivity of a map induced by the given system $\Sigma$. We will show that it can be effectively checked with finitely many successive derivatives of the input equations by studying the injectivity of a certain rational map of the parameters $\theta$ defined from the coefficients of the polynomials involved in the representation of the rational functions giving those derivatives. Finally, we will compare the notion of weak identifiability with other identifiability definitions given in previous works, including the approach via input-output equations.
Joint work with Pablo Solernó (Universidad de Buenos Aires, Argentina).
Friday, July 16, 11:30 ~ 12:00 UTC-3
General witness sets
Frank Sottile
Texas A&M University, USA - This email address is being protected from spambots. You need JavaScript enabled to view it.
Numerical algebraic geometry has a close relationship to intersection theory from algebraic geometry. We deepen this relationship, explaining how rational or algebraic equivalence gives a homotopy. We present a general notion of witness set for subvarieties of a smooth complete complex algebraic variety using ideas from intersection theory. Under appropriate assumptions, general witness sets enable numerical algorithms such as sampling and membership. These assumptions hold for products of flag manifolds. We introduce Schubert witness sets, which provide general witness sets for Grassmannians and flag manifolds.
Friday, July 16, 12:00 ~ 12:30 UTC-3
Rigid homotopy and structured polynomial systems
Felipe Cucker
City University of Hong Kong, Hong Kong - This email address is being protected from spambots. You need JavaScript enabled to view it.
This talk deals with the average complexity of solving structured polynomial systems that are characterized by a low evaluation cost, as opposed to the dense random model previously used. Firstly, we design a continuation algorithm that computes, with high probability, an approximate zero of a polynomial system given only as black-box evaluation program. Secondly, we introduce a universal model of random polynomial systems with prescribed evaluation complexity $L$. Combining both, we show that we can compute an approximate zero of a random structured polynomial system with $n$ equations of degree at most $\delta$ in $n$ variables with only poly($n,\delta$)$L$ operations with high probability. This exceeds the expectations implicit in Smale’s 17th problem.
Joint work with Peter Bürgisser (Technische Universität Berlin) and Pierre Lairez (Inria).
Friday, July 16, 12:30 ~ 13:00 UTC-3
Numerical homotopies from Khovanskii bases
Elise Walker
Texas A&M University, USA - This email address is being protected from spambots. You need JavaScript enabled to view it.
Homotopies are useful numerical methods for solving systems of polynomial equations. Embedded toric degenerations are one source for homotopy algorithms. In particular, if a projective variety has a toric degeneration, then linear sections of that variety can be optimally computed using the polyhedral homotopy. Any variety whose coordinate ring has a finite Khovanskii basis is known to have a toric degeneration. We provide embeddings for this Khovanskii toric degeneration and use the resulting homotopy to compute general linear sections of the variety.
Joint work with Michael Burr (Clemson University, USA) and Frank Sottile (Texas A&M University, USA).
Friday, July 16, 13:00 ~ 13:30 UTC-3
A complete error analysis on solving an overdetermined system in computer vision using linear algebra
Margaret H. Regan
Duke University, USA - This email address is being protected from spambots. You need JavaScript enabled to view it.
Many problems in computer vision are represented using a parametrized overdetermined system of polynomials which must be solved quickly and efficiently. Classical methods for solving these systems involve specialized solvers based on Groebner basis techniques or utilize randomization in order to create well-constrained systems for numerical techniques. We propose new methods in numerical linear algebra for solving such overdetermined polynomial systems and provide a complete error analysis showing that the numerical approach is stable. Examples will be provided to show the efficacy of the method and how the error in the data affects the error in the solution.
Joint work with Jonathan Hauenstein (University of Notre Dame, USA).
Friday, July 16, 13:45 ~ 14:15 UTC-3
On the normalized condition number of a computational problem
Federico Carrasco
UdelaR, Uruguay - This email address is being protected from spambots. You need JavaScript enabled to view it.
We define a normalized condition number which may be applied to many different computational problems and satisfy desirable properties. In addition, we obtain a general expression for its expected value. Furthermore, when the set of inputs with a given output is a linear space, we give a more detailed statement, which imply that may be a better choice than the usual condition number.
Friday, July 16, 14:15 ~ 14:45 UTC-3
Efficient algorithms for torus actions by interior-points methods for unconstrained geometric programming
Peter Bürgisser
TU Berlin, Germany - This email address is being protected from spambots. You need JavaScript enabled to view it.
There has been recent interest in the complexity of solving fundamental computational problems in invariant theory. These problems arise in the setting of an action of a reductive group on a vector space and capture a diverse set of problems in different areas of computer science, mathematics, and physics. Both algebraic and analytical approaches have been suggested. While no efficient algorithms are known for general groups, polynomial time algorithms were recently found when the acting group is an algebraic torus.
In the talk we focus on analytic solutions for the norm minimization and scaling problems in the case of a torus action. This amounts to unconstrained geometric programming problems. We introduce condition measures for these problems and provide condition-based analyses of interior-point methods for them. This way, we generalize the iteration complexity of recent interior-point methods for matrix scaling and matrix balancing.
See https://arxiv.org/abs/2008.12110
Joint work with Yinan Li (Centrum Wiskunde & Informatica (CWI) and QuSoft), Harold Nieuwboer (Korteweg–de Vries Institute for Mathematics and QuSoft, University of Amsterdam) and Michael Walter (Korteweg–de Vries Institute for Mathematics, Institute for Theoretical Physics, Institute for Language, Logic, and Computation, and QuSoft, University of Amsterdam).
Friday, July 16, 14:45 ~ 15:15 UTC-3
Sub-Linear Point Counting for Arbitrary Curves Over Prime Power Rings
J. Maurice Rojas
Texas A&M University, USA - This email address is being protected from spambots. You need JavaScript enabled to view it.
Let $k,p\in \mathbb{N}$ with $p$ prime and let $f\in\mathbb{Z}[x_1,x_2]$ have degree $d$ and all coefficients in $\{0,\ldots,p^{k-1}\}$. We give the first algorithm, with complexity sub-linear in $p$, to count the number of roots of $f$ over $\mathbb{Z}/(p^k)$: Our Las Vegas randomized algorithm works in time $(dk\log p)^{O(1)}\sqrt{p}$. The key is an efficient reduction from point counting over prime power rings to point counting over finite fields. Another consequence of our work is a recurrence that simplifies the computation of p-adic Igusa local zeta functions for curves.
The practical importance of our work is that it is faster than performing a resolution of singularities on the underlying curve and then applying a multivariate version of Hensel's Lemma. In particular, our algorithm sets the stage for point counting in higher dimensions, where resolution of singularities has completely impractical complexity.
Joint work with Caleb Robelle, University of Maryland, Baltimore County and Yuyu Zhu, Texas A&M University.
Friday, July 16, 15:15 ~ 15:45 UTC-3
Towards correct and efficient computations with polynomials
Michael Burr
Clemson University, United States - This email address is being protected from spambots. You need JavaScript enabled to view it.
Traditionally, there has been a trade-off between efficiency and correctness when deciding between symbolic and numeric computations. Hybrid symbolic-numeric computations can avoid this trade-off and be both efficient and correct. Such hybrid methods have been particularly fruitful in algorithms for solving polynomial systems.
In this talk we will discuss a new framework for the design of hybrid symbolic-numeric computations. This framework is devised to expose the key details so that both the efficiency and the correctness of the developed algorithms can be studied directly. We will illustrate this framework on algorithms for finding the isolated roots of systems of polynomials.
Joint work with Chee Yap (New York University) and Juan Xu (Beihang University).
Wednesday, July 21, 16:00 ~ 16:30 UTC-3
Multigraded Sylvester forms, duality and elimination matrices
Laurent Busé
Université Côte d'Azur, Inria, France - This email address is being protected from spambots. You need JavaScript enabled to view it.
In this talk, we will consider the equations of the elimination ideal associated to $n+1$ generic multihomogeneous polynomials defined over a product of projective spaces of dimension $n$. We will discuss a duality property and introduce multigraded Sylvester forms in order to make this latter duality explicit. These results provide a partial generalization of similar properties that are known in the setting of homogeneous polynomial systems defined over a single projective space, that we will also recall. We will also discuss a new family of elimination matrices that can be used for solving zero-dimensional multiprojective polynomial systems by means of linear algebra methods.
Joint work with Marc Chardin (Institut de Mathématiques de Jussieu, CNRS, Sorbonne Université) and Navid Nemati (Université Côte d'Azur, Inria).
Wednesday, July 21, 16:30 ~ 17:00 UTC-3
Sign conditions for the existence of at least one positive solution of a sparse polynomial system
Alicia Dickenstein
Universidad de Buenos Aires, Argentina - This email address is being protected from spambots. You need JavaScript enabled to view it.
We give sign conditions on the support and coefficients of a sparse system of d generalized polynomials in d variables that guarantee the existence of at least one positive real root, based on degree theory and Gale duality. In the case of integer exponents, we relate our sufficient conditions to algebraic conditions that emerged in the study of toric ideals.
Joint work with Frédéric Bihan (Université Savoie Mont Blanc) and Magalí Giaroli (Universidad de Buenos Aires).
Wednesday, July 21, 17:00 ~ 17:30 UTC-3
A Macaulay formula for the sparse resultant
Martín Sombra
ICREA and Universitat de Barcelona, Spain - This email address is being protected from spambots. You need JavaScript enabled to view it.
Compact and easy-to-evaluate formulae for resultants is a kind of "Philosopher's Stone" in computer algebra. In this search, determinantal formulae are important pearls that are hard to find. Macaulay showed in 1902 that homogeneous resultants can be computed as the quotient of two determinants 'à la Sylvester'. In 1993, Canny and Emiris extended his construction to sparse resultants, and conjectured that these can also be computed as the quotient of two determinants 'a la Sylvester'. In this talk, we will review the history of this problem and show how we managed to solve this conjecture.
Joint work with Carlos D'Andrea (Universitat de Barcelona, Spain) and Gabriela Jeronimo (Universidad de Buenos Aires, Argentina).
Wednesday, July 21, 17:30 ~ 18:00 UTC-3
Subresultants of $(x-a)^m$ and $(x-b)^n$, Jacobi polynomials and complexity
Teresa Krick
University of Buenos Aires and CONICET, Argentina - This email address is being protected from spambots. You need JavaScript enabled to view it.
We show that the coefficients of the subresultants of $(x-a)^m$ and $(x-b)^n$ with respect to the monomial basis can be computed in linear arithmetic complexity, which is faster than for arbitrary polynomials. This is obtained as a consequence of the amazing though seemingly unnoticed fact that these subresultants are essentially scalar multiples of Jacobi polynomials.
Joint work with Alin Bostan (INRIA Saclay, France), Agnes Szanto (NCSU, USA) and Marcelo Valdettaro (UBA, Argentina).
Wednesday, July 21, 18:00 ~ 18:30 UTC-3
Complexity of Plantinga-Vegter Algorithm
Alperen Ergur
UTSA, USA - This email address is being protected from spambots. You need JavaScript enabled to view it.
Plantinga-Vegter algorithm is a commonly used subdivision based method for meshing curves and surfaces. First rigorous complexity analysis of the method was provided by Burr, Gao, and Tsigaridas (https://doi.org/10.1016/j.jsc.2019.06.004) using the worst-case bit size complexity model. I'd like present beyond-worst-case analysis point of view on the complexity of Plantinga-Vegter algorithm using techniques from complexity theory of numerical algorithms and high dimensional probability. The ideas and techniques introduced in the talk are somewhat general and could be applied to a more broad family of symbolic-numeric algorithms.
Joint work with Felipe Cucker ( City University of Hong Kong) and Josue Tonelli-Cueto (Inria Paris & IMJ-PRG).
Wednesday, July 21, 18:45 ~ 19:15 UTC-3
Smooth Points on Semi-algebraic sets
Agnes Szanto
North Carolina State University, United States - This email address is being protected from spambots. You need JavaScript enabled to view it.
Many algorithms for determining properties of real algebraic or semi-algebraic sets rely upon the ability to compute smooth points. In this talk, I present a simple procedure based on computing the critical points of some well-chosen function that guarantees the computation of smooth points in each connected bounded component of a real atomic semi-algebraic set. Our technique is intuitive in principal, performs well on previously difficult examples, and is straightforward to implement using existing numerical algebraic geometry software. I also present the application of our method to design an efficient algorithm to compute the real dimension of algebraic sets, the original motivation for this research.
Joint work with Katherine Harris (North Carolina State University) and Jonathan Hauenstein (University of Notre Dame).
Wednesday, July 21, 19:15 ~ 19:45 UTC-3
Decomposable Sparse Polynomial Systems
Jose Israel Rodriguez
University of Wisconsin --- Madison, USA - This email address is being protected from spambots. You need JavaScript enabled to view it.
Améndola et al. proposed a method for solving systems of polynomial equations lying in a family which exploits a recursive decomposition into smaller systems. A family of systems admits such a decomposition if and only if the corresponding Galois group is imprimitive. When the Galois group is imprimitive we consider the problem of computing an explicit decomposition. A consequence of Esterov’s classification of sparse polynomial systems with imprimitive Galois groups is that this decomposition is obtained by inspection. In this talk, I will discuss how this leads to a recursive algorithm to solve decomposable sparse systems.
Joint work with Taylor Brysiewicz (Max Planck Institute for Mathematics in the Sciences in Leipzig), Frank Sottile (Texas A&M) and Thomas Yahl (Texas A&M).
Wednesday, July 21, 19:45 ~ 20:15 UTC-3
Novel Range Functions via Recursive Lagrange Interpolation, and its effectiveness in Real Root Isolation
Chee Yap
Courant, NYU, United States - This email address is being protected from spambots. You need JavaScript enabled to view it.
ABSTRACT: Range functions are an important tool for interval computations, and they can be employed for the problem of root isolation. In this paper, we first introduce new classes of range functions for real functions, using the remainder form framework of Cornelius and Lohner (1984). In particular, we propose a family of {\bf recursive Lagrange forms}. We then use some forms with cubic and quartic convergence for isolating the real roots of square-free polynomials with the algorithm {\bf Eval}, a relatively recent algorithm that has been shown to be effective and practical. Finally, we compare the performance of our new range functions against the standard Taylor forms. Range functions are often compared in isolation; in contrast, our holistic comparison is based on their performance in the {\bf Eval} algorithm. Here, some unique features of our recursive Lagrange forms which are not found in Taylor forms can be exploited. Theoretically, we expect a 3-fold speedup. Experimentally, we see a 2- to 4-fold speedup in {\bf Eval}.
Joint work with Kai Hormann (USI , Lugano, Switzerland) and Lucas Kania (USI, Lugano, Switzerland).
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}