Sparse implicitization by interpolation: Characterizing non-exactness and an application to computing discriminants

Emiris, Ioannis and Kalinka, Tatjana and Konaxis, Christos and Luu Ba, Thang (2013) Sparse implicitization by interpolation: Characterizing non-exactness and an application to computing discriminants. Computer-Aided Design - Special Issue on Solid and Physical Modeling 2012, 45 (2). pp. 252-261.

This is the latest version of this item.

[img] Text
acmac-0192.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, output-sensitive 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

Actions (login required)

View Item View Item