Implicitization of curves and (hyper)surfaces using predicted support (Q385002)

This paper introduces a method for finding the implicit form \(F(x_0, \ldots, x_n) = 0\) of hypersurfaces represented in parametric form. This process is also known as implicitization. The method works by splitting the problem into two parts, which are attacked separately. The first step applies sparse (or toric) elimination theory to predict a superset \(S\) of the support of the implicit form \(F\), i.e., the monomials that have nonzero coefficient in \(F\). In the second step one forms a matrix \(M\) by evaluating monomials in \(S\) at certain random sites, and obtains the coefficient vector of \(F\) as an element of the kernel of \(M\). The method can be used in the presence of base points as well, in which case the output polynomial contains the implicit form \(F\) as a factor, and works for both exact and approximate implicitization. Implementations in Maple and Matlab are provided to study the numerical stability and efficiency for several classes of curves and surfaces. It is found that ``unitary complex numbers offer the best tradeoff between speed and accuracy when numerical methods are employed, namely SVD, whereas for exact kernel computation random integers is the method of choice''. A comparison to existing software shows that the method is rather competitive.