Numerical examples

The implementation we made is available in maple and can be found and downloaded at http://www.cs.kuleuven.ac.be/$\sim$marc/software. The algorithm, uses pivoting to increase the numerical stability.

We performed two different types of tests. In the first we generated several examples in two variables, varying the degree.

Figure 1 gives an idea of the error produced by the algorithm, the error is measured as follows. We generated a fixed number of points $r$ on the unit circle of two variables, which we denote as $z_i=[x_i,y_i]$ (such that $x_i^2+y_1^2=1$). We denote the computed solution as $\mathbf{G}(\mathbf{x})$. We measure the error by computing the residual:

$$res=\max_{1\leq i \leq r} \frac{\vert\sum_{j=0}^{4}p_j(x_i,y_i)g_... ...{0\leq j \leq 4}\{\vert p_j(x_i,y_i)g_j(x_i,y_i)\vert,\vert v(x_i,y_i)\vert\}},$$

which is measured for three kinds of interpolation points: random points, an equal spaced grid, and a chebyshev grid always in $[-1,1]$.

Figure 1: Relative residual norms for the algorithm, in case of two variables.

Figure 2 gives the number of iteration steps, versus the degree of the input vector $\mathbf{P}(\mathbf{x})$.

Figure: Number of steps versus the degree of the polynomial $\mathbf{P}$.

Figure 3 shows that the algorithm can be adapted reducing the maximum number of columns to compute a solution. The maximum number of columns is calculated in the following way:

$$maxnumcol=numvars+2\;\;+\;\;numip*(numvars-1).$$

But in the algorithm, we can incorporate some cutting criterias. When a column in $\mathbf{B}(\mathbf{x})$ is too small, which means that the coefficients are very small, we can remove this column, because its residual will always be zero from now on, and this column will not contribute anymore in finding the solution. The second way to reduce the number of columns of $\mathbf{B}(\mathbf{x})$, is to pick out the solution columns, because we are searching for a module of solutions we immediately take out every column already satisfying our multivariate interpolation conditions. Because we maintain a matrix with residuals it is not so hard to see when a column is a solution of the homogeneous problem, so we can filter out these columns. This is what is presented in the next figure, the maximum number of columns, versus number of columns used in the algorithm.

Figure 3: Number of columns, versus the maximum number of columns.