Workshop on Solving Polynomial Equations and Applications
CWI, Amsterdam
57 October, 2022
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 symbolicnumeric 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:3010:30 Simon Telen
10:3011:00 break
11:0012:00 Simon Telen
12:0013:30 Lunch
13:3014:30 Elisenda Feliu
14:3015:00 Break
15:0016:00 Matías R. Bender
16:0017:00 Discussions/problem session
17:0018:30 Reception
Thursday 6 October
09:3010:30 Paul Breiding
10:3011:00 Break
11:0012:00 Evelyne Hubert
12:0013:30 Lunch
13:3014:30 Wieb Bosma
14:3014:45 Break
14:4515:45 Mohab Safey El Din
15:4517:00 Poster presentations
Friday 7 October
09:3010:30 Rosa Winter
10:3011:00 Break
11:0012:00 Bernard Mourrain
12:0013:30 Lunch
13:3014:30 Cecília Salgado
14:3015:00 Break
15:0016:00 Bernd Sturmfels
Speakers and Lectures
The list of invited speakers includes (in alphabetic order):
 Matías R. Bender (TU Berlin)
Title: Symbolicnumeric methods to solve polynomial systems
Slides.
Abstract:
In this lecture, we will study symbolicnumeric 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 parameterdependent 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 KacRice 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, PascualEscudero 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 nonlinear 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: MordellWeil rank jumps on families of elliptic curves
Abstract:
We will discuss recent advances around the variation of the
MordellWeil 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: Fourdimensional 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 4dimensional 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 twopart 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 pnorms.
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 BuseChardinNemati. 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, rankrevealing 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 Toeplitzblock(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 Cauchylike 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 rankrevealing 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
BernsteinKushnirenkoKhovanskii 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 steadystate 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 NewtonOkounkov 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 graphtheoretic 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 cases3point absolute pose, 5point relative pose, and 4point homography estimation for calibrated cameraswhere 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 signaturebased 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 socalled signaturebased 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 idealtheoretic operations and that it enables us to work with polynomial systems that are out of reach of stateoftheart computer algebra systems. This is joint work with Christian Eder, Pierre Lairez and Mohab Safey ElDin.
 Hadrien Notarantonio (INRIA ParisSaclay)
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 guessandprove paradigm and the geometry induced by those polynomial systems.
 Rémi Prébet (École Normale Supérieure ParisSaclay)
Title: Answering connectivity queries in semialgebraic sets through roadmaps: an application to
robotics
Slides.
Abstract:
Roadmaps of semialgebraic sets have been introduced to reduce the problem of answering
connectivity queries in an arbitrary semialgebraic set to queries over semialgebraic curves.
In this poster, I will first present how to use roadmaps and classical subroutines of effective
semialgebraic geometry, such as computing one point in each connected component of a given
semialgebraic set to solve challenging problems in robotics, such as cuspidality decisions.
Then, I will focus on the computation of roadmaps by the socalled 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 realworld 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, MaxPlanck Institute Leipzig), Monique Laurent (CWI, Tilburg University)
If you have any questions please contact us (Simon.Telen at cwi.nl).
