Optimizations for tensorial Bernstein-based solvers by using polyhedral bounds

Christoph Fünfzig, Dominique Michelucci, Sebti Foufou

Research output: Contribution to journalArticlepeer-review

Abstract

The tensorial Bernstein basis for multivariate polynomials in n variables has a number 3n of functions for degree 2. Consequently, computing the representation of a multivariate polynomial in the tensorial Bernstein basis is an exponential time algorithm, which makes tensorial Bernstein-based solvers impractical for systems with more than n = 6 or 7 variables. This article describes a polytope (Bernstein polytope) with a number O((n,2)) of faces, which allows to bound a sparse, multivariate polynomial expressed in the canonical basis by solving several linear programming problems. We compare the performance of a subdivision solver using domain reductions by linear programming with a solver using a change to the tensorial Bernstein basis for domain reduction. The performance is similar for n = 2 variables but only the solver using linear programming on the Bernstein polytope can cope with a large number of variables. We demonstrate this difference with two formulations of the forward kinematics problem of a Gough-Stewart parallel robot: a direct Cartesian formulation and a coordinate-free formulation using Cayley-Menger determinants, followed by a computation of Cartesian coordinates. Furthermore, we present an optimization of the Bernstein polytope-based solver for systems containing only the monomials xi and xi2. For these, it is possible to obtain even better domain bounds at no cost using the quadratic curve (xi, xi2) directly.

Original languageEnglish (US)
Pages (from-to)109-128
Number of pages20
JournalInternational Journal of Shape Modeling
Volume16
Issue number1-2
DOIs
StatePublished - Jun 2010

Keywords

  • Bernstein polynomials
  • algebraic systems
  • linear programming
  • simplex algorithm
  • subdivision solver

ASJC Scopus subject areas

  • Software
  • Modeling and Simulation
  • Computer Vision and Pattern Recognition
  • Computer Science Applications
  • Geometry and Topology
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Optimizations for tensorial Bernstein-based solvers by using polyhedral bounds'. Together they form a unique fingerprint.

Cite this