Schedule for: 24w5197 - Positive Solutions of Polynomial Systems Arising from Real-life Applications

In theoretical physics, a semi-algebraic set contained in a complex projective variety is called a positive geometry if it is equipped with a unique top-degree differential form satisfying some axioms. Examples include convex polyhedra, positive toric varieties and positive Grassmannians. Positive geometry is a developing branch of mathematics which studies the algebra, combinatorics and geometry of these objects, guided by questions from theoretical physics. In this lecture I will give precise definitions, work out examples and report on recent progress and challenges.

In applications of algebraic geometry, it is the real (often positive) solutions which matter. The gold standard for bounds on the number of real zeroes is Descartes' bound for univariate polynomials. Multivariate generalisations remain elusive. Khovanskii famously gave astronomical fewnomial bounds for positive solutions to a system of equations that depend on the number of monomials. While improved by work of Bihan and others, the bounds remain unrealistically large. Bihan's method, Gale duality ofor polynomial systems, replaces a system of n polynomials in n variables and n+1+k monomials by a system of rational functions in a k-dimensional polyhedron. This is particularly efficacious when k=1 (a circuit) where it gives a Descartes'-like bound. I will survey these developments and lay out some challenges, including extending this to non-standard real structures.

Numerical algebraic geometry provides a collection of algorithms classically designed to compute and analyze the set of complex solutions to a system of polynomial equations. Coupling numerical algebraic geometry algorithms with reality revealing approaches, such as critical point methods, yields computational methods for computing and analyzing the real points inside of the complex solution set. This talk will provide an introduction to some of these methods, demonstrate them on various applications, and consider some current challenges associated with numerically computing real solutions.

Most of the researchers in algebraic geometry have heard the name of Gröbner bases, a very useful computational tool introduced by Bruno Buchburger in 1965. However, fewer people are aware of another important computational tool in algebraic geometry called Cylindrical Algebraic Decomposition (CAD). CAD is introduced by George Collins in the 1970s. Its initial purpose was for Quantifier Elimination in nonlinear real arithmetic logic, but later found many more applications. Consider a system of polynomial equations where its coefficients involve parameters and thus are not all fixed numbers. By assigning different values to these parameters we obtain different systems of equations which may have different behaviours, for example, a different number of solutions. To make it more interesting, add the assumption that we are only interested in positive real solutions. This adds a set of simple inequalities to our initial system. The parameter values such that by crossing them, the behaviour of the system changes form a hypersurface called the discriminant variety. One can calculate this variety by the help of Gröbner basis. However, the next important task is to describe the regions in the complement of this variety where the system has a specific behaviour. This part and more can be handled by CAD. In this talk we first review the concept of CAD, and then showcase its power in solving different questions from applications, from finding multistationarity regions of a chemical reaction network to finding different types of bifurcations in population dynamics. While Gröbner basis is for equations only, CAD can handle inequalities as well. It sounds like a Swiss army knife that can be used for solving several types of questions. But its worst-case doubly exponential complexity makes it too heavy to carry it around as a practical handy tool. Thus there are a variety of attempts to reduce its complexity.

Real root classification and quantifier elimination arise in many applications of computing and engineering sciences. Most of algorithms from the state of the art suffer from a complexity which is doubly exponential in the number of involved parameters (if not the number of all indeterminates). In this talk, I will present some new algorithms which run in time which is singly exponential in both the number of variables to eliminate and the number of parameters. A preliminary implementation shows that its practical behaviour reflects the complexity gain.

Subtropical real root finding is a heuristic method designed to solve large multivariate polynomials. This method considers the polynomial as a collection of exponent vectors associated with sign information on the coefficients. It employs linear programming to heuristically identify points where the values of the polynomial have opposite signs. In successful cases, the intermediate value theorem is utilized to compute a zero of the polynomial represented as a tuple of real algebraic numbers. By implementing this approach using the Reduce computer algebra system and the Gurobi LP solver, we have achieved success in solving hundreds of problems derived from established mathematical models in chemistry and systems biology. These problems involved polynomials with up to 800,000 monomials in 10 variables and degrees up to 12, with an incompleteness failure rate of approximately 10 percent. The method has been adapted to satisfiability modulo theories solving (SMT), where the focus went from one single polynomial equation to several simulteneous strict polynomial inequalities, where SMT itself can be used in place of LP solving. Systematic experiments on the SMT-LIB have shown that the method is not a sufficiently strong decision procedure by itself but a valuable heuristic to use within a portfolio of techniques. The talk gives an overview of the method and its application, along with theoretical results regarding its incompleteness.

