[tel-01110756] Solving multi-homogeneous and determinantal systems: algorithms, complexity, applications.

Multivariate polynomial systems arising in Engineering Science often carry algebraic structures related to the problems they stem from. In particular, multi-homogeneous, determinantal structures and boolean systems can be met in a wide range of applications. A classical method to solve polynomial systems is to compute a Gröbner basis of the ideal associated to the system. This thesis provides new tools for solving such structured systems in the context of Gröbner basis algorithms. On the one hand, these tools bring forth new bounds on the complexity of the computation of Gröbner bases of several families of structured systems (bilinear systems, determinantal systems, critical point systems, boolean systems). In particular, it allows the identification of families of systems for which the complexity of the computation is polynomial in the number of solutions. On the other hand, this thesis provides new algorithms which take profit of these algebraic structures for improving the efficiency of the Gröbner basis computation and of the whole solving process (multi-homogeneous systems, boolean systems). These results are illustrated by applications in cryptology (cryptanalysis of MinRank), in optimization and in effective real geometry (critical point systems).



from HAL : Dernières publications http://ift.tt/1yBGVSd