Polytope-based computation of polynomial ranges

Christoph Fünfzig, Dominique Michelucci, Sebti Foufou

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Polynomial ranges are commonly used for numerically solving polynomial systems with interval Newton solvers. Often ranges are computed using the convex hull property of the tensorial Bernstein basis, which is exponential size in the number n of variables. In this paper, we consider methods to compute tight bounds for polynomials in n variables by solving two linear programming problems over a polytope. We formulate several polytopes based on the tensorial Bernstein basis, and we formulate a polytope for the quadratic patch Q n:= (x1, ..., xn, x21, ..., x2n, x1x2, ..., x n-1xn) by projections. This Bernstein polytope has Θ(n2) hyperplanes. We give the number of vertices, the number of hyperplanes, and the volume of each polytope for n = 1, 2, 3, 4, and we compare the computed range widths for random n-variate polynomials for n ≤ 10. The Bernstein polytope of polynomial size gives only marginally worse range bounds compared to the range bounds obtained with the tensorial Bernstein basis of exponential size.

Original languageEnglish (US)
Title of host publicationAPPLIED COMPUTING 2010 - The 25th Annual ACM Symposium on Applied Computing
Pages1247-1252
Number of pages6
DOIs
StatePublished - 2010
Event25th Annual ACM Symposium on Applied Computing, SAC 2010 - Sierre, Switzerland
Duration: Mar 22 2010Mar 26 2010

Publication series

NameProceedings of the ACM Symposium on Applied Computing

Other

Other25th Annual ACM Symposium on Applied Computing, SAC 2010
CountrySwitzerland
CitySierre
Period3/22/103/26/10

Keywords

  • Bernstein polynomials
  • multivariate polynomials
  • polynomial ranges
  • polytopes

ASJC Scopus subject areas

  • Software

Fingerprint Dive into the research topics of 'Polytope-based computation of polynomial ranges'. Together they form a unique fingerprint.

Cite this