TW 343

S. Vandebril, M. Van Barel, O. Ruatta, B. Mourrain
A new algorithm for solving multivariate polynomial problems by means of interpolation

Abstract

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 paper, 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 points 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 number of variables and their combinations. In the multivariate case we can have a lot of monomials of the same global degree but having different 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 module of polynomial vectors which generate all the solutions. Probably this algorithm has strong connections with Groebner basis algorithms, and we assume that in a lot of cases it can provide a nice alternative to the Groebner basis techniques. An implementation of the algorithm is made in Maple and we tested it for some different multivariate examples, varying the number of unknowns and their degree structure.

report.pdf / mailto: R. Vandebril