Fast computation of minimal interpolation bases in Popov form for arbitrary shifts

International audienceWe compute minimal bases of solutions for a general interpolation problem,which encompasses Hermite-Pad\'e approximation and constrained multivariateinterpolation, and has applications in coding theory and security.This problem asks to find univariate polynomial relations between $m$ vectorsof size $\sigma$; these relations should have small degree with respect to aninput degree shift. For an arbitrary shift, we propose an algorithm for thecomputation of an interpolation basis in shifted Popov normal form with a costof $\mathcal{O}\tilde{~}(m^{\omega-1} \sigma)$ field operations, where $\omega$is the exponent of matrix multiplication and the notation$\mathcal{O}\tilde{~}(\cdot)$ indicates that logarithmic terms are omitted.Earlier works, in the case of Hermite-Pad\'e approximation and in the generalinterpolation case, compute non-normalized bases. Since for arbitrary shiftssuch bases may have size $\Theta(m^2 \sigma)$, the cost bound$\mathcal{O}\tilde{~}(m^{\omega-1} \sigma)$ was feasible only with restrictiveassumptions on the shift that ensure small output sizes. The question ofhandling arbitrary shifts with the same complexity bound was left open.To obtain the target cost for any shift, we strengthen the properties of theoutput bases, and of those obtained during the course of the algorithm: all thebases are computed in shifted Popov form, whose size is always $\mathcal{O}(m\sigma)$. Then, we design a divide-and-conquer scheme. We recursively reducethe initial interpolation problem to sub-problems with more convenient shiftsby first computing information on the degrees of the intermediate bases