Chemical reaction networks can be represented by a system of polynomial ODEs involving many parameters. Numerical algebraic geometry can be used to solve these polynomial systems for their steady state solutions, specifically the positive steady states. Finding these solutions has an impact on certain properties such as mutistationarity, where there are two or more possible steady states. This talk will use a model of the extracellular signal-regulated kinase (ERK) network to showcase methods to sample the discriminant locus and analyze the parameter space to investigate the maximum number of positive real solutions. I will also discuss challenges and next steps to this process.

Polynomial systems that arise in applications often have fixed support, with coefficients that depend on unknown parameters, and a common theme in applied algebraic geometry is to understand how the geometry of the solution set varies with the value of the parameters. A particularly well-studied setting is when all coefficients vary freely and independently from each other, but in many practical applications, there are algebraic dependencies between the coefficients. In this talk, I’ll discuss a particular class of systems with this property, which we call vertically parametrized systems, where there are linear dependencies between coefficients of terms with the same monomial. Such systems arise naturally from for example chemical reaction network theory and optimization. I’ll give an overview of various results concerning geometric properties of the positive solution sets of vertically parametrized systems, such as dimension, smoothness and toricity, and show examples of how this plays a role in the study of robustness and multistationarity in reaction network theory. This is based on joint works with Elisenda Feliu and Beatriz Pascual-Escudero.

The condition number of a real polynomial system measures how sensitive the zero set is to perturbations of the systems. In this way, the condition number plays a fundamental in the analysis and development of numerical algorithms in algebraic geometry, being a fundamental invariant that controls many geometric features of the zero set. In this talk, we show a new family of bounds of the number of real zeros in terms of the condition number. We further discuss some of the algorithmic and probabilistic consequences of these new bounds and the under. This is joint work with Elias Tsigaridas.

Optional event. Coming soon!

Studying the homology groups of semi-algebraic subsets of $\mathbb{R}^n$ and obtaining upper bounds on the Betti numbers has been a classical topic in real algebraic geometry beginning with the work of Petrovskii and Oleinik, Thom, and Milnor. In this talk I will consider semi-algebraic subsets of $\mathbb{R}^n$ which are defined by symmetric polynomials and are thus stable under the standard action on $\mathbb{R}^n$ of the symmetric group $\mathfrak{S}_n$. The homology groups (with rational coefficients) of such sets thus acquire extra structure as $\mathfrak{S}_n$-modules leading to possible refinements on the classical bounds. I will also mention some algorithmic consequences and connections with a homological stability conjecture.

We describe an algorithm to compute Whitney stratifications of real algebraic varieties, and of polynomial maps between them, by exploiting the algebraic structure of certain conormal spaces. One of the map stratification algorithms described here yields a new method for solving the real root classification problem, which arises when studying multistationarity in the theory of chemical reaction networks, among other applications. We also explore applications of this new map stratification algorithm to the study of the singularities of Feynman integrals; understanding and evaluating these integrals is a fundamental component in a wide variety of problems arising in quantum field theory.

From Khovanskii's results, we know that some complexity of the topology of the real part of a variety defined by a system of real polynomials can be bounded (independently of the degrees) by the number of the monomials of the system. This raises the question of which are the optimal bounds, already in the case of a hypersurface. We will see that the number of connected components of a smooth hypersurface in the positive orthant of R^n defined by a real polynomial with d+k+1 monomials, where d is the dimension of the affine span of the exponent vectors, is smaller than d2^{O(k^2)}, improving the previously known bounds. We can even refine this bound for k=2 by showing that a smooth hypersurface defined by a real polynomial with d+3 monomials in n variables has at most (d+5)/2 connected components in the positive orthant of R^n. Moreover, this bound is sharp for d=2 (and any n). This is joint work with Frédéric Bihan and Tristan Humbert.

This talk focuses on systems of real polynomial equations in two variables, whose monomials give rise to exactly five distinct exponent vectors. It is known that such a system cannot have more than fifteen solutions in the positive orthant of the real plane. I will summarize the state of the art regarding the general problem of constructing sparse polynomial systems with many positive solutions. I will then present a construction of a system as above having seven positive solutions. This forms the best construction yet, and it uses tools developed in tropical geometry.

