A fast solver for a bivariate polynomial vector homogeneous interpolation problem

In this paper we present a fast method for solving the following bivariate interpolation problem: Given the interpolation points $(\omega_i,\xi_j)$ for $i \in I$ and $ j \in J$ and the corresponding weights $\Phi_{i,j}$ and $\Psi_{i,j}$, we look for a polynomial vector $[\,p(x,y),q(x,y)\,]$ satisfying the following equation: $$p(\omega_i,\xi_j)\Phi_{i,j}+q(\omega_i,\xi_j)\Psi_{i,j}=0$$ for $i \in I$ and $j \in J$. We solve the problem by solving smaller univariate interpolation problems, which we solve with the fast interpolation solver of Van Barel and Bultheel \cite{ma006}. We rewrite the polynomials $p(x,y)$ and $q(x,y)$ in the following form: \begin{eqnarray*} p(x,y) & = & p_0(y)+p_1(y)x+p_2(y)x^2+\cdots \\ q(x,y) & = & q_0(y)+q_1(y)x+q_2(y)x^2+\cdots \end{eqnarray*} By substituting for $y$ the values of $\xi_j$ we get different univariate interpolation problems in $x$, which we solve with the fast univariate solver. This gives us a lot of univariate polynomials, which coefficients are polynomials evaluated in the interpolation points $\xi_j$. When we have enough values for these coefficients, we can also find the remaining unknown polynomials in $y$. The algorithm as presented here can be extended to multivariate problems, still being fast, and it is even possible to solve more general problems, with more unknown polynomials, but these are topics for future research. An application of this approach is the solving of a block Toeplitz matrix with circulant blocks, which can therefore be solved in a fast way. The algorithm is implemented in matlab and results concerning the accuracy and efficiency are shown.nrpages: 23status: publishe