This thesis studies algorithms for computing linear recurrence relations with constant coefficients satisfied by a sequence. This computation is highly structured and can be formulated in terms of structured linear algebra involving Hankel matrices. In 1968 and 1969, Berlekamp and Massey independently designed an algorithm exploiting this structure to compute these recurrences for uni-indexed sequences. This algorithm relies on the computation of Padé approximants, which can be obtained in a quasi-optimal complexity using the Half-GCD algorithm. For multi-index sequences, computing recurrences have at least quadratic complexity, and it seems difficult to fully exploit the structure of the problem to design a more efficient algorithm.
This thesis makes two main contributions: improving the computation of rational reconstruction and computing recurrences for bi-indexed sequences. For the first aspect, recent algorithmic improvements in polynomial matrices allowed us to obtain a constant-factor reduction in the complexity of the Half-GCD algorithm. For the second, we define a Half-GCD algorithm on univariate polynomials with uni-index sequence coefficients, whose intermediate computations allow us to recover a Gröbner basis of the ideal of relations, and to derive a solver for bi-Hankel matrices. Efficient algorithms for solving such matrices could therefore lead to faster Gröbner basis computations via the Sparse-FGLM algorithm.