In this talk, we will discuss a method based on real tropical geometry that provides lower bounds on the maximal number of positive real solutions of a parametrized polynomial equation system. The method is designed for equation systems that arise from biochemical reaction networks, where positive solutions correspond to the steady states of the model. We will compare this tropical approach to existing polyhedral methods, such as Viro's patchworking. Furthermore, we will discuss how to compute such tropical lower bounds using Polymake. The talk is based on joint work in progress with Kemal Rose.

Restaurant: Carmen de la Victoria Cost: 40 euros per participant (Important: this is not covered by the organization).

Under mass-action kinetics, biochemical reaction networks induce a polynomial autonomous system of differential equations. Such a system is said to have absolute concentration robustness (ACR) in the species Xi if the value of the i-th coordinate is constant in the positive steady state locus. It is of interest to determine (quickly) whether a given biochemical system has ACR in some species. We revisit some (known) approaches to this problem that are incomplete and propose some new methods for deciding ACR, which harness computational algebra. This is joint work with Luis D. García Puente (Colorado College), Elizabeth Gross (University of Hawai‘i at Manoa), Heather A. Harrington (University of Oxford and Max Planck Institute of Molecular Cell Biology and Genetics and Technische Universität Dresden), Matthew Johnston (Lawrence Technological University), Nicolette Meshkat (Santa Clara University) and Anne Shiu (Texas A&M University).

The multistability problem of biochemical reaction systems is crucial for understanding basic phenomena such as decision-making process in cellular signaling. Mathematically, it is a challenging real quantifier elimination problem. We present some recent progress on multistability of small reaction networks. 1) For reaction networks with two reactions (possibly reversible), we find the multistable network those have the minimum numbers of reactants and species. 2) For reaction networks with one-dimensional stoichiometric subspaces, we give the relation between the maximum numbers of stable steady states and steady states. 3）For bi-reaction networks, we completely characterize the bi-reaction networks that admit multistability.

In this talk, I will present an approach for counting zeros of polynomial systems, where each polynomial is a general linear combination of fixed, prescribed polynomials. Our tools primarily rely on the theory of Khovanskii bases. I will demonstrate the application of this approach to the problem of counting the number of approximate stationary states for coupled Duffing oscillators. We have derived a Khovanskii basis for the corresponding polynomial system and determined the number of its complex solutions for an arbitrary degree of nonlinearity in the Duffing equation and an arbitrary number of oscillators. This is joint work with Viktoriia Borovik, Mateusz Michalek, Leonid Monin, Javier del Pino, Simon Telen and Oded Zilberberg.

In reaction networks, the existence of multistationarity is a precursor to multistability which has been linked to cellular-decision making processes. On the other hand, ACR is robustness of concentration of a species at steady states. While both these are important network properties, their coexistence is rare. I will discuss the coexistence in relation to the network structures and present minimal conditions necessary for coexistence.

Finding algebraic invariants to describe the methods that we use to perform elimination is a very interesting topic in applied algebra. If the computations rely on an object which is intrinsic to the algebra of the polynomial system (and not too attached to the extra elements that we use to compute), then the complexity of these computations is governed by that invariant. In this context, an interesting case of study is the relation between the widely used Gröbner bases and the Castelnuovo-Mumford regularity. One of the most important results in this direction is due to Bayer and Stillman who showed that if we consider the maximal degree of an element of the Gröbner basis as a measure of its complexity then (up to using generic coordinates and the degree reverse lexicographic monomial order), this degree coincides with the Castelnuovo- Mumford regularity. In this talk, I will explain this relation by showing all the power of the Castelnuovo-Mumford regularity and its importance in computational algebra. However, the unbeatable doubly exponential bounds for the regularity force us to find further structure to exploit in the polynomial systems. A standard case of interest are multihomogeneous or sparse polynomial systems. In the rest of the talk, I will introduce the existing definitions and results for the multigraded Castelnuovo-Mumford regularity, and show how we can relate it to the multi-degrees in a multihomogeneous Gröbner basis, by introducing novel and interesting descriptions. This talk is based on joint work with Laurent Busé, Matías Bender and Elias Tsigaridas.

