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

Raf Vandebril ²,
Marc Van Barel ³,
Olivier Ruatta ⁴,
Bernard Mourrain ⁵

Date: 1-11-2001

Abstract:

In this paper we present a new kind of algorithm, for finding a solution $(g_0(\mathbf{x}),g_1(\mathbf{x}),\ldots,g_n(\mathbf{x}))$ of the system:

$$g_0(\mathbf{x})p_0(\mathbf{x})+g_1(\mathbf{x})p_1(\mathbf{x})+\ldots+g_n(\mathbf{x})p_n(\mathbf{x})=v(\mathbf{x}),$$

where $v(\mathbf{x}), g_i(\mathbf{x})$ and $p_i(\mathbf{x})$ are multivariate polynomials of a certain degree, in the variables $\mathbf{x}=(x_1,x_2,\ldots,x_n)$. The algorithm is based on a multivariate interpolation approach, which is a straightforward extension of the univariate algorithm of Van Barel and Bultheel [15]. 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 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 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 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 number of unknowns and their degree structure.

Keywords: multivariate interpolation, multivariate polynomials, updating algorithm, module of solution vectors, pivoting