A reduced-complexity algorithm for polynomial interpolation

Most traditional bivariate polynomial interpolation algorithms need to construct the Gröbner basis of a module for the interpolation result. In this paper, we present an algorithm that constructs the basis for a gradually extending submodule to save computation, based on a partial order of the elements of the submodule´s Gröbner basis. It also can be generalized for negative weighted interpolation and multivariate interpolation.