Bounds for the Range of a Bivariate Polynomial over a Triangle

The problem of finding an enclosure for the range of a bivariate polynomial p over the unit triangle is considered. The polynomial p is expanded into Bernstein polynomials. If p has only real coefficients the coefficients of this expansion, the so-called Bernstein coefficients, provide lower and upper bounds for the range. In the case that p has complex coefficients the convex hull of the Bernstein coefficients encloses the range. The enclosure is improved by subdividing the unit triangle into squares and triangles and computing enclosures for the range of p over these regions. It is shown that the sequence of enclosures obtained in this way converges to the convex hull of the range in the Hausdorff distance. Furthermore, it is described how the Bernstein coefficients on these regions can be computed economically.     

Inclusion Isotonicity of Convex–Concave Extensions for Polynomials Based on Bernstein Expansion

In this paper the expansion of a polynomial into Bernstein polynomials over an interval I is considered. The convex hull of the control points associated with the coefficients of this expansion encloses the graph of the polynomial over I. By a simple proof it is shown that this convex hull is inclusion isotonic, i.e. if one shrinks I then the convex hull of the control points on the smaller interval is contained in the convex hull of the control points on I. From this property it follows that the so-called Bernstein form is inclusion isotone, which was shown by a longish proof in 1995 in this journal by Hong and Stahl. Inclusion isotonicity also holds for multivariate polynomials on boxes. Examples are presented which document that two simpler enclosures based on only a few control points are in general not inclusion isotonic. Received September 12, 2002; revised February 5, 2003 Published online: April 7, 2003     

Delaunay partitions in Rn applied to non-convex programs and vertex/facet enumeration problems

Using a pair of theorems linking Delaunay partitions and linear programming, we develop a method to generate all simplices in a Delaunay partition of a set of points, and suggest an application to a piecewise linear non-convex optimization problem. The same method is shown to enumerate all facets of a polytope given as the convex hull of a finite set of points. The dual problem of enumerating all vertices of a polytope P defined as the intersection of a finite number of half-spaces is also addressed and solved by sequentially enumerating vertices of expanding polytopes defined within P. None of our algorithms are affected by degeneracy. Examples and computational results are given.     

A note on the Bernstein algorithm for bounds for interval polynomials

In computing the range of values of a polynomial over an intervala≤x≤b one may use polynomials of the form $$\left( {\begin{array}{*{20}c} k \\ j \\ \end{array} } \right)\left( {x - a} \right)^j \left( {b - x} \right)^{k - j} $$ called Bernstein polynomials of the degreek. An arbitrary polynomial of degreen may be written as a linear combination of Bernstein polynomials of degreek≥n. The coefficients of this linear combination furnish an upper/lower bound for the range of the polynomial. In this paper a finite differencelike scheme is investigated for this computation. The scheme is then generalized to interval polynomials.     

Solving nonlinear polynomial systems in the barycentric Bernstein basis

We present a method for solving arbitrary systems of N nonlinear polynomials in n variables over an n-dimensional simplicial domain based on polynomial representation in the barycentric Bernstein basis and subdivision. The roots are approximated to arbitrary precision by iteratively constructing a series of smaller bounding simplices. We use geometric subdivision to isolate multiple roots within a simplex. An algorithm implementing this method in rounded interval arithmetic is described and analyzed. We find that when the total order of polynomials is close to the maximum order of each variable, an iteration of this solver algorithm is asymptotically more efficient than the corresponding step in a similar algorithm which relies on polynomial representation in the tensor product Bernstein basis. We also discuss various implementation issues and identify topics for further study.     

An efficient algorithm for checking the robust stability of a polytope of polynomials

An efficient algorithm for checking the robust stability of a polytope of polynomials is proposed. This problem is equivalent to a zero exclusion condition at each frequency. It is shown that such a condition has to be checked at only afinite number of frequencies. We formulate this problem as aparametric linear program which can be solved by the Simplex procedure, with additional computations between steps consisting of polynomial evaluations and calculation of positive polynomial roots. Our algorithm requires a finite number of steps (corresponding to frequency checks) and in the important case when the polytope of parameters is a hypercube, this number is at most of orderO(m ³ n ²), wheren is the degree of the polynomials in the family andm is the number of parameters. Supported by NASA under Contract No. NCC2-477 and by a Charles Powell Foundation Grant.     

Robustness analysis of polynomials with polynomial parameterdependency using Bernstein expansion

This paper considers the robust stability verification of polynomials with coefficients depending polynomially on parameters varying in given intervals. Two algorithms are presented, both rely on the expansion of a multivariate polynomial into Bernstein polynomials. The first one is an improvement of the so-called Bernstein algorithm and checks the Hurwitz determinant for positivity over the parameter set. The second one is based on the analysis of the value set of the family of polynomials and profits from the convex hull property of the Bernstein polynomials. Numerical results to real-world control problems are presented showing the efficiency of both algorithms     

