Let P ∈ Z[X, Y] be a square-free polynomial and C(P):= {(α, β) ∈ R2, P(α, β) = 0} be the real algebraic curve defined by P. Our main result is an algorithm for the computation of the local topology in a neighbourhood of each of the singular points and critical points of the projection wrt the X-axis in Õ(d6τ+d7) bit operations where Õ means that we ignore logarithmic factors in d and τ. Compared to state of the art sub-algorithms used for computing a Cylindrical Algebraic Decomposition, this result avoids a generic shear and gives a deterministic algorithm for the computation of the topology of C(P) i.e a straight-line planar graph isotopic to C(P) in Õ(d6τ + d7) bit operations.

The number of connected components of a real algebraic set defined in Rk by equations of degree d is O(d)k which is polynomial in the degree, and singly exponential in the number of variables. Moreover it is very easy to design algebraic sets defined by polynomials of degree 2d in k variables with O(d)k connected components.

In this paper we describe the first singly exponential algorithm for computing the first Betti number of a given semi-algebraic set. We also describe algorithms for obtaining semi-algebraic descriptions of the semi-algebraically connected components of any given real algebraic or semi-algebraic set. Singly exponential algorithms for computing the zero-th Betti number, and the Euler-Poincaré characteristic, were known before. No singly exponential algorithm was known for computing any of the individual Betti numbers other than the zero-th one.

Given Q 2 R[X1 ; : : : ; Xk ] with deg(Q) d; we give an algorithm that outputs a semi-algebraic description for each of the semi-algebraically connected components of Z(Q) ae R k : The complexity of the algorithm as well as the size of the output are bounded by d O(k 3 ) : More generally, given any semi-algebraic set S defined by a quantifier-free formula involving a family of polynomials, P = fP1 ; : : : ; Psg ae R[X1 ; : : : ; Xk ] whose degrees are at most d; we give an algorithm that outputs a semi-algebraic description for each of the semialgebraically connected components of S: The complexity of the algorithm as well as the size of the output is bounded by s k+1 d O(k 3 ) : This improves the previously best known bound of (sd) k O(1) for this problem due to Canny, Grigor'ev, Vorobjov and Heintz, Roy and Solern`o [9, 14]. 1 Introduction Let R be a real closed field. A semi-algebraic set in R k is the set of points which satisfy a boolean combination of polynom...

We consider a family ofspolynomials, P = {P1, …,Ps}, inkvariables with coefficients in a real closed fieldR, each of degree at mostd, and an algebraic varietyVof real dimensionk′ which is defined as the zero set of a polynomialQof degree at mostd. The number of semi-algebraically connected components of all non-empty sign conditions on P overVis bounded bysk′(O(d))k. In this paper we present a new algorithm to compute a set of points meeting every semi-algebraically connected component of each non-empty sign condition of P overV. Its complexity issk′ + 1dO(k). This interpolates a sequence of results between the Ben-Or–Kozen–Reif algorithm which is the casek′ = 0, in one variable, and the Basu–Pollack–Roy algorithm which is the casek′ =k. It improves the results where the same problem was solved in timesk′ + 1dO(k′k).

We describe an algorithm for producing the smallest complex algebralc variety containing a given semi-algebraic set S, and all the irreducible components of S. Let S be defined by s polynomials of degrees less than d with integer coefficients of bit lengths less than A4.Then the complexity of the algorithm is bounded from above by a polynomial in M, Sn, dn'.The degree of the complexification is less than sndo 'n), while the degrees of polynomials defining the complexification and irreducible components are less than do(n) 1

We consider a semi-algebraic set S defined by s polynomials of degree d in k variables.We present a new algorithm for computing a semi-algebraic path in S comecting two points if they happen to lie in the same connected component of S.This algorithm, which works in time s ~tldo(~z) improves the complexity of the fastest algorithm solving this problem known to this date.

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.

In this paper we give a new algorithm for performing quantifier elimination from first order formulae over real closed fields. This algorithm improves the complexity of the asymptotically fastest algorithm for this problem, known to this date. A new feature of our algorithm is that the role of the algebraic part (the dependence on the degrees of the input polynomials) and the combinatorial part (the dependence on the number of polynomials) are separated, making possible our improved complexity bound. Another new feature is that the degrees of the polynomials in the equivalent quantifier-free formula that we output, are independent of the number of input polynomials. As special cases of this algorithm, we obtain 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. Using the theory developed in this paper, we also give an improved bound on the radius of a ball centered at the origin, which is guaranteed to intersect every connected component of the sign partition induced by a family of polynomials. We also use our methods to obtain algorithms for solving certain decision problems in real and complex geometry which improves the complexity of the currently known algorithms for these problems.>

In this paper we show that computer algebra methods in mechanical geometry theorem proving can also be applied to obtain new theorems involving inequalities. An interesting feature is that in real geometry, several cases can occur, none of them being more generic than the other. The examples we give come from the geometry of the triangle, more precisely comparing radii of circles defined in the triangle.

Article Aspect graphs of algebraic surfaces Share on Author: Marie-Françoise Roy View Profile Authors Info & Claims ISSAC '93: Proceedings of the 1993 international symposium on Symbolic and algebraic computationAugust 1993 Pages 135–143https://doi.org/10.1145/164081.164106Online:01 August 1993Publication History 6citation245DownloadsMetricsTotal Citations6Total Downloads245Last 12 Months3Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

Recently several theoretical single exponential time algorithms (in the number of variables) have been proposed for deciding the existential theory of reals. These algorithms have from a complexity analysis point of view a much better behaviour than CAD which was doubly exponential in the number of variables, but an efficient implementation based on these new ideas has never been performed yet. This paper is devote to the development of the following idea “it is possible to implement efficiently slight variants of single exponential methods well adapted to important particular cases of the decision problem”. We explain the main ideas, propose more efficient versions of the methods and make concrete propositions for future experiments*.

Article Sturm-Habicht sequence Share on Authors: L. Gonzalez View Profile , H. Lombardi View Profile , T. Recio View Profile , M.-F. Roy View Profile Authors Info & Claims ISSAC '89: Proceedings of the ACM-SIGSAM 1989 international symposium on Symbolic and algebraic computationJuly 1989 Pages 136–146https://doi.org/10.1145/74540.74558Published:17 July 1989 36citation499DownloadsMetricsTotal Citations36Total Downloads499Last 12 Months11Last 6 weeks2 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access