Nash equilibria in finite N-player games can be characterized as the nonnegative solutions of structured systems of real polynomial equations and inequalities. The equations are multilinear, yet fundamental questions on the maximum number of Nash equilibria are still open even for two players. In semidefinite games, which can be seen as a subclass of more general families of quantum games, the strategy spaces are given by slices of the positive semidefinite cone. In the talk, we develop the transition from finite games to semidefinite games and present bounds on the maximal number of connected components of Nash equilibria in semidefinite games. Based on joint works with Constantin Ickstadt, Elias Tsigaridas and Antonios Varvitsiotis.

We consider parametrized systems of generalized polynomial equations for positive variables, involving a positive parameter for each monomial. Our framework encompasses systems of generalized polynomial equations, as studied in fewnomial and reaction network theory. It turns out that the relevant geometric objects of the problem are a bounded set arising from the coefficients and two subspaces representing monomial differences and dependencies. The dimension of the latter subspace (the monomial dependency 'd') is crucial. In our framework, which is based on linear algebra and convex geometry, we rewrite the problem in terms of 'd' binomial equations on the coefficient set, involving 'd' monomials in the positive parameters. We illustrate our approach with applications to fewnomial theory and reaction networks.

Solving the steady-state equations of a polynomial dynamical system is a recurring task throughout applied mathematics. One such task of particular impact is solving the power flow equations, a system of quadratic equations which model the nonlinear relationship between voltage magnitudes and power injections in an electric power network. Real solutions to the power flow equations give operating points for an electric power network. Traditionally, a single operating point is found using Newton’s method, but there is little theory to support that this solution is the best, or even a good choice. This talk will survey the history of the power flow problem and outline heuristics used in practice as well as optimization techniques that have been popularized via competitions like the ARPA-E GO competition. We will then turn to recent work which extends the applicability of globally convergent methods for solving power flow systems using techniques like monodromy and parameter continuation. Much of this work relies on recent results characterizing the combinatorial geometry associated to the power flow equations for families of networks. We will conclude by discussing practical considerations when solving the power flow equations as well as variations often important for practical grid operation.

The study of fragile economic systems is important in identifying systems that are vulnerable to a dramatic collapse. For instance, complex systems like supply chains are at risk of being fragile because they require many parts to work well simultaneously. Even when each individual firm has a small susceptibility to a shock, the global system may still be at great risk. A recent survey by Matthew Elliot and Ben Golub review fragile economic systems from the point of view of networks. In a network, the reliability that the final product (e.g., a car, computer, or life saving medication) is made is determined by the probabilities of shocks being in the system. Thus, the reliability can transition from zero to a positive probability depending on the chances of a shock. Characterizing these phase transitions is an important problem in the theory of economic fragility. In our work, we view these phase transitions through the algebraic geometry lens by using resultants. As a result, we bring new tools to econometrics to analyze multi-parameter models, and we fully describe the reliability of several new network models using computational algebraic geometry. Our most significant application is a surprising case study on a mixture of two multi-parameter supply chain models.

The Structure-from-Motion pipeline in Computer vision aims to create a 3D model of an object or scene appearing in multiple pictures. Within this pipeline, multiple algebraic objects model the cameras, the features to reconstruct, and the triangulation process. In this talk, I will give an overview of one problem where finding nonnegative solutions of polynomials allows for a meaningful 3D reconstruction: the Perspective-n-Point (PnP) problem. The goal in the PnP problem is to determine the position and orientation of a camera given its intrinsic parameters and a set of $n$ 2D-to-3D correspondences. When the focal length of the cameras is unknown, this problem can be solved by finding positive solutions of a polynomial system given that the focal length must be positive. We will focus on the cases $n=3$ and $n=4$ where solvers have already been developed by the Algebraic Vision community. The main reference for this talk will be the paper A general solution to the P4P problem for camera with unknown focal length by Bujnak, Kukelova and Pajdla.

Phylogenetics is the study of the evolutionary history of species on our planet. This history is often represented by phylogenetic trees or networks, where the leaves represent current species and interior nodes symbolize their ancestors. This study is based on genomic data and has applications in determining pathogen origins, shaping biodiversity conservation strategies, and aiding in cancer cell traceability, among other fields. It is common to model nucleotide substitution in a phylogenetic tree using a Markov process. These processes can be viewed as polynomial applications in terms of the substitution parameters and the study of these polynomials and the geometry of the algebraic varieties that arise from them can be used to reconstruct phylogenetic trees. However, not all points of these algebraic varieties make biological sense. In this talk, we will discuss the importance of studying the subsets of positive parameters and biologically meaningful points in the varieties and explore how restricting to these subsets can provide insight into phylogenetic reconstruction.