An algorithm for implicit interpolation (Q744017): Difference between revisions

Let \(R=\mathbb{C}[x_1,\ldots,x_n]\) and \(f_1,\ldots,f_n\) be a sequence of polynomials with integer coefficients. Suppose that the ideal generated by these polynomials is zero-dimensional and radical. Further, assume that \(V\subset \mathbb{C}^n\) is the variety associated to these polynomials. In the paper under review, the author considers the \textit{implicit interpolation} problem; i.e. {\parindent= 6mm\begin{itemize} \item[\(\bullet\)] to construct a space \(\Pi_V\subset \mathbb{Q}[x_1,\ldots,x_n]\) so that for any \(f\) in this ring there exists \(P_f\in \Pi_V\) with \(P_f(v)=f(v)\) for each \(v\in V\) \item [\(\bullet\)] to find \(P_f\in \Pi_V\) for each \(f\in \mathbb{Q}[x_1,\ldots,x_n]\). \end{itemize}} The author applies a geometric solution of \(V\), the Bezoutian of the \(f_i\)'s and the Jacobian of the \(f_i\)'s to provide a symbolic procedure to construct \(\Pi_V\) and \(P_f\) for a given \(f\). Further, he exhibits a probabilistic algorithm for this purpose and discusses its arithmetic complexity. Finally, he shows that this algorithm improves, for some special cases, the complexities of the algorithms that use Gröbner bases or H-bases.