## Abstract

The tensorial Bernstein basis for multivariate polynomials in n variables has a number 3^{n} 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 x_{i} and x_{i}^{2}. For these, it is possible to obtain even better domain bounds at no cost using the quadratic curve (x_{i}, x_{i}^{2}) 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