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.
In this paper, a new algorithm for performing quantifier elimination from first order formulas over real closed fields in given. This algorithm improves the complexity of the asymptotically fastest algorithm for this problem, known to this data. A new feature of this algorithm is that the role of the algebraic part (the dependence on the degrees of the imput polynomials) and the combinatorial part (the dependence on the number of polynomials) are sparated. Another new feature is that the degrees of the polynomials in the equivalent quantifier-free formula that is output, are independent of the number of input polynomials. As special cases of this algorithm new and improved algorithms for deciding a sentence in the first order theory over real closed fields, and also for solving the existential problem in the first order theory over real closed fields, are obtained.  Let (S_0 ) be a smooth and compact real variety given by a reduced regular sequence of polynomials (f_1, , f_p ). This paper is devoted to the algorithmic problem of finding efficiently a representative point for each connected component of (S_0 ) . For this purpose we exhibit explicit polynomial equations that describe the generic polar varieties of (S_0 ). This leads to a procedure which solves our algorithmic problem in time that is polynomial in the (extrinsic) description length of the input equations (f_1, , f_p ) and in a suitably introduced, intrinsic geometric parameter, called the degree of the real interpretation of the given equation system (f_1, ,f_p ). 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... Let f 1 , ldots, f s be polynomials in Q[X 1 , ..., X n ] that generate a radical ideal and let V be their complex zero-set. Suppose that V is smooth and equidimensional; then we show that computing suitable sections of the polar varieties associated to generic projections of V gives at least one point in each connected component of V ∩ Rn. We deduce an algorithm that extends that of Bank, Giusti, Heintz and Mbakop to non-compact situations. Its arithmetic complexity is polynomial in the complexity of evaluation of the input system, an intrinsic algebraic quantity and a combinatorial quantity. We have developed in the past several algorithms with intrinsic complexity bounds for the problem of point finding in real algebraic varieties. Our aim here is to give a comprehensive presentation of the geometrical tools which are necessary to prove the correctness and complexity estimates of these algorithms. Our results form also the geometrical main ingredients for the computational treatment of singular hypersurfaces. In particular, we show the non–emptiness of suitable generic dual polar varieties of (possibly singular) real varieties, show that generic polar varieties may become singular at smooth points of the original variety and exhibit a sufficient criterion when this is not the case. Further, we introduce the new concept of meagerly generic polar varieties and give a degree estimate for them in terms of the degrees of generic polar varieties. The statements are illustrated by examples and a computer experiment. Tarski in 1948, (Tarski 1951) published a quantifier elimination method for the elementary theory of real closed fields (which he had discovered in 1930). As noted by Tarski, any quantifier elimination method for this theory also provides a decision method, which enables one to decide whether any sentence of the theory is true or false. Since many important and difficult mathematical problems can be expressed in this theory, any computationally feasible quantifier elimination algorithm would be of utmost significance. PLEASE NOTE: The original Technical Report TR00853 is missing. A copy can be found at http: www.sciencedirect.com science article pii S0747717110800033 Computing at least one point in each connected component of a real algebraic set is a basic subroutine to decide emptiness of semi-algebraic sets, which is a fundamental algorithmic problem in effective real algebraic geometry. In this article we propose a new algorithm for the former task, which avoids a hypothesis of properness required in many of the previous methods. We show how studying the set of non-properness of a linear projection ź enables us to detect the connected components of a real algebraic set without critical points for ź. Our algorithm is based on this observation and its practical counterpoint, using the triangular representation of algebraic varieties. Our experiments show its efficiency on a family of examples. Let the polynomials f"1,..., f"[email protected]? @?[X"1,..., X"n] have degrees deg (f"i) = 0,..., f"k >= 0. In the case of a positive answer the algorithm constructs a certain finite set of solutions (which is, in fact, a representative set for the family of components of connectivity of the set of all real solutions of the system). The algorithm runs in time polynomial in M(kd) ^n^2. The previously known upper time bound for this problem was Sh=(A"1+A"[email protected][email protected]?)[email protected]?^n.Sc^1^ ^3.