New below: Workshop preliminary program
How to come to IHP / Live stream
Special week
October 9 to 13, 2023
 Moment Method in Optimization (short course, Monday and Tuesday), D. Henrion
Lecture notes on the moment method
Location: Amphitheatre Darboux
Schedule Monday 10:0012:00 and Tuesday 10:0012:00
 Polynomials Systems and Real Geometry (long course, Tuesday to Friday), I. Emiris and D. Plaumann
Lecture notes on real algebraic geometry
Location: Amphitheatre Darboux
Schedule Tuesday 14:0017:30 and Wednesday 10:0012:00. Thursday 10:0012:00 and new: 14:0017:30 Friday 14:0017:00
 General audience presentation, Wednesday 11th, 16:0017:00, B. Sturmfels
Location: Amphitheatre Darboux
Title: The quadratic equation revisited.
Abstract High school students learn how to express the solution of a quadratic equation in one unknown in terms of its three coefficients. What does this this formula matter? We offer an answer in terms of discriminants and data. This lecture invites the audience to a journey towards nonlinear algebra.
Workshop: Geometry of Polynomial System Solving, Optimization and Topology
Organizers: C. D’Andrea, P. Lairez, M. Safey El Din, É. Schost, L. Zhi
October 16 to 20, 2023
Location: Amphitheatre Hermite
Polynomial systems encode a wide range of nonlinear (but static) phenomena which arise in many applications. Nonlinearity makes them nontrivial to handle, both from complexity and reliability viewpoints. Still, because of their importance for key applications e.g. in mechanism design and optimization amongst many others, various algorithmic approaches have been developed. During the last decades, tremendous achievements have been accomplished to design faster algorithms for polynomial system solving, extend their capabilities to tackle topological issues and understand their complexities. For instance, let us mention new families of algorithms to exploit algebraic and geometric properties of polynomial systems and their solution sets such as sparsity or weighted and multihomogeneity, algorithms for understanding the topology of semialgebraic sets (Betti numbers, connectivity queries), the raise of sumsofsquares certificates to certify emptiness over the reals of polynomial systems through symbolicnumeric approaches, and last but not least, qualitive advances in the line of Smale’s 17th problem.
Many challenges remain to be addressed to pave the way towards high performance polynomial system solvers tackling large scale applications. Topical issues lie in the combination of efficiency and certification, computing exact certificates of emptiness, understanding the geometry of polynomial systems and their solution sets to exploit better their properties algorithmically. This workshop will cover broadly all these topics.
Invited speakers
Christian Eder (Kaiserslautern, Germany) Recent advances in Gröbner basis algorithms and geometric applications
Abstract
The tasks of designing innovative mathematical software and of solving complex
research problems using computational methods are strongly mutually dependent.
Developing a new generation of algorithms to considerably push the
computational boundaries of nonlinear algebra, notably addressing polynomial
system solving, is thus envitable. One important task of this process is to no
longer use Gröbner bases only as a black box in higher level algorthms, but to
optimize their computation with the geometric context in mind. In this talk, we
will illustrate this idea by presenting a new algorithm for computing Gröbner
bases of saturated polynomial ideals. Moreover, we introduce msolve, an open
source software package build to provide this new generation of efficient and
optimized algorithms for the community.
The contents of this talk are based on joint work with Jérémy Berthomieu and
Mohab Safey El Din.
Elisenda Feliu (Copenhagen, Denmark) Positive solutions to polynomial systems and applications to reaction networks
Abstract
The main object of study in the (algebraic) theory of reaction networks is the solution se of a system of parametric polynomial equations in the positive orthant. This system consists of polynomials
with fixed support, the coefficients are linear in the parameters, but there might be some (proportionality) dependencies among the coefficients. The questions of interest concern properties of this system, and
of its intersection with a family of parallel linear subspaces of complementary dimension. In this case, of relevance is to determine the possible number of zeros the system has when the parameters vary.
In this talk I will introduce the framework and the families of polynomial systems under study in full generality, and having the reaction networks as the main application. I will proceed to discuss recent
results addressing the expected dimension of the solution sets and on how to decide whether the solution set admits a toric parametrization for all parameter values. The latter is relevant for the problem of
counting solutions, and this connection will also be explained in the talk.
Jon Hauenstein (Notre Dame, USA) Some advances in numerical algebraic geometry for computing real solutions
Abstract. Numerical algebraic geometry provides a collection of algorithms for computing and analyzing solution sets of polynomial systems. This talk will discuss new techniques that have been developed in numerical algebraic geometry for focusing on real solution sets of polynomial systems. Several applications of these techniques will be presented such as computing smooth points on algebraic sets, approximate synthesis of mechanisms, and path planning for output mode switching.
Martin Helmer (Raleigh, USA) Conormal Spaces and Whitney Stratifications
Abstract. We describe a new algorithm for computing Whitney stratifications of complex projective varieties. The main ingredients are (a) an algebraic criterion, due to Lê and Teissier, which reformulates Whitney regularity in terms of conormal spaces and maps, and (b) a new interpretation of this conormal criterion via ideal saturations, which can be practically implemented on a computer. We show that this algorithm improves upon the existing state of the art by several orders of magnitude, even for relatively small input varieties. This is joint work with Vidit Nanda (Oxford).
Teresa Krick (Buenos Aires, Argentina) Nonnegativity and rational sums of squares over zerodimensional varieties
Abstract In this work in progress with Lorenzo Baldi and Bernard Mourrain, we extend previous results on univariate rational sums of squares, obtained with Bernard and Agnes Szanto, to the case of a nonnegative rational polynomial on a basic zerodimensional semialgebraic set defined by rational polynomials.
Monique Laurent (Centrum Wiskunde & Informatica (CWI) Amsterdam, and Tilburg University, The Netherlands) Sums of squares approximations in polynomial optimization: performance analysis and degree bounds
Abstract Polynomial optimization deals with optimizing a polynomial function over a feasible region defined by polynomial inequalities, thus modeling a broad range of hard nonlinear nonconvex optimization problems. Hierarchies of tractable semidefinite relaxations have been introduced that are based on using sums of squares of polynomials as a ``proxy” for global nonnegativity. These hierarchies give bounds on the global minimum of the original problem with asymptotic convergence (under a minor compactness assumption). In this lecture we discuss recent results on the performance analysis of these hierarchies and related effective degree bounds for dedicated sums of squares representations of positive polynomials on some classes of compact semialgebraic sets (including the hypercube, the sphere or the ball).
Anton Leykin (Atlanta, USA) ugeneration: solving systems of polynomials equationbyequation
Abstract We develop a new method that improves the efficiency of equationbyequation homotopy continuation methods for solving polynomial systems. Our method is based on a novel geometric construction and reduces the total number of homotopy paths that must be numerically continued. These improvements may be applied to the basic algorithms of numerical algebraic geometry in the settings of both projective and multiprojective varieties. (This is joint work with T. Duff and J. I. Rodriguez.)
Zijia Li (Beijing, China) Polynomial Systems Arising in Paradoxical 6R Linkages
Abstract In this talk, we first provide a comprehensive definition of closed nlinkages and explain their mobility, typically denoted as n6. We then focus on the intriguing subset of closed nlinkages with a mobility higher than n6, known as paradoxical linkages. Based on the powerful tools of Bond Theory and the freezing technique, we present a thorough classification of nlinkages with a mobility of n4 or higher, incorporating revolute, prismatic, or helical joints. Additionally, we explicitly derive strong necessary conditions for nRlinkages with a mobility of n5. Utilizing these necessary conditions, we explore and discuss possible polynomial systems that arise in paradoxical 6R linkages.
Fatemeh Mohammadi (Leuven, Belgium) Polynomial systems arising in the formal verification of programs
Abstract. Multiple classical problems in the formal verification of programs such as reachability, termination, and templatebased synthesis can be reduced to solving polynomial systems of equations. In this talk, I will describe the primary objects and these connections. In particular, I will show how the algebraic and geometric techniques can be applied, enhancing the scalability and completeness for such problems.
Marc Moreno Maza (London, Canada) Modular algorithms for computing triangular decompositions of polynomial systems
[abstract](https://rtca2023.github.io/pages_Paris/files_m5/abstract_morenomaza.pdf)Chenqi Mou (Beijing, China) Chordal Graphs in Triangular Decomposition in TopDown Style
Abstract
In this talk, I will present the connections between chordal graphs from graph theory
and triangular decomposition in topdown style from symbolic computation, including the
underlying theories, algorithms, and applications in biology. Viewing triangular decomposition in
topdown style as polynomial generalization of Gaussian elimination, we show that all the
polynomial sets, including all the computed triangular sets, appearing in several typical
topdown algorithms for triangular decomposition have associated graphs which are subgraphs of
the chordal graph of the input polynomial set. These theoretical results can be interpreted as
“triangular decomposition in topdown style preserves chordality” and are further used to design
sparse triangular decomposition for polynomial sets which are sparse with respect to their
variables. Sparse triangular decomposition is shown to be more efficient than ordinary one
experimentally, and its application on computing equilibria of biological dynamic systems will
also be reported.
This talk is based on the joint work with Yang Bai, Jiahua Lai, and Wenwen Ju.
Bernard Mourrain (Inria, SophiaAntipolis) Solving by duality
Abstract. Finding the common roots of a set of polynomial equations is a problem that appears in many contexts and applications. Standard approaches for solving this difficult question, such as Grobner 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 a dual approach which focuses on linear functionals vanishing at the roots. We will review the properties of Truncated Normal Forms, the connexion with classical computer algebra approaches and resultants. We will also detail the dual approach in the context of optimisation problems and for analysing isolated singularities. Examples from geometric modeling, robotics and tensor decomposition will illustrate the numerical behavior of these dual methods.
Cordian Riener (Tromso, Norway) The geometry of the Vandermonde map at infinity
Abstract The Vandermonde map is the polynomial map given by the powersum polynomials. We study the geometry of the image of the nonnegative orthant under under this map and focus on the limit as the number of variables approaches infinity. We will show, the geometry of this limit is the key to new undecidability results in nonnegativity of symmetric polynomials and deciding validity of trace inequalities in linear algebra.
PierreJean Spaenlehauer (Nancy, France) Dimension results for sparse systems homogenized via rational polytopes
Abstract. A classical method to compute with sparse polynomials is to homogenize them with respect to Newton polytopes, regarding them as homogeneous elements of Cartier degrees in the Cox ring of a projective toric variety. In this talk, we investigate subvarieties defined by generic polynomial systems in the Cox ring when the degrees are nonnecessarily Cartier, with a view towards identifying alternative toric homogenizations that are suitable for practical computations. Joint work with Matías Bender.
Topical day: Mechanism Design and Computer Algebra
October 24, 2023
Organizer: J. Schicho
Location: Amphitheatre Darboux
Speakers. Maria AlberichCarraminana, Didier Henrion, HansPeter Schröcker, Josef Schicho
Schedule:
 9:3010:30 Galois Theory for Planar Mechanisms J. Schicho
Abstract.
Let $G$ be a graph with $n$ vertices and $e$ edges. The computation of the position of $n$ points in the plane such that for any two vertices in the graph connected by an edge, the distance between the two corresponding points is given, is equivalent to the inverse kinematic problem for a (highly parallel) planar mechanism with revolute joints. If the graph is a Laman graph, then the solution set is generically a finite set of orbits under the group of Euclidean displacements, and can be assigned a Galois group (which is associated to the field extension needed to express the solutions exactly). We explain some geometric ideas for analyzing the Galois group. Using these ideas, we determine the number of components of the solution set for graphs that have the property that the above position problem is generically solvable. 11:0012:00 Mechanisms from Motions – Rational and Algebraic H.P.
Schröcker
Abstract.
The factorization of rational motions has been introduced about a decade ago. On a kinematics level it corresponds to the decomposition of a rational motion into elementary motions (rotations, translations, ...) The mathematics behind is the factorization of special polynomials over noncommutative rings into linear factors. This talk gives an overview about the past decade of motion factorization and explains many of the underlying constructions of mechanisms at hand of animations. It will also feature a new geometric factorization algorithm that highlights the importance of “kinematics at infinity” and gives rise to an extension of the factorization theory from rational to algebraic motions.  14:0015:00 Inverse kinematics with computer algebra and the Lasserre hierarchy
D. Henrion
Abstract.
The Inverse Kinematics (IK) problem consists of finding robot control parameters to bring it into a desired position under kinematics and collision constraints. We describe a global solution to the optimal IK problem for a general serial manipulator with 7 degrees of freedom (7DOF) with revolute joints. Classical modeling yields a polynomial optimization problem with constraints of degree four. A direct application of the momentSOS (sums of squares) aka Lasserre hierarchy generates semidefinite optimization problems which are too large for stateoftheart numerical solvers. Using computer algebra (Groebner basis computations), we show that the kinematic constraints due to rotations can all be generated by degree two polynomials. On this reduced problem, we demonstrate that the second relaxation of the Lasserre hierarchy is sufficient to solve the 7DOF IK problem on a KUKA LBR IIWA manipulator and we show that we are able to compute the optimal IK or certify infeasibility in 99% of the tested poses. This is joint work with Pavel Trutman (Prague), Tomas Pajdla (Prague) and Mohab Safey El Din (Paris).  15:0016:00 Cloth State Representation Using a Derivative of the Gauss Linking Integral M. AlberichCarraminana
Abstract.
Robotic manipulation of cloth presents a complex challenge due to the infinitedimensional shapestate space of textiles. This complexity makes accurate state estimation a daunting task. To address this issue, we introduce the concept of dGLI Cloth Coordinates—a finite, lowdimensional representation of cloth states. This novel approach enables us to effectively distinguish among a wide range of folded states, paving the way for efficient learning methods in cloth manipulation planning and control.Preliminary Program of the workshop  All talks in Amphitheater Hermite
Monday October 16th, 2023  

8:45  Welcome coffee  
9:159:30  Opening


9:3010:30  PierreJean Spaenlehauer  Dimension results for sparse systems homogenized via rational polytopesAbstract. A classical method to compute with sparse polynomials is to homogenize them with respect to Newton polytopes, regarding them as homogeneous elements of Cartier degrees in the Cox ring of a projective toric variety. In this talk, we investigate subvarieties defined by generic polynomial systems in the Cox ring when the degrees are nonnecessarily Cartier, with a view towards identifying alternative toric homogenizations that are suitable for practical computations. Joint work with Matías Bender. 
10:3011:00  Coffee break  
11:0012:00  Chenqi Mou  Chordal Graphs in Triangular Decomposition in TopDown StyleAbstract. In this talk, I will present the connections between chordal graphs from graph theory and triangular decomposition in topdown style from symbolic computation, including the underlying theories, algorithms, and applications in biology. Viewing triangular decomposition in topdown style as polynomial generalization of Gaussian elimination, we show that all the polynomial sets, including all the computed triangular sets, appearing in several typical topdown algorithms for triangular decomposition have associated graphs which are subgraphs of the chordal graph of the input polynomial set. These theoretical results can be interpreted as “triangular decomposition in topdown style preserves chordality” and are further used to design sparse triangular decomposition for polynomial sets which are sparse with respect to their variables. Sparse triangular decomposition is shown to be more efficient than ordinary one experimentally, and its application on computing equilibria of biological dynamic systems will also be reported. This talk is based on the joint work with Yang Bai, Jiahua Lai, and Wenwen Ju. 
12:0014:30  Lunch break  
14:3015:30  Marc Moreno Maza  Modular algorithms for computing triangular decompositions of polynomial systemsabstract_morenomaza.pdf 
15:3016:00  Coffee break  
Tuesday October 17th, 2023  
9:3010:30  Fatemeh Mohammadi  Polynomial systems arising in the formal verification of programsAbstract. Multiple classical problems in the formal verification of programs such as reachability, termination, and templatebased synthesis can be reduced to solving polynomial systems of equations. In this talk, I will describe the primary objects and these connections. In particular, I will show how the algebraic and geometric techniques can be applied, enhancing the scalability and completeness for such problems. 
10:3011:00  Coffee break  
11:0012:00  Elisenda Feliu  Positive solutions to polynomial systems and applications to reaction networksAbstract. The main object of study in the (algebraic) theory of reaction networks is the solution se of a system of parametric polynomial equations in the positive orthant. This system consists of polynomials with fixed support, the coefficients are linear in the parameters, but there might be some (proportionality) dependencies among the coefficients. The questions of interest concern properties of this system, and of its intersection with a family of parallel linear subspaces of complementary dimension. In this case, of relevance is to determine the possible number of zeros the system has when the parameters vary. In this talk I will introduce the framework and the families of polynomial systems under study in full generality, and having the reaction networks as the main application. I will proceed to discuss recent results addressing the expected dimension of the solution sets and on how to decide whether the solution set admits a toric parametrization for all parameter values. The latter is relevant for the problem of counting solutions, and this connection will also be explained in the talk. 
12:0014:30  Lunch break  
14:3015:30  Zijia Li  Polynomial Systems Arising in Paradoxical 6R LinkagesAbstract. In this talk, we first provide a comprehensive definition of closed nlinkages and explain their mobility, typically denoted as n6. We then focus on the intriguing subset of closed nlinkages with a mobility higher than n6, known as paradoxical linkages. Based on the powerful tools of Bond Theory and the freezing technique, we present a thorough classification of nlinkages with a mobility of n4 or higher, incorporating revolute, prismatic, or helical joints. Additionally, we explicitly derive strong necessary conditions for nRlinkages with a mobility of n5. Utilizing these necessary conditions, we explore and discuss possible polynomial systems that arise in paradoxical 6R linkages. 
15:3016:00  Coffee  
Wednesday October 18th, 2023  
9:3010:30  Jon Hauenstein  Some advances in numerical algebraic geometry for computing real solutionsAbstract. Numerical algebraic geometry provides a collection of algorithms for computing and analyzing solution sets of polynomial systems. This talk will discuss new techniques that have been developed in numerical algebraic geometry for focusing on real solution sets of polynomial systems. Several applications of these techniques will be presented such as computing smooth points on algebraic sets, approximate synthesis of mechanisms, and path planning for output mode switching. 
10:3011:00  Coffee break  
11:0012:00  Anton Leykin  ugeneration: solving systems of polynomials equationbyequationAbstract. We develop a new method that improves the efficiency of equationbyequation homotopy continuation methods for solving polynomial systems. Our method is based on a novel geometric construction and reduces the total number of homotopy paths that must be numerically continued. These improvements may be applied to the basic algorithms of numerical algebraic geometry in the settings of both projective and multiprojective varieties. (This is joint work with T. Duff and J. I. Rodriguez.) 
Free afternoon  
18:30  Reception.  
Thursday October 19th, 2023  
9:3010:30  Monique Laurent  Sums of squares approximations in polynomial optimization: performance analysis and degree boundsAbstract. Polynomial optimization deals with optimizing a polynomial function over a feasible region defined by polynomial inequalities, thus modeling a broad range of hard nonlinear nonconvex optimization problems. Hierarchies of tractable semidefinite relaxations have been introduced that are based on using sums of squares of polynomials as a ``proxy” for global nonnegativity. These hierarchies give bounds on the global minimum of the original problem with asymptotic convergence (under a minor compactness assumption). In this lecture we discuss recent results on the performance analysis of these hierarchies and related effective degree bounds for dedicated sums of squares representations of positive polynomials on some classes of compact semialgebraic sets (including the hypercube, the sphere or the ball). 
10:3011:00  Coffee break  
11:0012:00  Bernard Mourrain  Solving by dualityAbstract. Finding the common roots of a set of polynomial equations is a problem that appears in many contexts and applications. Standard approaches for solving this difficult question, such as Grobner 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 a dual approach which focuses on linear functionals vanishing at the roots. We will review the properties of Truncated Normal Forms, the connexion with classical computer algebra approaches and resultants. We will also detail the dual approach in the context of optimisation problems and for analysing isolated singularities. Examples from geometric modeling, robotics and tensor decomposition will illustrate the numerical behavior of these dual methods. 
12:0014:30  Lunch break  
14:3015:30  Teresa Krick  Nonnegativity and rational sums of squares over zerodimensional varietiesAbstract. In this work in progress with Lorenzo Baldi and Bernard Mourrain, we extend previous results on univariate rational sums of squares, obtained with Bernard and Agnes Szanto, to the case of a nonnegative rational polynomial on a basic zerodimensional semialgebraic set defined by rational polynomials. 
15:3016:00  Coffee break  
16:0017:00  Martin Helmer  Conormal Spaces and Whitney StratificationsAbstract. We describe a new algorithm for computing Whitney stratifications of complex projective varieties. The main ingredients are (a) an algebraic criterion, due to Lê and Teissier, which reformulates Whitney regularity in terms of conormal spaces and maps, and (b) a new interpretation of this conormal criterion via ideal saturations, which can be practically implemented on a computer. We show that this algorithm improves upon the existing state of the art by several orders of magnitude, even for relatively small input varieties. This is joint work with Vidit Nanda (Oxford). 
Friday October 20th, 2023  
9:3010:30  Cordian Riener  The geometry of the Vandermonde map at infinityAbstract. The Vandermonde map is the polynomial map given by the powersum polynomials. We study the geometry of the image of the nonnegative orthant under under this map and focus on the limit as the number of variables approaches infinity. We will show, the geometry of this limit is the key to new undecidability results in nonnegativity of symmetric polynomials and deciding validity of trace inequalities in linear algebra. 
10:3011:00  Coffee break  
11:0012:00  Christian Eder  Recent advances in Gröbner basis algorithms and geometric applicationsAbstract. The tasks of designing innovative mathematical software and of solving complex research problems using computational methods are strongly mutually dependent. Developing a new generation of algorithms to considerably push the computational boundaries of nonlinear algebra, notably addressing polynomial system solving, is thus envitable. One important task of this process is to no longer use Gröbner bases only as a black box in higher level algorthms, but to optimize their computation with the geometric context in mind. In this talk, we will illustrate this idea by presenting a new algorithm for computing Gröbner bases of saturated polynomial ideals. Moreover, we introduce msolve, an open source software package build to provide this new generation of efficient and optimized algorithms for the community. The contents of this talk are based on joint work with Jérémy Berthomieu and Mohab Safey El Din. 
End of the workshop 