Abstract: This talk is an introductory lecture for the session. Recent advances in symbolic and numeric methods have expanded the approaches to solving polynomial equations and their applications. We highlight these methods and their applications, aligning with the topics that will be presented in the session. Supplementary tools such as polyhedral homotopy continuation, Khovanskii basis, monodromy, and tropical geometry are introduced. As fields of applications of symbolic-numeric methods, we showcase computer vision, optimization, dynamical systems, and chemical reaction networks.

Abstract: The Kuramoto model is a dynamical system that models the interaction of coupled oscillators. There has been much work to effectively bound the number of equilibria to the Kuramoto model for a given network. By formulating the Kuramoto equations as a system of algebraic equations, we first relate the complex root count of the Kuramoto equations to the combinatorics of the underlying network by showing that the complex root count is generically equal to the normalized volume of the corresponding adjacency polytope of the network. We then give explicit algebraic conditions under which this bound is strict and show that there are conditions where the Kuramoto equations have infinitely many equilibria.

Abstract: In this talk we introduce monodromy coordinates. Given a parametrized family of zero-dimensional polynomial systems, monodromy solving is an effective numerical algorithm for computing a solution set to a single instance, provided the monodromy group of the family is transitive. Thanks to modern software implementations, this algorithm can be so fast that the bottleneck to solving a system lies in the memory required to store all of the solutions. The novel concept of monodromy coordinates provides a time-memory tradeoff which offers the ability to solve large polynomial systems with little storage requirements, at the cost of the computation taking longer. We outline the basic structure of this data-type, its benefits, and its drawbacks.

Abstract: Galois/monodromy groups attached to parametric systems of polynomial equations provide a method for detecting the existence of symmetries in solution sets. Beyond the question of existence, one would like to compute formulas for these symmetries, towards the eventual goal of solving the systems more efficiently. I will describe one possible approach to this task using numerical homotopy continuation and multivariate rational function interpolation. I will illustrate this approach on practical examples of 3D reconstruction formulated by minimal problems in computer vision. This is joint work with Timothy Duff, Tomas Pajdla and Margaret Regan.

Link to paper: arXiv:2312.12685

Link to Github: DecomposingPolynomialSystems.jl

Abstract: The concept of the Gröbner fan for a polynomial ideal, pioneered by Mora and Robbiano in 1988, offers a powerful polyhedral framework wherein the maximal cones correspond to the reduced Gröbner bases of the ideal. Within this geometric structure lies the tropical variety, a subcomplex of the Gröbner fan, used for diverse applications in mathematics and beyond. Despite its significance, the computational complexity associated with tropical varieties restricts practical computations to small-scale instances.

In this talk, we delve into prototypic examples, particularly focusing on tropical Grassmannians and flag varieties. These examples, along with their combinatorial counterparts like Young tableaux and Gelfand-Cetlin polytopes, offer valuable insights into the broader landscape of tropical geometry. Moreover, we describe a geometric approach using mutations of polytopes, which aids in taking Gröbner walks within the tropical fan alongside these polytopes to effectively compute various cones within the tropical varieties. One application of this method is to compute toric degeneration of varieties, which are popular objects in algebraic geometry as they can be modeled on polytopes and polyhedral fans. This is mainly because there is a dictionary between their geometric properties and the combinatorial invariants of their polytopes. This dictionary can be extended from toric varieties to arbitrary varieties through toric degenerations. I will describe how to obtain such degenerations using the theory of Gröbner fans and tropical geometry.

This is based on joint work with Oliver Clarke.

Abstract: Accurate upper bounds on the number of roots of a polynomial system play a key role in numerical algebraic geometry. In this talk, I will discuss various strategies for sharpening the classical BKK bound, by replacing the mixed volume with a tropical intersection number. This also allows us to construct explicit start systems and homotopies that generalize the polyhedral homotopies of Huber and Sturmfels, and I will briefly demonstrate a Julia implementation that uses and extends the tropical functionality in OSCAR to compute such homotopies. As a case study, we use steady state systems from chemical reaction network theory, for which our tropical root bounds can be shown to be generically sharp.

This is a combination of joint works in progress with Elisenda Feliu, Paul Helminck, Yue Ren, Benjamin Schröter and Máté Telek.

Abstract: Subalgebra (SAGBI) bases were introduced as an analogue of Groebner bases to polynomial algebras. Subsequently, they were generalized to Khovanskii bases, which have many elegant theoretical properties. For example, Newton-Okounkov bodies can be constructed from Khovanskii bases, and the volume of the Newton-Okounkov body can be used to bound the number of solutions to zero-dimensional systems of equations.

Subalgebra bases, on the other hand, are typically easier to compute than Khovanskii bases, and there are several existing software packages for their computation. In this talk, we will present an equivalence between subalgebra bases for quotient rings and Khovanskii bases. In particular, we will see how to use existing software packages for subalgebra bases to compute Newton-Okounkov bodies.

Abstract: We present a new algorithm to solve structured polynomial equations over an algebraically closed field. The algorithm is based on eigenvalue computations. We assume that the equations are defined on a unirational variety and specialize the construction of Macaulay matrices to this setting. When the parameterizing functions form a Khovanskii basis, these matrices can be computed in a nice combinatorial way. This plays a fundamental role in the implementation, because Khovanskii (or SAGBI) bases are the analogous notion of Gröbner bases for subalgebras of polynomial rings. To the best of our knowledge, Khovanskii bases had not been used in symbolic equation solving before. We illustrate our algorithm by solving equations on del Pezzo surfaces and Grassmannians. This is a joint work with Marta Panizzut and Simon Telen.

arXiv:2306.14871

Abstract: The algebraic degree of an optimization problem is a well studied topic in applied algebraic geometry. It appears in statistics, semidefinite programming, computer vision and physics. Geometrically, these degrees are the degree of a projection map and can be computed by determining the fiber over a general point. Algebraically, this counts the number of solutions to a particular system of polynomial equations, but they can also be understood in terms of topological invariants using the Euler obstruction function. In this talk, we will recall the unbalanced Procrustes problem (UPP) and introduce the algebraic degree of UPPs (joint work with Thomas Yahl).

Abstract: The monodromy group (over the complex numbers) is a geometric invariant that encodes the structure of the solutions for a parameterized family of polynomial systems and can be computed using numerical algebraic geometry. An approach over the real numbers was developed by Hauenstein and I as the real monodromy structure, which is computed piece-wise to obtain tiered characteristics of the real solution set. This work generalizes the real monodromy structure to give information about partial permutations of real solutions induced by loops in an open subset of the parameter space. The talk will explain the new methods using motivating examples in optimization such as low-rank approximation and ellipse-fitting. This is joint work with Tim Duff.