Bases de relations en une ou plusieurs variables : algorithmes rapides et applications

In this thesis, we study algorithms for a problem of finding relations in one or severalvariables. It generalizes that of computing a solution to a system of linear modularequations over a polynomial ring, including in particular the computation of Hermite-Padéapproximants and bivariate interpolants. Rather than a single solution, we aim atcomputing generators of the solution set which have good properties.Precisely, the input of our problem consists of a finite-dimensional module given bythe action of the variables on its elements, and of some elements of this module; the goalis to compute a Gröbner basis of the module of syzygies between these elements. In termsof linear algebra, the input describes a matrix with a type of Krylov structure, and thegoal is to compute a compact representation of a basis of the nullspace of this matrix.We propose several algorithms in accordance with the structure of the multiplicationmatrices which specify the action of the variables. In the case of a Jordan matrix, weaccelerate the computation of multivariate interpolants under degree constraints; ourresult for a Frobenius matrix leads to a faster algorithm for computing normal forms ofunivariate polynomial matrices. In the case of several dense matrices, we accelerate thechange of monomial order for Gröbner bases of multivariate zero-dimensional ideals.Dans cette thèse, nous étudions des algorithmes pour un problème de recherche de relationsà une ou plusieurs variables. Il généralise celui de calculer une solution à un systèmed’équations linéaires modulaires sur un anneau de polynômes, et inclut par exemple lecalcul d’approximants de Hermite-Padé ou d’interpolants bivariés. Plutôt qu’une seule solution,nous nous attacherons à calculer un ensemble de générateurs possédant de bonnespropriétés.Précisément, l’entrée de notre problème consiste en un module de dimension finiespécifié par l’action des variables sur ses éléments, et en un certain nombre d’élémentsde ce module ; il s’agit de calculer une base de Gröbner du module des relations entreces éléments. En termes d’algèbre linéaire, l’entrée décrit une matrice avec une structurede type Krylov, et il s’agit de calculer sous forme compacte une base du noyau de cettematrice.Nous proposons plusieurs algorithmes en fonction de la forme des matrices de multiplicationqui représentent l’action des variables. Dans le cas d’une matrice de Jordan, nousaccélérons le calcul d’interpolants multivariés sous certaines contraintes de degré ; nos résultatspour une forme de Frobenius permettent d’accélérer le calcul de formes normalesde matrices polynomiales univariées. Enfin, dans le cas de plusieurs matrices denses,nous accélérons le changement d’ordre pour des bases de Gröbner d’idéaux multivariészéro-dimensionnels