Let @math be a linear matrix, or pencil, generated by given symmetric matrices @math of size @math with rational entries. The set of real vectors x such that the pencil is positive semidefinite is a convex semi-algebraic set called spectrahedron, described by a linear matrix inequality (LMI). We design an exact algorithm that, up to genericity assumptions on the input matrices, computes an exact algebraic representation of at least one point in the spectrahedron, or decides that it is empty. The algorithm does not assume the existence of an interior point, and the computed point minimizes the rank of the pencil on the spectrahedron. The degree @math of the algebraic representation of the point coincides experimentally with the algebraic degree of a generic semidefinite program associated to the pencil. We provide explicit bounds for the complexity of our algorithm, proving that the maximum number of arithmetic operations that are performed is essentially quadratic in a multilinear B 'ezout bound of @math . When @math (resp. @math ) is fixed, such a bound, and hence the complexity, is polynomial in @math (resp. @math ). We conclude by providing results of experiments showing practical improvements with respect to state-of-the-art computer algebra algorithms.
On input @math , @math can be defined by @math polynomial inequalities in @math of degree @math (see e.g. @cite_34 ). As far as we know, the state-of-the-art for designing algorithms deciding the emptiness of @math consists only of algorithms for deciding the emptiness of general semi-algebraic sets; our contribution being the first attempt to exploit structural properties of the problem, e.g. through the smallest rank property (Theorem ).
@cite_34
2950326154 2063194632 2949393806 2949730746
Let @math be an arbitrary polynomial of degree @math with @math non-zero integer coefficients of absolute value less than @math . In this paper, we answer the open question whether the real roots of @math can be computed with a number of arithmetic operations over the rational numbers that is polynomial in the input size of the sparse representation of @math . More precisely, we give a deterministic, complete, and certified algorithm that determines isolating intervals for all real roots of @math with @math many exact arithmetic operations over the rational numbers. When using approximate but certified arithmetic, the bit complexity of our algorithm is bounded by @math , where @math means that we ignore logarithmic. Hence, for sufficiently sparse polynomials (i.e. @math for a positive constant @math ), the bit complexity is @math . We also prove that the latter bound is optimal up to logarithmic factors. Let @math be @math -variate polynomials with rational coefficients of maximum degree @math and let @math be the set of common complex solutions of @math . We give an algorithm which, up to some regularity assumptions on @math , computes an exact representation of the global infimum @math of the restriction of the map @math to @math , i.e., a univariate polynomial vanishing at @math and an isolating interval for @math . Furthermore, it decides whether @math is reached, and if so, it returns @math such that @math . This algorithm is probabilistic. It makes use of the notion of polar varieties. Its complexity is essentially cubic in @math and linear in the complexity of evaluating the input. This fits within the best known deterministic complexity class @math . We report on some practical experiments of a first implementation that is available as a Maple package. It appears that it ca... We show a new way to round vector solutions of semidefinite programming (SDP) hierarchies into integral solutions, based on a connection between these hierarchies and the spectrum of the input graph. We demonstrate the utility of our method by providing a new SDP-hierarchy based algorithm for constraint satisfaction problems with 2-variable constraints (2-CSP's). More concretely, we show for every 2-CSP instance I a rounding algorithm for r rounds of the Lasserre SDP hierarchy for I that obtains an integral solution that is at most worse than the relaxation's value (normalized to lie in [0,1]), as long as r > k ( ) ( ) ;, where k is the alphabet size of I, @math , and @math denotes the number of eigenvalues larger than @math in the normalized adjacency matrix of the constraint graph of @math . In the case that @math is a instance, the threshold @math is only a polynomial in @math , and is independent of the alphabet size. Also in this case, we can give a non-trivial bound on the number of rounds for instance. In particular our result yields an SDP-hierarchy based algorithm that matches the performance of the recent subexponential algorithm of Arora, Barak and Steurer (FOCS 2010) in the worst case, but runs faster on a natural family of instances, thus further restricting the set of possible hard instances for Khot's Unique Games Conjecture. Our algorithm actually requires less than the @math constraints specified by the @math level of the Lasserre hierarchy, and in some cases @math rounds of our program can be evaluated in time @math . We consider the problem of computing critical points of the restriction of a polynomial map to an algebraic variety. This is of first importance since the global minimum of such a map is reached at a critical point. Thus, these points appear naturally in non-convex polynomial optimization which occurs in a wide range of scientific applications (control theory, chemistry, economics,...). Critical points also play a central role in recent algorithms of effective real algebraic geometry. Experimentally, it has been observed that Gr "obner basis algorithms are efficient to compute such points. Therefore, recent software based on the so-called Critical Point Method are built on Gr "obner bases engines. Let @math be polynomials in @math of degree @math , @math be their complex variety and @math be the projection map @math . The critical points of the restriction of @math to @math are defined by the vanishing of @math and some maximal minors of the Jacobian matrix associated to @math . Such a system is algebraically structured: the ideal it generates is the sum of a determinantal ideal and the ideal generated by @math . We provide the first complexity estimates on the computation of Gr "obner bases of such systems defining critical points. We prove that under genericity assumptions on @math , the complexity is polynomial in the generic number of critical points, i.e. @math . More particularly, in the quadratic case D=2, the complexity of such a Gr "obner basis computation is polynomial in the number of variables @math and exponential in @math . We also give experimental evidence supporting these theoretical results.