Workshop on Solving Polynomial Equations and Applications

Polynomial equations are at the heart of many problems in pure and applied mathematics. They form a powerful tool for modelling nonlinear phenomena in the sciences. Application areas range from robotics, chemistry and computer vision to quantum physics and statistics. Recent progress has made it possible to reliably solve challenging polynomial equations arising in such practical contexts. This workshop will feature a friendly introduction to existing methods, presentations of the latest software tools and research talks by experts in the field. The focus will be on new trends and methodology, as well as applications in the sciences.

Presentation of the workshop

The workshop will start with a masterclass on solving polynomial equations, with a focus on homotopy methods, normal form methods, computer algebra methods, and symbolic-numeric algorithms. This will include introductory lectures and demos on how to use existing software tools. The presentations will be delivered by Matías R. Bender and Simon Telen on Wednesday 5 October, and by Wieb Bosma, Paul Breiding and Mohab Safey El Din on Thursday 6 October. These are the Lecture Notes accompanying the introductory lectures by Simon Telen.

This is combined with research talks by the other invited speakers, as listed below.

We encourage students and young researchers to participate and contribute a research poster. To submit a poster please send a title and abstract to Simon Telen (Simon.Telen at cwi.nl) by Friday 23 September.

You may download the program of the workshop here.

Registration

Participation is free, but registration is mandatory since the workshop has a limited capacity. Please register here (before 1 October 2022).

Program

Wednesday 5 October
09:30-10:30 Simon Telen
10:30-11:00 break
11:00-12:00 Simon Telen
12:00-13:30 Lunch
13:30-14:30 Elisenda Feliu
14:30-15:00 Break
15:00-16:00 Matías R. Bender
16:00-17:00 Discussions/problem session
17:00-18:30 Reception

Thursday 6 October
09:30-10:30 Paul Breiding
10:30-11:00 Break
11:00-12:00 Evelyne Hubert
12:00-13:30 Lunch
13:30-14:30 Wieb Bosma
14:30-14:45 Break
14:45-15:45 Mohab Safey El Din
15:45-17:00 Poster presentations

Friday 7 October
09:30-10:30 Rosa Winter
10:30-11:00 Break
11:00-12:00 Bernard Mourrain
12:00-13:30 Lunch
13:30-14:30 Cecília Salgado
14:30-15:00 Break
15:00-16:00 Bernd Sturmfels

Speakers and Lectures

The list of invited speakers includes (in alphabetic order):

- Matías R. Bender (TU Berlin)
Title: Symbolic-numeric methods to solve polynomial systems
Slides.
Abstract: In this lecture, we will study symbolic-numeric methods to solve system of polynomial equations. These algorithms use a symbolic preprocessing to linearize the problem and then they compute approximations of the solutions of the system by using numerical linear algebra. We will focus on how they perform such a linearization using Sylvester/Macaulay matrices and illustrate these algorithms using the Julia package EigenvalueSolver.jl.

- Wieb Bosma (Radboud Universiteit Nijmegen)
Title: Using computer algebra to solve polynomial systems
Slides.
Abstract: By examples from the development and use of the computer algebra system Magma, I will highlight some algorithms (and their problems) for solving polynomial systems symbolically. Among the issues I intend to discuss, besides large complexity, are those arising from the need to make algebraic extensions if the base field is not algebraically closed, the ambiguity in representing solutions and of interpreting them as complex numbers.

- Paul Breiding (Universität Osnabrück)
Title:Using homotopy continuation
Slides.
Abstract: My lecture is on polynomial homotopy continuation (PHC) and it consists of two parts. In the first part I will explain the theory that one needs to understand in order to effectively use PHC. In the second part I will show example applications.

