Fast resolution of integer Vandermonde systems

Abstract

The resolution of polynomial interpolation problems with integer coefficients directly involves the open issue of the integer inversion of a general Vandermonde matrix defined over the field Z/pZ, for p prime number. The purpose of this paper is to demonstrate the possibility to invert a Vandermonde matrix with integer mod p coefficients and exactly compute the integer inverse matrix in the ring Mat(Z/pZ) of square matrices over Z/pZ through the new fast algorithm InVanderMOD. The explicit formula derived for the integer inversion of Vandermonde matrices entirely develops inside the field of the integers mod p, with due consideration to the operation of integer division. The inversion procedure InVanderMOD is valid for any prime number p and competitive in terms of computational effort, since its computational cost is less than O(n^3).