A new algorithm for solving multivariate polynomial problems by means of interpolation

In this paper we present a new kind of algorithm, for finding a solution (g0 (x), g1 (x), . . . , gn(x)) of the system: g0 (x)p0 (x) + g1 (x)p1 (x) + . . . + gn (x)pn (x) = v(x), where v(x), gi (x) and pi (x) are multivariate polynomials of a certain degree, in the variables x = (x1 , x2 , . . . , xn ). The algorithm is based on a multivariate interpolation approach, which is a straightforward extension of the univariate algorithm of Van Barel and Bultheel. In their approach interpolation points are added one after each other, taking into account the degree structure of the solution. In this pa- per, exactly the same is done, for solving multivariate interpolation problems. Every step a new interpolation point is introduced, so that the intermediate result satisfies all the previous interpolation conditions and also the new added one. After having added enough interpolation points we will have the solution. Another difference between the univariate and the multivariate approach, is the num- ber of variables and their combinations. In the multivariate case we can have a lot of monomials of the same global degree but having dif- ferent degrees in each variable, and these degrees play an important role in for example algebraic geometry. We mentioned that we search for a solution of the system (not a unique solution), but in fact we get even more, we get a set of polynomial vectors which generate the module of all the solutions. An implementation of the algorithm is made in Maple and we tested it for some different multivariate examples, varying the num- ber of unknowns and their degree structure.nrpages: 26status: publishe