An Improved Algorithm for Multivariate Polynomial Interpolation

Abstract

In this paper, we present an improved method based on Zippel’s algorithm for multivariate polynomial interpolation, and a testing point technique is proposed to verify the recovered polynomial. Compared with Zippel’s algorithm, the new method not only returns an exact target polynomial but takes less computation time as well. The experiments show the effectiveness of the improved method.