Fast resolution of integer Vandermonde systems

Rosa Di Salvo, Luigia Puccio

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 ℤ/pℤ, 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(ℤ/pℤ) of square matrices over ℤ/pℤ 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(n3).

Keywords


Modular arithmetic; polynomial interpolation; numerical linear algebra

Full Text:

PDF


DOI: http://dx.doi.org/10.1478/AAPP.921A2

Copyright (c) 2015 AAPP | Physical, Mathematical, and Natural Sciences