logo EDITE Sujets de doctorat

Sparse Grobner Bases and Applications

Sujet proposé par
Directeur de thèse:
Doctorant: Matias Rafael BENDER
Unité de recherche UMR 7606 Laboratoire d'informatique de Paris 6

Domaine: Sciences et technologies de l'information et de la communication

Projet

Grobner bases were introduced by Bruno Buchberger in 1965 . Ten years ago, \\'e have opened a new area for efficient Grabner basis computations by proposing algorithms F.+/ Fs relying on linear algebra. Nevertheless, no general algorithm, however powerful, can take advantage of the specific nature of its input. However, problems coming from applications are not random but have an additional structure. For instance, polynomial systems can be invariant by the action of some finite groups, multi-linear (each equation is linear w.r.t. to one block of variables) or more generally multihomogeneous. For each particular structure, we were able to identify large classes of problems whose theoretical and practical complexity could be imprmed and to propose in each situation dedicated algorithms. These results turned out to be a key ingredient in recent breakthroughs in cryptography (for instance the discrete logarithm problem over finite fields). At first glance, multi-homogeneity, weighted homogeneity (quasi-homogeneity), overdeterminedness, sparseness and symmetries seem to be unrelated structures. Indeed, until recently we have obtained specific results for one type of structure: hence we obtain dedicated algorithm and sharp complexity results by reducing the problem of sol\'ing bilinear systems to determinantal ideals; 1Ye also propose adhoc techniques to handle symmetries. In order to ha\'e a uniform approach of these probles, ll'e introduce sparse Grabner bases, an analng of classical Gri.'>bner bases for semi group algebras, and 11·c propose sparse 1 arianls of the classical F4 / F_5 and FGLM algorithms to compute them. The PhD project will focus on the folloll'ing two directions. 2 Sparse Grobner bases We have proposed variants of F_5 and FGLM to solve symbolically systems whose support lie in the same support (unmixed systems); we ha\'e also obtained sharp complexity results when the monomials in the support are integer points in a lattice polytope. We want to im·estigate two new research directions. First, a possible extension of this work would be the generalization to mixed systems (where the algorithms and the complexity would depend on the Newton polytope of each of the polynomials of the system). Some results seem to indicate that such a generalization may be possible. Another restriction of the result, is that the complexity analysis (bounding the maximal degree occurring in the Grl'>bner basis computation) is for the moment restricted to the polytopal case. However, a classical question is to bound the number of solutions in the algebraic closure of a polynomial system where all polynomials hm e generic coefficients. When the exponent vectors of the monomials arc the points with integer coordinates in a lattice polytope, Kushnirenko 's theorem shows that the number of solutions is bounded by the normalized volume of the polytope. A natural question that arises is then to extend the work we have done in the polytopal case to the case where only a small subset of monomials appear in the equations (jewnomial systems). A noticeable result would be to compute a sparse Grabner basis of such a system in polynomial time when the number of monomials in the support is close to the number of variables. From an implementation point of view, we feel that implementing efficiently this new generation of algorithms in a general framework could be a new research area. Probably algorithms from com ex geometry or the combinatorial \\'Orld would be necessary components of an efficient implementation. Also , merging our existing approach (the so called sparse-Matrix F5) with a Buchberger's type approach 1 could lead to a termination criterion of the algorithm in the non-regular cases and for positive dimensional systems.

3 Algorithms for symmetric tensor decomposition - the real case

A symmetric tensor is a higher order generalization of a symmetric matrix. The decomposition of a symmetric tensor consists into writing it using a minimal number, called symmetric rank, of linear combinations of symmetric outer products of vectors. This could be seen as a generalization of cigenrnluc decomposition of symmetric matrices to higher order symmetric tensors. When the rank is small there are algorithms for computing it efficiently. Howe\'er, neither their theoretical nor their practical performance is \\'ell understood . Every symmetric tensor is equivalent to a homogeneous polynomial, where the dimension of the tensor corresponds to the degree and its order corresponds to the numher of variables . Therefore , the problem of symmetric tensor decomposition is equivalent to write a homogeneous polynomial as a sum of power of linear forms . A first goal is to consider optimal algorithms for decomposing homogeneous polynomials in two variables . The current state-of-the-art consists of algorithms with arithmetic complexity O(d2), where d is the degree of the polynomial. We will target for algorithms with complexity O(d2 log"(d)) where c is a constant. The aforementioned algorithms decompose the tensor over the complex numbers A relevant question is to generalize the study to decompose symmetric tensors m·er the real numbers. We will also extend our study to decomposition algorithms over the real numbers. Such algorithms will strongly depend on real root isolation algorithms of uni,·ariate polynomial. Since real root isolation is of crucial impo11ance for the team in many applications, if time permits, we will also focus on these algorithms. We would like to mention that when the rank is big the problem of decomposition could be reduced to a highly structured polynomial system. We plan to exploit this structure and propose a new algorithm for the general problem of decomposing a symmetric tensor. This study of structured and 3 Algorithms for symmetric tensor decomposition - the real case A symmetric tensor is a higher order generalization of a symmetric matrix. The decomposition of a symmetric tensor consists into writing it using a minimal number, called symmetric rank, of linear combinations of symmetric outer products of vectors. This could be seen as a generalization of cigenrnluc decomposition of symmetric matrices to higher order symmetric tensors. When the rank is small there are algorithms for computing it efficiently. Howe\'er, neither their theoretical nor their practical performance is \\'ell understood . Every symmetric tensor is equivalent to a homogeneous polynomial, where the dimension of the tensor corresponds to the degree and its order corresponds to the number of variables . Therefore , the problem of symmetric tensor decomposition is equivalent to write a homogeneous polynomial as a sum of power of linear forms . A first goal is to consider optimal algorithms for decomposing homogeneous polynomials in two variables . The current state-of-the-art consists of algorithms with arithmetic complexity O(d2), where d is the degree of the polynomial. We will target for algorithms with complexity O(d2 log"(d)) where c is a constant. The aforementioned algorithms decompose the tensor over the complex numbers A relevant question is to generalize the study to decompose symmetric tensors m·er the real numbers. We will also extend our study to decomposition algorithms over the real numbers. Such algorithms will strongly depend on real root isolation algorithms of univariate polynomial. Since real root isolation is of crucial importance for the team in many applications, if time permits, we will also focus on these algorithms. We would like to mention that when the rank is big the problem of decomposition could be reduced to a highly structured polynomial system. We plan to exploit this structure and propose a new algorithm for the general problem of decomposing a symmetric tensor. This study of structured and sparse

Enjeux

Another restriction of the result, is that the complexity analysis (bounding the maximal degree occurring in the Globner basis computation) is for the moment restricted to the polytopal case. However, a classical question is to bound the number of solutions in the algebraic closure of a polynomial system where all polynomials hm e generic coefficients. When the exponent vectors of the monomials arc the points with integer coordinates in a lattice polytope, Kushnirenko 's theorem shows that the number of solutions is bounded by the normalized volume of the polytope. A natural question that arises is then to extend the work we have done in the polytopal case to the case where only a small subset of monomials appear in the equations (jewnomial systems). A noticeable result would be to compute a sparse Grobner basis of such a system in polynomial time when the number of monomials in the support is close to the number of variables. From an implementation point of view, we feel that implementing efficiently this new generation of algorithms in a general framework could be a new research area. Probably algorithms from com ex geometry or the combinatorial \\'Orld would be necessary components of an efficient implementation. Also , merging our existing approach (the so called sparse-Matrix F5) with a Buchberger's type approach 1 could lead to a termination criterion of the algorithm in the non-regular cases and for positive dimensional systems.