Solving Polynomial Systems

Weekly Reading Seminars

 2023 


Welcome to the Weekly Reading Seminars on Solving Polynomial Systems taking place on Thursdays 16:00-18:00 CET. 

Seminar room: B.02.18 (Maths building).

Organizers:  Fatemeh Mohammadi

                       Sebastian Seemann


Registration:

Please email Fatemeh if you are interested in attending the meeting or have any questions.


Overview:

The main aim of this reading group is to get familiar with systems of polynomial equations and methods (symbolic and numerical) for solving them. Our main motivation is to understand the theory up to the level so that we are equipped to use and possibly adapt it to applied problems. 


Schedule:


Introduction to polynomial systems: We introduce central notions of polynomial systems and give examples of polynomial systems from the pure and applied side. In particular, we discuss the usual fields involved and consider the univariate and the linear cases. Then, we consider examples such as the Fermat equations and systems coming from polynomial optimization. 


Number of solutions: With the purpose of developing numerical methods for solving polynomial systems, it is important to find theoretical upper bounds to their number of solutions. They will correspond to upper bounds to the number of iterations that the numerical methods will perform. In this talk, we will present three different results. First, we will see Bézout Theorem that provides an upper bound based on the degree of the polynomials appearing in the system. Second, we will see Kushnirenko Theorem which exploits the vanishing of the coefficients of some monomials. Finally, we will see Bernstein-Kushnirenko Theorem: it is a refinement of the previous result, and it is used in applications. To conclude we mention that the upper bounds that we will obtain are, in general, sharp (i.e., they give the exact number of solutions for a generic system in the family to whom the theorems apply).


Computational Methods - normal form method: We study computational methods to solve systems of polynomial equations. We restrict our attention to zero-dimensional systems without points of multiplicity two or higher. The central observation is, that the coordinates of the solutions of a system of polynomial equations are encoded in the eigenstructure of the multiplication endomorphisms of the coordinate ring of the solution set. As an example we use Macauley matrices to determine normal forms and discuss how Gröbner bases are used to determine normal forms in a more general setting.



Homotopy continuation: We give an overview of the homotopy continuation method for numerically solving polynomial systems. The ideas and tools employed for this technique are recalled and tested against concrete examples. We will explore both the limits and the advantages of continuously deformating polynomial systems, and we will point at its concrete applications. The computational examples presented are based on the HomotopyContinuation package of Julia.



Multiplication polynomials over finite local rings: We show that every point at infinity P of an elliptic curve defined over a local ring can be described solely in terms of its x coordinate, which can therefore be used to parametrize all its multiples nP. Furthermore we show that this parametrization can be expressed through rational polynomials in n of bounded degree and no constant term. We call these polynomials "Multiplicative Polynomials". We then exploit the properties of these polynomials to prescribe the group structure of a general elliptic curve defined over a wide class of rings, which was previously unknown.



Quadratization and convexification in polynomial binary optimization: I will give an overview of this paper. I will explain the generic solution approach for the problem of minimizing a polynomial in binary variables. The generic approach consists of three distinct phases, together with several possible variants of each phase. The first phase is mainly about how to decompose each monomial of the problem into pairs of submonomials, down to the initial variables. The decomposition is called a quadratiziation scheme. The second phase builds a quadratic reformulation of a polynomial in binary variables based on a given quadratization scheme. The resulting quadratic problem is usually non-convex and is difficult to solve. Therefore, in the third phase, I will show how to convexify non-convex quadratic problems. This leads to a convex quadratic problem, that can be solved using the branch-and-bound method.



Polyhedral homotopy: Homotopy continuation methods to solve polynomial systems of equations require constructing a start system whose solutions are easier to compute. The number of solutions of the start system needs to be at least the number of solutions of the target system, which is traditionally bounded by the Bezout theorem. The Bernstein bound gives a much tighter bound to the number of solutions of the target system. Applying this bound in the homotopy algorithm allows us to follow less paths and save a great amount of computations. In this talk I will give an overview of Section 3 of this paper, focusing on Bernstein’s bound and the polyhedral homotopy algorithm, with concrete examples using the HomotopyContinuation package of Julia. 



