Improved Hermite multivariate polynomial interpolation
Philippe Gaborit, Olivier Ruatta · 2006
In this paper we give an algorithm with complexity O(mu2) to solve Hermite multivariate polynomial interpolation with mu conditions on its Hasse derivatives. In the case of bivariate interpolation used to perform list-decoding on Reed-Solomon of length n and dimension k with multiplicity m on each point, it permits to obtain a complexity in O(n2m4) which does not depend on the rate k/n and better than previously known complexity in O( n2m5(n/k)(1/2)). This algorithm can also be used for recent interpolation list-decoding with three and more variables. For interpolation on polynomial with n points and M variables with prescribed multiplication order m the general complexity of the algorithm is O(n2m2M)