Emiris, Ioannis and Kalinka, Tatjana and Konaxis, Christos and Luu Ba, Thang (2013) Sparse implicitization by interpolation: Characterizing nonexactness and an application to computing discriminants. ComputerAided Design  Special Issue on Solid and Physical Modeling 2012, 45 (2). pp. 252261.
This is the latest version of this item.
Text
acmac0192.pdf Download (463Kb) 
Abstract
We revisit implicitization by interpolation in order to examine its properties in the context of sparse elimination theory. Based on the computation of a superset of the implicit support, implicitization is reduced to computing the nullspace of a numeric matrix. The approach is applicable to polynomial and rational parameterizations of curves and (hyper)surfaces of any dimension, including the case of parameterizations with base points. Our support prediction is based on sparse (or toric) resultant theory, in order to exploit the sparsity of the input and the output. Our method may yield a multiple of the implicit equation: we characterize and quantify this situation by relating the nullspace dimension to the predicted support and its geometry. In this case, we obtain more than one multiples of the implicit equation; the latter can be obtained via multivariate polynomial gcd (or factoring). All of the above techniques extend to the case of approximate computation, thus yielding a method of sparse approximate implicitization, which is important in tackling larger problems. We discuss our publicly available Maple implementation through several examples, including the benchmark of bicubic surface. For a novel application, we focus on computing the discriminant of a multivariate polynomial, which characterizes the existence of multiple roots and generalizes the resultant of a polynomial system. This yields an efficient, outputsensitive algorithm for computing the discriminant polynomial.
Item Type:  Article 

Subjects:  Q Science > QA Mathematics 
Depositing User:  Christos Konaxis 
Date Deposited:  19 Mar 2013 08:35 
Last Modified:  21 Aug 2017 02:18 
URI:  http://preprints.acmac.uoc.gr/id/eprint/192 
Available Versions of this Item

Sparse implicitization by interpolation:
Characterizing nonexactness and an application to computing discriminants. (deposited 30 Jun 2012 13:14)
 Sparse implicitization by interpolation: Characterizing nonexactness and an application to computing discriminants. (deposited 19 Mar 2013 08:35) [Currently Displayed]
Actions (login required)
View Item 