On continued fraction expansion of real roots of polynomial systems, complexity and condition numbers

We elaborate on a correspondence between the coefficients of a multivariate polynomial represented in the Bernstein basis and in a tensor-monomial basis, which leads to homography representations of polynomial functions that use only integer arithmetic (in contrast to the Bernstein basis) and are feasible over unbounded regions. Then, we study an algorithm to split this representation and obtain a subdivision scheme for the domain of multivariate polynomial functions. This implies a new algorithm for real root isolation, MCF, that generalizes the Continued Fraction (CF) algorithm of univariate polynomials.A partial extension of Vincent’s Theorem for multivariate polynomials is presented, which allows us to prove the termination of the algorithm. Bounding functions, projection and preconditioning are employed to speed up the scheme. The resulting isolation boxes have optimized rational coordinates, corresponding to the first terms of the continued fraction expansion of the real roots. Finally, we present new complexity bounds for a simplified version of the algorithm in the bit complexity model, and also bounds in the real RAM model for a family of subdivision algorithms in terms of the real condition number of the system. Examples computed with our C++ implementation illustrate the practical aspects of our method.     

Hurwitz testing sets for parallel polytopes of polynomials

In considering robustness of linear systems with uncertain paramenters, one is lead to consider simultaneous stability of families of polynomials. Efficient Hurwitz stability tests for polytopes of polynomials have earlier been developed using evaluations on the imaginary axis. This paper gives a stability criterion for parallel polytopes in terms of Hurwitz stability of a number of corners and edges. The ‘testing set’ of edges and corners depends entirely on the edge directions of the polytope, hence the results are particularly applicable in simultaneous analysis of several polytopes with equal edge directions.It follows as a consequence, that Kharitonov's four polynomial test for independent coefficient uncertainties is replaced by a test of 2q polynomials, when the stability region is a sector Ω = { e^iv | > 0, rπ/q < | v | ≤ π } and r/q is a rational number.     

基于约束Jacobi基的多项式反函数逼近及应用

求解多项式反函数是CAGD中的一个基本问题.提出一种带端点Ck约束的反函数逼近算法.利用约束Jacobi基作为有效工具, 推导了它与Bernstein基的转换公式,采用Bernstein多项式的升阶、乘积、积分与组合运算, 给出了求解反函数系数的具体算法.该算法稳定、简易, 克服了以往计算反函数的系数时每次逼近系数需全部重新计算的缺陷.最后通过具体逼近实例验证了文中算法的正确性和有效性, 同时给出了它在PH曲线准弧长参数化中的应用.     

A hierarchy of LMI inner approximations of the set of stable polynomials

Exploiting spectral properties of symmetric banded Toeplitz matrices, we describe simple sufficient conditions for the positivity of a trigonometric polynomial formulated as linear matrix inequalities (LMIs) in the coefficients. As an application of these results, we derive a hierarchy of convex LMI inner approximations (affine sections of the cone of positive definite matrices of size m) of the nonconvex set of Schur stable polynomials of given degree n<m. It is shown that when m tends to infinity the hierarchy converges to a lifted LMI approximation (projection of an LMI set defined in a lifted space of dimension quadratic in n) already studied in the technical literature. An application to robust controller design is described.     

On fractional faces of the metric polytope

The integrality recognition problem is considered on a sequence M _{n, k} of nested relaxations of a Boolean quadric polytope, including the rooted semimetric M _n and metric M _{n, 3} polytopes. The constraints of the metric polytope cut off all faces of the rooted semimetric polytope that contain only fractional vertices. This makes it possible to solve the integrality recognition problem on M _n in polynomial time. To solve the integrality recognition problem on the metric polytope, we consider the possibility of cutting off all fractional faces of M _{n, 3} by a certain relaxation M _{n, k} . The coordinates of points of the metric polytope are represented in homogeneous form as a three-dimensional block matrix. We show that in studying the question of cutting off the fractional faces of the metric polytope, it is sufficient to consider only constraints in the form of triangle inequalities.     

Parallel methods for absolute irreducibility testing

A heuristic algorithm for testing absolute irreducibility of multivariate polynomials over arbitrary fields using Newton polytopes was proposed in Gao and Lauder (Discrete Comput. Geom. 26:89–104, [2001]). A preliminary implementation by Gao and Lauder (2003) established a wide range of families of low degree and sparse polynomials for which the algorithm works efficiently and with a high success rate. In this paper, we develop a BSP variant of the absolute irreducibility testing via polytopes, with the aim of producing a more memory and run-time efficient method that can provide wider ranges of applicability, specifically in terms of the degrees of the input polynomials. In the bivariate case, we describe a balanced load scheme and a corresponding data distribution leading to a parallel algorithm whose efficiency can be established under reasonably realistic conditions. This is later incorporated in a doubly parallel algorithm in the multivariate case that achieves similar scalable performance. Both parallel models are analyzed for efficiency, and the theoretical analysis is compared to the performance of our experiments. In the empirical results we report, we achieve absolute irreducibility testing for bivariate and trivariate polynomials of degrees up to 30,000, and for low degree multivariate polynomials with more than 3,000 variables. To the best of our knowledge, this sets a world record in establishing absolute irreducibility of multivariate polynomials.     

