Séminaire Calcul Formel

Efficient algorithms for computing univariate relations

by Vincent Neiger (Technical University of Denmark)

Salle XR202 (Bâtiment XLIM)

Salle XR202

Bâtiment XLIM

In this talk, we will present recent results about the fast computation of univariate relations, including in particular rational interpolants and Hermite-Pad\'e approximants. Such relations are a central tool in computer algebra, arising in situations such as the guessing of linear differential equations, the list-decoding of Reed-Solomon codes, or the computation of normal forms of polynomial matrices. After giving an overview of the problem and of existing fast algorithms, the emphasis will be placed on the main ideas behind the recent algorithmic improvements. This talk involves joint work with Claude-Pierre Jeannerod, \'Eric Schost, Gilles Villard, and Vu Thi Xuan.