3:00pm - 5:00pmNumerical methods for structured polynomial system solving
Chair(s): Alperen Ergur (TU Berlin), Pierre Lairez (INRIA), Gregorio Malajovich (Universidade Federal do Rio de Janeiro, Brazil), Josue Tonelli-Cueto (TU Berlin)
Improvements in the understanding of numerical methods for dense polynomial system solving led to the complete solution of Smale's 17th problem. At this point, it remains an open challenge to achieve the same success in the solution of structured polynomial systems: explain the typical behavior of current algorithms and devise polynomial-time algorithms for computing roots of polynomial systems. In this minisymposium, researchers will present the current progress on applying numerical methods to structured polynomial systems.
(25 minutes for each presentation, including questions, followed by a 5-minute break; in case of x<4 talks, the first x slots are used unless indicated otherwise)
Polyhedral Real Homotopy Continuation
Timo de Wolff, Alperen Ergür
TU Berlin
We design a homotopy continuation algoritm to find real roots of sparse polynomial systems based on numerically tracking a well-known geometric deformation process called Viro’s patchworking. The main advantage of our algorithm is that it entirely operates over the field of real numbers and tracks the optimal number of solution paths. The price for this property is that the algorithm is not guaranteed to work universally, but requires to solve and track polynomial systems located in an unbounded component of the complement of the A-discriminant. We provide a relative entropy programming based relaxation to certify this requirement on the input data.
Root counts of structured algebraic systems
Ioannis Z. Emiris1, Raimundas Vidunas2, Evangelos Bartzos3, Josef Schicho4
1National and Kapodistrian University of Athens, 2U.Vilnius, Lithuania, 3NKU Athens, 4JKU Linz, Austria
We consider bounds on the number of complex roots of well-constrained algebraic systems, namely mixed volume and multi-homogeneous Bezout bound. We relate these bounds to permanent expressions, generalizing this relationship to the case of systems whose Newton polytopes are products of arbitrary polytopes in complementary subspaces. This improves the computational complexity of determining the bounds. We apply the bounds to obtaining new counts on the number of complex embeddings of minimally rigid graphs in the plane, in space, and on the sphere. We relate the bounds to certain combinatorial properties of the graphs such as the number of ways to orient the edges according to certain rules. We focus on bounds for semi-mixed algebraic systems where equations are partitioned to subsets with common Newton polytopes. This is applied to counting the number of totally mixed Nash equilibria in games of several players.
A local complexity theory
Teresa Krick1, Felipe Cucker2
1Universidad de Buenos Aires, 2City University of Hong Kong
I will describe advances on an on-going project of establishing a local complexity theory. This is inspired on the concept of smoothed analysis introduced some years ago by Spielman and Teng, which takes as cost the supremum of the average on small balls around points. Here we are interested in styuding directly the average on small balls around points, without considering the supremum on the whole space. We believe that this would be a more accurate notion of cost for practical problems than the smoothed complexity. Our first analysis studies local complexity for real conic condition numbers, under uniform and Gaussian distributions.
Low-degree approximation of real singularities
Antonio Lerario1, Paul Breiding2, Daouda Niang Diatta3, Hanieh Keneshlou2
1SISSA, 2MPI-MSI Leipzig, 3Université Assane SECK de Ziguinchor
In this talk I will discuss some recent results that allow to approximate a real singularity given by polynomial equations of degree d (e.g. the zero set of a polynomial, or the number of its critical points of a given Morse index) with a singularity which is diffeomorphic to the original one, but it is given by polynomials of degree O(d^{1/2} log d). The approximation procedure is constructive (in the sense that one can read the approximating polynomial from a linear projection of the given one) and quantitative (in the sense that the approximating procedure will hold for a subset of the space of polynomials with measure increasing very quickly to full measure as the degree goes to infinity).
I will also discuss the potential of this procedure for improving the average complexity of some algorithms.
This is based on a combination of joint works with P. Breiding, D. N. Diatta and H. Keneshlou.