Subdivision methods for solving polynomial equations

This paper presents a new algorithm for solving a system of polynomials, in a domain of Rⁿ${\mathbb{R}}^n$. It can be seen as an improvement of the Interval Projected Polyhedron algorithm proposed by Sherbrooke and Patrikalakis [Sherbrooke, E.C., Patrikalakis, N.M., 1993. Computation of the solutions of nonlinear polynomial systems. Comput. Aided Geom. Design 10 (5), 379–405]. It uses a powerful reduction strategy based on univariate root finder using Bernstein basis representation and Descarte’s rule  . We analyse the behavior of the method, from a theoretical point of view, shows that for simple roots, it has a local quadratic convergence speed and gives new bounds for the complexity of approximating real roots in a box of Rⁿ${\mathbb{R}}^n$. The improvement of our approach, compared with classical subdivision methods, is illustrated on geometric modeling applications such as computing intersection points of implicit curves, self-intersection points of rational curves, and on the classical parallel robot benchmark problem.     

Formalization of Bernstein Polynomials and Applications to Global Optimization

This paper presents a formalization in higher-order logic of a practical representation of multivariate Bernstein polynomials. Using this representation, an algorithm for finding lower and upper bounds of the minimum and maximum values of a polynomial has been formalized and verified correct in the Prototype Verification System (PVS). The algorithm is used in the definition of proof strategies for formally and automatically solving polynomial global optimization problems.     

A deterministic (2−2/(k+1))n algorithm for k-SAT based on local search

Local search is widely used for solving the propositional satisfiability problem. Papadimitriou (1991) showed that randomized local search solves 2-SAT in polynomial time. Recently, Schöning (1999) proved that a close algorithm for k-SAT takes time (2−2/k)ⁿ up to a polynomial factor. This is the best known worst-case upper bound for randomized 3-SAT algorithms (cf. also recent preprint by Schuler et al.).We describe a deterministic local search algorithm for k-SAT running in time (2−2/(k+1))ⁿ up to a polynomial factor. The key point of our algorithm is the use of covering codes instead of random choice of initial assignments. Compared to other “weakly exponential” algorithms, our algorithm is technically quite simple. We also describe an improved version of local search. For 3-SAT the improved algorithm runs in time 1.481ⁿ up to a polynomial factor. Our bounds are better than all previous bounds for deterministic k-SAT algorithms.     

Bounds for an interval polynomial

We discuss the evaluation of the range of values of an interval polynomial over an interval. Several algorithms are proposed and tested on numerical examples. The algorithms are based on ideas by Cargo and Shiska [2] and Rivlin [4]. The one basic algorithm uses Bernstein polynomials. It is shown to converge to the exact bounds and it has furthermore the property that if the maximum respectively the minimum of the polynomials occurs at an endpoint of the interval then the bound is exact. This is a useful property in routines for polynomials zeros. The other basic method is based on the meanvalue theorem and it has the advantage that the degree of approximation required for a certain apriori tolerance is smaller than the degree required in the Bernstein polynomial case. The mean value method is shown to be at least quadratically convergent and the Bernstein polynomial method is shown to be at least linearly convergent.     

Analysis of nonlinear electrical circuits using bernstein polynomials

In electrical circuit analysis, it is often necessary to find the set of all direct current (d.c.) operating points (either voltages or currents) of nonlinear circuits. In general, these nonlinear equations are often represented as polynomial systems. In this paper, we address the problem of finding the solutions of nonlinear electrical circuits, which are modeled as systems of n polynomial equations contained in an n-dimensional box. Branch and Bound algorithms based on interval methods can give guaranteed enclosures for the solution. However, because of repeated evaluations of the function values, these methods tend to become slower. Branch and Bound algorithm based on Bernstein coefficients can be used to solve the systems of polynomial equations. This avoids the repeated evaluation of function values, but maintains more or less the same number of iterations as that of interval branch and bound methods. We propose an algorithm for obtaining the solution of polynomial systems, which includes a pruning step using Bernstein Krawczyk operator and a Bernstein Coefficient Contraction algorithm to obtain Bernstein coefficients of the new domain. We solved three circuit analysis problems using our proposed algorithm. We compared the performance of our proposed algorithm with INTLAB based solver and found that our proposed algorithm is more efficient and fast.