Description
Date depot: 1 janvier 1900
Titre: Sparse Grobner Bases and Applications
Directeur de thèse:
Jean-Charles FAUGÈRE (LIP6)
Domaine scientifique: Sciences et technologies de l'information et de la communication
Thématique CNRS : Non defini
Resumé:
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 complexit
Doctorant.e: Bender Matias Rafael