LIP6 CNRS Sorbonne Université
Direct Link LIP6 » Actualité » Doctorants

VU Thi Xuan

Docteur
Équipe : PolSys
Date de départ : 09/12/2020

Direction de recherche : Mohab SAFEY EL DIN

Co-encadrement : 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.

Soutenance : 09/12/2020 - 10h - Zoom - https://us02web.zoom.us/j/85767929978?pwd=cmFvcWdyZGZhVkJiRndwU05DYnptUT09

Membres du jury :

M. BUSE Laurent (Inria Sophia Antipolis) [Rapporteur]
M. RIENER Cordian (Arctic University of Norway) [Rapporteur]
M. GRAILLAT Stef (Sorbonne Université, LIP6, PEQUAN)
M. SPAENLEHAUER Pierre-Jean (INRIA Nancy)
Mme. ZHI Lihong (University of Chinese Academy of Sciences)
M. FAUGERE Jean-Charles (LIP6 / Inria)
Arne Storjohann (University of Waterloo)
Stephen Vavasis (University of Waterloo)

Publications 2020

 Mentions légales
Carte du site |