06044882

j

06044882 F\"unfzig, Christoph Michelucci, Dominique Foufou, Sebti Polytope-based computation of polynomial ranges. Comput. Aided Geom. Des. 29, No. 1, 18-29 (2012). 2012 Elsevier Science Publishers B.V. (North-Holland), Amsterdam EN polynomial ranges Bernstein polynomials multivariate polynomials polytopes numerical examples polynomial systems interval Newton solvers linear programming

doi:10.1016/j.cagd.2011.09.001

Summary: 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 a polytope defined as the convex hull of the coefficients with respect to the tensorial Bernstein basis, and we formulate several polytopes based on the Bernstein polynomials of the domain. These Bernstein polytopes can be defined by a polynomial number of halfspaces. We give the number of vertices, the number of hyperfaces, 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\leqslant 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.