BENDER Matias Rafael

PhD graduated
Team : PolSys
Departure date : 06/15/2019

Supervision : Jean-Charles FAUGÈRE

Co-supervision : TSIGARIDAS Elias

Algorithms for sparse polynomial systems : Gröbner bases and resultants

Polynomial system solving is one of the oldest and most important problems in computational mathematics and has many applications in computer science. It is an intrinsically hard problem with complexity at least single exponential in the number of variables. However, in most of the cases, the polynomial systems coming from applications have some kind of structure. In this thesis we focus on exploiting the structure related to the sparsity of the supports of the polynomials; that is, we take advantage of the fact that the polynomials only have a few monomials with non-zero coefficients. Our objective is to solve sparse systems faster than the worst case estimates that assume that all the terms are present. We develop algorithms for mixed sparse polynomial systems, that is, systems where the sparsity structure of the polynomials (Newton polytope) is different. We elaborate on two domains of elimination theory: sparse resultants and Gröbner bases. We work on each domain independently, but we also combine them to introduce new algorithms showing for the first time their relation in the sparse setting. We build on the multigraded Castelnuovo-Mumford regularity to develop this relation. We use resultants to propose "optimal" algorithms to solve families of mixed multilinear systems and, for a more general setting, we use Gröbner bases to solve sparse systems avoiding useless computations. The complexity of our algorithms depends on the sparsity structure of the systems (Newton polytopes). Finally, we introduce quasi-optimal algorithms to decompose binary forms.

Defence : 06/03/2019

Jury members :

M. Carlos D'Andrea, Professor Agregat, Universitat de Barcelona [Rapporteur]
Mme. Agnes Szanto (rapporteuse), Professor, North Carolina State University [Rapporteur]
M. Laurent Busé, Chargé de recherche, INRIA - Sophia Antipolis
M. Jean-Charles Faugère, Directeur de Recherche, INRIA - Paris
M. Stef Graillat, Professeur, Sorbonne Université
M. Bernard Mourrain, Directeur de Recherche, INRIA - Sophia Antipolis
M. Elias Tsigaridas, Chargé de recherche, INRIA - Paris
M. Gilles Villard, Directeur de recherche, CNRS - INS2I

Departure date : 06/15/2019

2016-2021 Publications