Numerical algebraic geometry:  Suppose we are given a system of polynomial equations whose solution set is not a finite set of points, but rather a positive-dimensional algebraic variety. What does it even mean to (numerically) solve such a system? One answer to this question is given by the notion of numerical irreducible decomposition, which consists of a so-called witness set for each irreducible component of our variety. In my talk I will introduce these concepts, and explain the cascade algorithm for computing a numerical irreducible decomposition, including a demonstration in HomotopyContinuation.jl. The talk will be about Section 4 of this paper.



Linear Convex Optimization with Gurobi: In this talk we will discuss the main topics regarding the formulation and the solution of Linear Convex Optimization (also know as Linear Programming) and Mixed Integer Linear Programming, with a focus on the computer software Gurobi. Specifically, we will discuss the simplex method, the concept of duality of an LP problem, and the Branch and Bound algorithm. Finally, we will see how to formulate and solve some well known problem, including the Knapsack Problem, the solution of a Sudoku and the Traveling Salesman Problem, as instances of MILP.



Certification:  The talk will be about Section 5 of this paper. In particular, we will talk about certification of numerically obtained solutions to systems of polynomial equations. For this we will also take a closer look at interval arithmetic, Smales' alpha theory, and Krawczyk´s method. 



A stratified polyhedral homotopy method: I will give an overview of this paper. In this talk, we mainly talk about how to numerically sample reduced irreducible components of all dimensions of the zero set of Laurent polynomial system using polyhedral homotopy continuation.



Efficient Computation of Macaulay Matrix Nullspaces Through Exploiting Shift-Invariant Structures: In this talk, we discuss the problem of efficiently computing the right-nullspace of the Macaulay matrix, which is a crucial step in many polynomial systems root-solving algorithms. For an overdetermined bivariate polynomial system Σ with S ≥ 2 equations of degree dσ the complexity of computing a nullspace containing all system roots is O(dσ6) using standard algorithms (e.g., SVD, rank-revealing QR). We however show that it is possible to reduce the complexity to O(dσ5) if one is willing to exploit the shift-invariant structures in the Macaulay matrix. By converting the Macaulay matrix into a Cauchy-like matrix using Fourier transforms, we devise an algorithm that efficiently determines the nullspace from a rank-revealing LU factorization using the celebrated Schur algorithm. Since the algorithm relies on Gaussian elimination to compute the nullspace, interesting parallels to Gröbner basis computations can be drawn. Details of the proposed method, including stability considerations, are covered in the talk. Also discussed are generalizations of the fast algorithm to polynomial systems expressed in the Chebyshev basis and the difficulties involved with extending the fast algorithm to general n-variable systems.



Computing with real algebraic curves: topology and connectivity properties: Real algebraic curves arise in many applications, such as computer aided geometric design, geometric modeling, or robotics. They are also topical objects in computational real algebraic geometry, and an example of a basic task is that of computing the topology of such curves, embedded in an ambient space of a prescribed dimension. Besides, using the notion of roadmap, one can reduce connectivity queries in real algebraic sets of arbitrary dimensions to such queries in real algebraic curves. In this talk, I will give an overview of the main approaches to efficiently tackling these problems on real algebraic curves, depending on the dimension of the ambient space containing them. This contains joint work with Md. Nazrul Islam and Adrien Poteaux.



Computational Semi-Algebraic Geometry for Differential Equations and Robotics: Computational semi-algebraic geometry is a field at the interface of mathematics and computer science that address the problem of solving geometric problems that can be phrased in terms of polynomial equations and inequalities with real coefficients. In this talk, I will present classical subroutines of this field through their use to solve challenging problems across applied mathematics, such as the stability of equilibra in ODEs and discretization schemes for PDEs. Once these subroutines are introduced, I will detail how to combine them for the identification of a certain class of manipulators, namely the so-called cuspidal robots. This talk contains joint work with Damien Chablat, Mohab Safey El Din, Durgesh Salunkhe, and Philippe Wenger.

Organizers:  Fatemeh Mohammadi

                       Sebastian Seemann