- Elisenda Feliu (University of Copenhagen)
Title: Positive solutions to polynomial systems and reaction networks
Slides.
Abstract: In the context of (bio)chemical reaction networks, the dynamics of the concentrations of the chemical species over time are often modelled by a system of parameter-dependent ordinary differential equations, which are typically polynomial or described by rational functions. The study of the steady states of the system translates then into the study of the positive solutions to a parametric polynomial system.
In this talk I will start by presenting the formalism of the theory of reaction networks and the mathematical challenges faced. Afterwards I will focus on two specific recent works. First, I will present results to determine the generic dimension of the minimal algebraic variety containing all positive steady states (work in progress). Afterwards, I will discuss a numerical approach to approximate the parameter region where the system has more than one positive solution based on a Kac-Rice formula (https://doi.org/10.1090/mcom/3760). The latter property is termed multistationarity and is relevant in the context of the application.
The results I will present arise mainly from joint works with Henriksson, Pascual-Escudero and Sadeghimanesh.

- Evelyne Hubert (Inria Sophia Antipolis)
Title: Algorithms for fundamental invariants and equivariants
Slides.
Abstract: For a finite group, we present three algorithms to compute a generating set of invariant simultaneously to generating sets of basic equivariants, i.e., equivariants for the irreducible representations of the group. The main novelty resides in the exploitation of the orthogonal complement of the ideal generated by invariants; its symmetry adapted basis delivers the fundamental equivariants. Fundamental equivariants allow to assemble symmetry adapted bases of polynomial spaces of higher degrees, and these are essential ingredients in exploiting and preserving symmetry in computations. They appear within algebraic computation and beyond, in physics, chemistry and engineering.

- Bernard Mourrain (Inria Sophia Antipolis)
Title: Solving by duality
Slides.
Abstract: Finding the common roots of a set of polynomial equations is a problem that appears in many contexts and applications. Many standard approaches for solving this difficult question, such as Gröbner bases, border basis, triangular sets, etc. are based on polynomial reductions but their instability against numerical approximations can be critical. In this talk, we will describe the dual approach which focuses on linear functionals vanishing at the roots. We will review the properties of Truncated Normal Forms, the connection with classical computer algebra techniques and resultants. We will also detail the dual approach in the context of optimisation problems. Examples from geometric modeling, robotics and tensor decomposition will illustrate the numerical behavior of these dual methods.

- Mohab Safey El Din (Sorbonne University)
Title: Polynomial system solving with Gröbner bases and applications
Slides.
Abstract: Gröbner bases algorithms and computations are versatile tools for solving exactly non-linear algebraic equations. They can be used in a wide range of important and challenging applications ranging from e.g. information theory and security (coding theory, cryptology) -- where base fields are finite fields -- to applications in engineering sciences (biology, chemistry, robotics).
In this talk, we will recall basic definitions and properties of Gröbner bases, and explain how these properties can be used to solve polynomial systems (in a broad sense). Next, a few glimpse on algorithmic aspects, computational issues and implementation bottlenecks will be given. Topical applications in cryptography will be reviewed. Challenging applications in robotics, on which numerical methods tend to fail, will illustrate the potential of Gröbner bases for engineering sciences. Practical experiments and reports will use the C library msolve and its companion AlgebraicSolving.jl Julia package, authored by Berthomieu, Eder and Safey El Din.

- Cecília Salgado (Groningen University)
Title: Mordell-Weil rank jumps on families of elliptic curves

Abstract: We will discuss recent advances around the variation of the Mordell-Weil rank in families of elliptic curves. The first part of the talk will be dedicated to introducing the theme, motivating, presenting the state of the art and a brief view on the different techniques used to deal with the problem. The second part will cover results obtained in 3 different recent collaborations with Dan Loughran, Renato Dias and Hector Pasten, which deal with rank jumps on rational and K3 elliptic surfaces.

- Bernd Sturmfels (MPI Leipzig, UC Berkeley)
Title: Four-dimensional Lie algebras revisited
Slides.
Abstract: We discuss a system of 16 quadratic equations in 24 variables that arises in the study of Lie algebras. The solutions are the Lie algebra structures on a 4-dimensional vector space. There are four irreducible components of dimension 11. We compute their degrees and Hilbert polynomials, and thereby answer a 1999 question by Kirillov and Neretin. This is joint work with Laurent Manivel and Svala Sverrisdottir.

- Simon Telen (CWI, Amsterdam)
Title: Solving polynomial equations and applications
Slides.
Abstract: This two-part lecture serves as an introduction to the main topics of this workshop. I will introduce systems of polynomial equations and the main approaches for solving them. I will also discuss applications and solution counts. The theory is illustrated by many examples. The lecture is based on these notes.

- Rosa Winter (King's College London)
Title: Recovery from power sums
Slides.
Abstract: In this talk I will speak about joint work with Hana Melánová and Bernd Sturmfels, in which we study the problem of recovering a collection of n numbers from the evaluation of m power sums. The polynomial system that we obtain corresponds to intersecting Fermat hypersurfaces, and it can be underconstrained (m < n), square (m = n), or overconstrained (m > n). Questions that we ask are for example, when is recovery possible? If it is possible, is it unique? If it is not unique, can we give an upper bound for the number of solutions? We look at these questions in complex, real, and real positive settings. I will show results and conjectures involving deviations from the Bézout bound, and the recovery of vectors from length measurements by p-norms.

Poster presentations

The list of poster presentations includes (in alphabetic order):

- Antoine Bereau (École Polytechnique and Inria)
Title: The Nullstellensatz for sparse tropical polynomial systems
Poster.
Abstract: Grigoriev and Podolskii have established in 2018 a tropical analog of the effective Nullstellensatz, showing that a system of tropical polynomial equations is solvable if and only if a linearized system obtained from a Macaulay matrix truncated up to some degree N is solvable. Their result provides an explicit value of N as a function of the number of variables and of the degrees of the input polynomials. This value is higher than the its classical analog, and in fact the question of the optimal truncation degree was left open. We provide a new proof of the tropical Nullstellensatz leading to a smaller value of N . We recover in particular the classical Macaulay degree bound for square homogeneous systems. Our approach is inspired by a construction of Canny - Emiris (1993) for sparse polynomial systems, refined by Sturmfels (1994). It leads to new truncation methods adapted to sparse tropical systems. This is joint work with Marianne Akian and Stéphane Gaubert.

- Carles Checa (NKUA, Athens and Athena RC)
Title: Toric Sylvester forms and applications
Poster.
Abstract: The elimination of variables from a system of homogeneous polynomials is deeply connected to the saturation of ideals with respect to a certain geometrically irrelevant ideal. Thus, the search and study of universal generators of the saturation of an ideal generated by generic homogeneous polynomials, such as Jacobian determinants, is an important topic in elimination theory. We investigate this question in the general setting of homogeneous polynomials in the Cox ring of a projective toric variety $X_{\Sigma}$. As our main results, we establish a duality property and then we make it explicit by introducing toric Sylvester forms, under a certain positivity assumption on $X_{\Sigma}$. In particular, we prove that toric Sylvester forms yield a basis of the graded piece at $\alpha \in \text{Pic}(X_{\Sigma})$ of $I^{\text{sat}}/I$, where $I$ denotes an ideal generated by $n+1$ generic forms, $n$ is the dimension of $X_{\Sigma}$ and $I^{\text{sat}}$ the saturation of $I$ with respect to the irrelevant ideal of the Cox ring of $X_{\Sigma}$. These results generalize classical results of Jouanolou in the case where $X_{\Sigma}$ is a projective space, as well as their recent extension to the case of a product of projective spaces by Buse-Chardin-Nemati. Then, to illustrate the relevance of toric Sylvester forms we provide some consequences in elimination theory. First, we define hybrid elimination matrices by incorporating toric Sylvester forms in the classical Macaulay matrices; more generally, from the classical Koszul complex we obtain a new complex whose determinant of some of its graded pieces is proved to be equal to the toric resultant. Second, we extend the construction of hybrid elimination matrices to the case of overdetermined polynomial systems, providing this way a new family of matrices that can be used for solving such polynomial systems by means of linear algebra methods. Finally, we show that one can take advantage of toric Sylvester forms for computing toric residues of product of forms; this is a generalization of a formula due to Jouanolou in the case $X_{\Sigma}$ is a projective space.

- Nick Dewaele (KU Leuven)
Title: Sensitivity of roots of underdetermined systems

Abstract: When a polynomial system has simple roots, the condition number measures the sensitivity of the solutions to perturbations of the coefficients of the polynomial. However, many systems found in applications are overparameterised. That is, for every solution, there exists a family of equivalent solutions to the same system. In this case, the classic theory of condition is not meaningful because the condition number is always infinite. This poster presents an alternative condition number that quantifies the distance from a fixed solution of the system to the family of solutions of a perturbed system.

- Nithin Govindarajan (KU Leuven)
Title: A fast algorithm for computing Macaulay nullspaces of bivariate polynomial systems
Poster.
Abstract: As a crucial first step towards finding the (approximate) common roots of an (overdetermined) bivariate polynomial system of equations Σ, the problem of determining an explicit numerical basis for the right nullspace of the system's Macaulay matrix is considered. If the integer d_Σ denotes the total degree of the S (> 2) bivariate polynomials in the system, the cost of computing a nullspace basis containing all system roots involves O(S^2(d_Σ)^6) floating point operations using standard numerical algebra techniques (e.g., a singular value decomposition, rank-revealing QR). We show that it is actually possible to design an algorithm that reduces the complexity to O((d_Σ)^5).
The proposed algorithm exploits the almost Toeplitz-block-(block-) Toeplitz structure of the Macaulay matrix under a carefully chosen indexing of its entries and uses displacement rank theory to efficiently convert them into Cauchy-like matrices with the help of fast Fourier transforms. By modifying the classical total pivoting Schur algorithm for Cauchy matrices, a compact representation of the right nullspace is eventually found from a rank-revealing LU factorization.

- Paul Helminck (Durham University)
Title: Generic root counts of polynomial systems using tropical geometry
Slides.
Abstract: We present a general technique using tropical geometry to obtain generic root counts of parametrized polynomial systems, which improves the root counts obtained from the Bernstein-Kushnirenko-Khovanskii Theorem. This allows us to express the root count of a wide class of square systems as the matroidal degree of an explicit variety. This class includes the steady-state equations of chemical reaction networks, where the key factor that determines the root count is a certain matroid. It also includes the birational intersection indices defined by Kaveh and Khovanskii when the ambient variety is a torus. For the latter, we find that we can calculate volumes of Newton-Okounkov bodies in terms of the McMullen's polytope algebra.

- Oskar Henriksson (University of Copenhagen)
Title: Parametric toricity in the positive orthant for steady state varieties
Slides.
Abstract: Monomial parametrizability (also called toricity) of the solution set of a system of polynomial equations plays an important role in many applications. For instance, in reaction network theory, checking whether a given network has various chemical properties such as multistationarity simplifies greatly under the assumption of toricity of the set of steady states, provided that the exponents (but not necessarily the coefficients) of the parametrization are known. Over the complex numbers, toricity in the above sense is well understood, and boils down to checking if the radical of the ideal generated by the equations is prime and binomial. In reaction network theory, the situation is complicated by the fact that only the positive real solutions of the steady state equations are relevant. In addition, one often wants to check toricity for all possible values of certain unknown parameters that appear in the polynomials. Previous work on this type of parametric positive toricity in reaction network theory has mainly focused on various sufficient algebraic and graph-theoretic conditions. In this work, we give new conditions for both detecting and precluding parametric positive toricity, that make use of the special structure that the steady state equations have, and invoke a wide array of concepts from computational algebra, including polyhedral geometry, homotopy continuation and injectivity of monomial maps restricted to linear subspaces. This is joint work with Elisenda Feliu.

- Viktor Korotynskiy (CTU, Prague)
Title: Galois/monodromy groups for decomposing minimal problems in 3D reconstruction
Slides.
Abstract: We consider Galois/monodromy groups arising in computer vision applications, with a view towards building more efficient polynomial solvers. The Galois/monodromy group allows us to decide when a given problem decomposes into algebraic subproblems, and whether or not it has any symmetries. Tools from numerical algebraic geometry and computational group theory allow us to apply this framework to classical and novel reconstruction problems. We consider three classical cases--3-point absolute pose, 5-point relative pose, and 4-point homography estimation for calibrated cameras--where the decomposition and symmetries may be naturally understood in terms of the Galois/monodromy group. We then show how our framework can be applied to novel problems from absolute and relative pose estimation. For instance, we discover new symmetries for absolute pose problems involving mixtures of point and line features. We also describe a problem of estimating a pair of calibrated homographies between three images. For this problem of degree 64, we can reduce the degree to 16; the latter better reflecting the intrinsic difficulty of algebraically solving the problem.

- Mate Laszlo Telek (University of Copenhagen)
Title: Reaction networks and a generalization of Descartes' rule of signs to hypersurfaces
Poster.
Abstract: This poster presents recent work, where we provided upper bounds on the number of connected components of the complement of a hypersurface in the positive orthant and phrased our results as partial generalizations of the classical Descartes' rule of signs to multivariate polynomials (with real exponents). In particular, we gave conditions based on the geometrical configuration of the exponents and the sign of the coefficients that guarantee that the number of connected components of the complement of the hypersurface where the defining polynomial attains a negative value is at most one or two. These results helped us to answer problems arising from chemical reaction network theory that had been computationally infeasible by using other existing methods of real algebraic geometry.

- Rafael Mohr (CNRS, Paris)
Title: A signature-based Gröbner basis algorithm for computing the nondegenerate locus of a polynomial system

Abstract: We present an algorithm that, given a finite set of multivariate polynomials, computes an ideal representing the nondegenerate locus of the polynomial system, i.e. the closure of the set of points where the codimension of the variety cut out by the polynomial system matches the number of equations. This algorithm is the combination of an elementary algebraic procedure with a so-called signature-based Gröbner basis (sGB) algorithm. In contrast to many other symbolic algorithms we do not use Gröbner bases as a black box but modify the sGB algorithm itself to compute the ideal representing the nondegenerate locus. We show experimentally that this yields a massive reduction in the overhead induced by a "naive" version of the above mentioned algebraic procedure that uses Gröbner bases as a black box to perform ideal-theoretic operations and that it enables us to work with polynomial systems that are out of reach of state-of-the-art computer algebra systems. This is joint work with Christian Eder, Pierre Lairez and Mohab Safey El-Din.

- Hadrien Notarantonio (INRIA Paris-Saclay)
Title: Gröbner bases in the service of enumerative combinatorics
Poster.
Abstract: In enumerative combinatorics, many classes of objects (e.g., walks, maps) obey various sets of structural constraints (e.g., evolution domains, colorings). A common method to study and understand such classes is to first translate the structural constraints into a functional equation in one or several generating functions, and then to solve this equation: in our case the formal power series solution of this equation is algebraic (i.e. annihilated by a nonzero polynomial) and solving this equation means to exhibit such a polynomial. The state of the art for solving such an equation is to first translate it in terms of a parameterized polynomial system, and then to solve it by the use of elimination theory. This yields an intensive need of Gröbner bases computations in combinatorics. In my poster, I will present this area of research and show how one can solve those equations by using the state of the art in polynomial system solving, and by a more recent algorithm using the guess-and-prove paradigm and the geometry induced by those polynomial systems.

- Rémi Prébet (École Normale Supérieure Paris-Saclay)
Title: Answering connectivity queries in semi-algebraic sets through roadmaps: an application to robotics
Slides.
Abstract: Roadmaps of semi-algebraic sets have been introduced to reduce the problem of answering connectivity queries in an arbitrary semi-algebraic set to queries over semi-algebraic curves. In this poster, I will first present how to use roadmaps and classical subroutines of effective semi-algebraic geometry, such as computing one point in each connected component of a given semi-algebraic set to solve challenging problems in robotics, such as cuspidality decisions. Then, I will focus on the computation of roadmaps by the so-called roadmap algorithms and give an overview of the recent progress and our contributions to this point. Finally, we will see ongoing work on how to use roadmaps by analyzing the connectivity properties of algebraic curves. This talk gathers joint works with Damien Chablat, Mohab Safey El Din, Durgesh Salunkhe, Éric Schost and Philippe Wenger.

- Kemal Rose (MPI MiS Leipzig)
Title: Quadratically constrained polynomial optimisation in statistics
Poster.
Abstract: Partially observable Markov decision processes (POMDP's) form a broad framework, modelling various real-world decision processes that are based on partial information. We demonstrate how POMDP's fit into the framework of quadratically constrained polynomial optimisation and discuss objective value exactness of the SDP relaxation.

Location

Amsterdam Science Park Congress Center, Euler Room. Location next to the entrance of CWI.

Science Park 125, 1098 XG Amsterdam

CWI, Science Park 123, 1098 XG Amsterdam.

Accomodation

Interested participants may make a hotel reservation at Hotel Casa. Hotel Casa (Eerste Ringdijkstraat 4, Amsterdam) is conveniently located near Amstel train station and from there you can walk, cycle or take the bus to CWI.

Organizers

Simon Telen (CWI, Max-Planck Institute Leipzig), Monique Laurent (CWI, Tilburg University)

If you have any questions please contact us (Simon.Telen at cwi.nl).