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 language | English (US) |
---|---|
Pages (from-to) | 109-128 |
Number of pages | 20 |
Journal | International Journal of Shape Modeling |
Volume | 16 |
Issue number | 1-2 |
DOIs | |
State | Published - 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