Cette thèse est centrée sur le calcul de relations de récurrence linéaires à coefficients constants satisfaites par une suite. Ce calcul est hautement structuré et peut être représenté via l’algèbre linéaire par des matrices appelées matrices Hankel. En 1968 et 1969, Berlekamp et Massey conçoivent indépendamment un algorithme exploitant cette structure pour le calcul de ces récurrences pour les suites à un indice. Cet algorithme repose sur le calcul d’un couple de polynômes appelés approximants de Padé, pouvant être obtenus de façon quasi optimale en s’appuyant sur l’algorithme du demi-PGCD. Pour les suites à plusieurs indices, le calcul de récurrences a une complexité au moins quadratique et il semble difficile d’exploiter pleinement la structure du problème afin de concevoir un algorithme plus efficace.
Cette thèse apporte deux contributions principales : l’amélioration du calcul de reconstruction rationnelle et le calcul de récurrences pour les suites à deux indices. Pour le premier aspect, des améliorations algorithmiques récentes sur les matrices polynomiales nous ont permis d’obtenir un gain d’un facteur constant sur la complexité du demi-PGCD. Pour le second, nous définissons un algorithme de demi-PGCD sur des polynômes univariés à coefficients des suites à un indice, dont les calculs intermédiaires permettent de retrouver une base de Gröbner de l’idéal des relations, et d’en dériver un algorithme de résolution de matrices bi-Hankel. Une résolution efficace de telles matrices ouvre ainsi la voie à une amélioration du calcul de bases de Gröbner via l’algorithme Sparse-FGLM.