Algorithms in real algebraic geometry
algorithmic real algebraic geometrycomplexity of algorithmsquantifier eliminationreal closed fieldsreal semi-algebraic sets
Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10) Research exposition (monographs, survey articles) pertaining to algebraic geometry (14-02) Semialgebraic sets and related spaces (14P10) Computational aspects in algebraic geometry (14Q99) Symbolic computation and algebraic computation (68W30)
The monograph gives a self-contained detailed exposition of the algorithmic real algebraic geometry. The first part of the book is intended to prepare the reader for understanding the main part, devoted to the algorithms. The preparatory topics include the theory of algebraically closed and real closed fields with quantifier elimination and transfer principles, the semi-algebraic sets and the related quadratic form theory, elements of topology culminating with the Oleinik-Petrovsky-Milnor-Thom upper bounds to the Betti numbers of real algebraic and semi-algebraic sets. The algorithmic problems discussed in the book are mainly real root counting, deciding the existence of solutions for systems of equalities and inequalities, computing the projections of semi-algebraic sets, deciding a sentence of the theory of real closed fields, eliminating quantifiers, and computing topological properties of algebraic and semi-algebraic sets. Among the particular algorithms studied in the book, one finds the Cauchy index theory, various methods for counting real roots and solving polynomial systems, the cylindrical decomposition algorithm, finding realizable sign conditions, computing roadmaps and connected components of algebraic and semi-algebraic sets. A special attention is paid to the complexity of the basic algorithms for linear algebra, remainder sequences, subresultant sequences, root counting methods. In general, the monograph is well written and will be useful both for beginners and for advanced readers, who work in real algebraic geometry or apply its methods in other fields.
- Subdivision methods for solving polynomial equations
- On overlays and minimization diagrams
- Bounds on sizes of finite bisimulations of Pfaffian dynamical systems
- Likelihood ratio tests and singularities
- Exotic quantifiers, complexity classes, and complete problems
- Implicit Riquier bases for PDAE and their semi-discretizations
- A prolongation-projection algorithm for computing the finite real variety of an ideal
- On the complexity of counting components of algebraic varieties
- Iterated discriminants
- Generators of the ideal of an algebraic space curve
- Isotopic triangulation of a real algebraic surface
- Real zeros of the zero-dimensional parametric piecewise algebraic variety
- Computing combinatorial types of trajectories in Pfaffian dynamics
- NC algorithms for real algebraic numbers
- Subresultants and locally nilpotent derivations.
- On the polynomial Wolff axioms
- Computing with quadratic forms over number fields
- Recognizing free generating sets of \(\ell\)-groups
- Configurations of lines in space and combinatorial rigidity
- Eliminating disjunctions by disjunction elimination
- Regions of multistationarity in cascades of Goldbeter-Koshland loops
- An equivalence theorem for regular differential chains
- Algorithms to compute the topology of orientable real algebraic surfaces
- Computing the Betti numbers of arrangements via spectral sequences
- On factoring parametric multivariate polynomials
- Margins of discrete Bayesian networks
- Determining the limits of bivariate rational functions by Sturm's theorem
- Sylvester double sums, subresultants and symmetric multivariate Hermite interpolation
- To cure or not to cure: consequences of immunological interactions in CML treatment
- The multistationarity structure of networks with intermediates and a binomial core network
- Solving the equality-constrained minimization problem of polynomial functions
- A canonical form for the continuous piecewise polynomial functions
- A short contribution to the theory of regular chains
- Solving the interference problem for ellipses and ellipsoids: new formulae
- Bit complexity for computing one point in each connected component of a smooth real algebraic set
- A comparison of algorithms for proving positivity of linearly recurrent sequences
- An introduction to multiscale techniques in the theory of Anderson localization. I
- Mixed preferential attachment model: homophily and minorities in social networks
- Interlacing families. III: Sharper restricted invertibility estimates
- The saddle point problem of polynomials
- The Schur-Erdős problem for semi-algebraic colorings
- A farewell to Ricky Pollack
- Comment on: ``Entanglement in three coupled oscillators
- Note on scalar curvature of extremal Kähler metrics on \(\mathbb{C} P^2 \# 2 \overline{\mathbb{C} P^2}\)
- Complexity of solving parametric polynomial systems
- Fixed points of the EM algorithm and nonnegative rank boundaries
- Real or natural number interpretation and their effect on complexity
- Towards semantic mathematical editing
- Three-monotone interpolation
- Multilevel polynomial partitions and simplified range searching
- Almost linear Nash groups
- Reasoning about probabilistic sequential programs
- Shallow packings, semialgebraic set systems, macbeath regions, and polynomial partitioning
- Multistationarity and bistability for fewnomial chemical reaction networks
- Curves testing boundedness of polynomials on subsets of the real plane
- Determination of the limits for multivariate rational functions
- A delineability-based method for computing critical sets of algebraic surfaces
- Determination of the tangents for a real plane algebraic curve
- On the frontiers of polynomial computations in tropical geometry
- Computing the asymptotes for a real plane algebraic curve
- Bounds for the geodesic diameter of connection components of semi-algebraic open sets
- On the complexity of real root isolation using continued fractions
- An explicit solution to Post's problem over the reals
- Topology of real algebraic space curves
- Counting complexity classes for numeric computations. II: Algebraic and semialgebraic sets
- Polynomial systems with few real zeroes
- The adjacency graph of a real algebraic surface
- Minimizing polynomials via sum of squares over the gradient ideal
- Robust global optimization with polynomials
- On the complexity of the resolvent representation of some prime differential ideals
- Extremal polynomials in Smale's mean value conjecture
- Polynomial equations with one catalytic variable, algebraic series and map enumeration
- A new approach to characterizing the relative position of two ellipses depending on one parameter
- Exact, efficient, and complete arrangement computation for cubic curves
- Rational univariate reduction via toric resultants
- Crossing patterns of semi-algebraic sets
- Numerical analysis of a bisection-exclusion method to find zeros of univariate analytic functions
- Symmetric semi-algebraic sets and non-negativity of symmetric polynomials
- Can one design a geometry engine? Can one design a geometry engine? On the (un)decidability of certain affine Euclidean geometries
- The differential of probabilistic entailment
- The anisotropic part of a quadratic form over a number field
- Positive dimensional parametric polynomial systems, connectivity queries and applications in robotics
- Machine learning the real discriminant locus
- \texttt{PTOPO}: computing the geometry and the topology of parametric curves
- Quantifier elimination theory and maps which preserve semipositivity
- The approach of moments for polynomial equations
- Existence, stability, and symmetry of relative equilibria with a dominant vortex
- Quadric arrangement in classifying rigid motions of a 3D digital image
- Faster geometric algorithms via dynamic determinant computation
- Exogenous probabilistic computation tree logic
- A heuristic prover for real inequalities
- Geometric path integrals. A language for multiscale biology and systems robustness
- Unit distances in three dimensions
- I-RiSC: an SMT-compliant solver for the existential fragment of real algebra
- Explicit factors of some iterated resultants and discriminants
- Parts of quantum states
- On the Betti numbers of sign conditions
- Delocalization properties at isolated avoided crossings in Lipkin-Meshkov-Glick type Hamiltonian models
- Categorical complexity
- Two logical hierarchies of optimization problems over the real numbers
This page was built for publication: Algorithms in real algebraic geometry
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5906950)
