Supervision : Mohab SAFEY EL DIN

Co-supervision : M. Éric Schost (University of Waterloo), M. George Labahn (University of Waterloo)

Homotopy algorithms for solving structured determinantal systems

Multivariate polynomial systems arise in numerous applications with special structures. In particular, determinantal structures and invariant systems appear in a wide range of applications such as in polynomial optimization and related questions in real algebraic geometry. The goal of this thesis is to provide efficient algorithms to solve such structured systems.
In order to solve the first kind of systems, we design efficient algorithms by using symbolic homotopy continuation techniques. While the homotopy methods, in both numeric and symbolic contexts, are well-understood and widely used in polynomial system solving for square systems, the use of these methods to solve over-determined systems is not so clear.
Meanwhile, determinantal systems are over-determined with more equations than unknowns. We provide probabilistic homotopy algorithms which take advantage of the determinantal structure to compute isolated points in the zero-sets of determinantal systems. The runtimes of our algorithms are polynomial in the sum of the multiplicities of the isolated points and the degree of the homotopy curve. We also give the bounds on the number of isolated points that we have to compute in three contexts: all entries of the input are in classical polynomial rings, all these polynomials are sparse, and they are weighted polynomials.
In addition, we deal with the problem of finding critical points of a symmetric polynomial map on an invariant algebraic set. We exploit the invariance properties of the input to split the solution space according to the orbits of the symmetric group. This allows us to design an algorithm which gives a triangular description of the solution space and which runs in time polynomial in the number of points that we have to compute. Our results are illustrated by applications in studying real algebraic sets defined by invariant polynomial systems by means of the critical point method.

2020-2023 Publications

• 2023
  • J.‑Ch. Faugère, G. Labahn, M. Safey El Din, E. Schost, Th. Vu : “Computing critical points for invariant algebraic systems”, Journal of Symbolic Computation, vol. 116, pp. 365-399, (Elsevier) (2023)
• 2022
  • G. Labahn, V. Neiger, Th. Vu, W. Zhou : “Rank-Sensitive Computation of the Rank Profile of a Polynomial Matrix”, ISSAC 2022, Villeneuve-d'Ascq, France (2022)
• 2021
  • Jonathan D. Hauenstein, M. Safey El Din, E. Schost, Th. Vu : “Solving determinantal systems using homotopy techniques”, Journal of Symbolic Computation, vol. 104, pp. 754-804, (Elsevier) (2021)
  • G. Labahn, M. Safey El Din, E. Schost, Th. Vu : “Homotopy techniques for solving sparse column support determinantal polynomial systems”, Journal of Complexity, vol. 66, pp. 101557, (Elsevier) (2021)
• 2020
  • Th. Vu : “Homotopy algorithms for solving structured determinantal systems”, thesis, phd defence 12/09/2020, supervision Safey el din, Mohab, co-supervision : M., Éric Schost (University of Waterloo), M., George Labahn (University of Waterloo) (2020)