.

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ème d’équations linéaires modulaires sur un anneau de polynômes, et inclut par exemple le calcul 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 bonnes propriétés. Précisément, l’entrée de notre problème consiste en un module de dimension finie spécifié par l’action des variables sur ses éléments, et en un certain nombre d’éléments de ce module ; il s’agit de calculer une base de Gröbner du modules des relations entre ces éléments. En termes d’algèbre linéaire, l’entrée décrit une matrice avec une structure de type Krylov, et il s’agit de calculer sous forme compacte une base du noyau de cette matrice. Nous proposons plusieurs algorithmes en fonction de la forme des matrices de multiplication qui représentent l’action des variables. Dans le cas d’une matrice de Jordan,nous accélérons le calcul d’interpolants multivariés sous certaines contraintes de degré ; nos résultats pour une forme de Frobenius permettent d’accélérer le calcul de formes normales de 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és zéro-dimensionnels. / In this thesis, we study algorithms for a problem of finding relations in one or several variables. It generalizes that of computing a solution to a system of linear modular equations over a polynomial ring, including in particular the computation of Hermite- Padéapproximants and bivariate interpolants. Rather than a single solution, we aim at computing generators of the solution set which have good properties. Precisely, the input of our problem consists of a finite-dimensional module given by the action of the variables on its elements, and of some elements of this module; the goal is to compute a Gröbner basis of the module of syzygies between these elements. In terms of linear algebra, the input describes a matrix with a type of Krylov structure, and the goal 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 multiplication matrices which specify the action of the variables. In the case of a Jordan matrix, we accelerate the computation of multivariate interpolants under degree constraints; our result for a Frobenius matrix leads to a faster algorithm for computing normal forms of univariate polynomial matrices. In the case of several dense matrices, we accelerate the change of monomial order for Gröbner bases of multivariate zero-dimensional ideals.

Cette thèse aborde des sujets d'approximation diophantienne et de transcendance liés aux fonctions exponentielles. Il est tout d'abord établit des liens entre les coefficients d'approximants de Hermite-Padé, ceux de polynômes d'interpolation de Hermite et certains cofacteurs d'un déterminant de Vandermonde généralisé. Nous utilisons ensuite la notion de hauteur d'une matrice (que nous majorons grâce aux liens précédemment fournis) afin de donner une nouvelle démonstration de la transcendance de $e$. Ces résultats nous permettent finalement d'obtenir de nouveaux énoncés d'approximation diophantienne tels que la minoration de la distance de l'exponentielle d'un nombre algébrique (de hauteur absolue logarithmique de Weil bornée) à un autre nombre algébrique (lui aussi de hauteur absolue logarithmique de Weil bornée) en fonction de ces mêmes bornes. Il est ensuite donné, pour différentes valeurs de nombres rationnels $a$, quelques estimations remarquables telles que le minimum, sur l'ensemble des entiers non nuls $b$ et $c$, de la distance $|e^(b)-a^(c)|$.