Efficient algorithms for computing the Euler-Poincaré characteristic of symmetric semi-algebraic sets

DOI10.1090/CONM/697/14046MaRDI QIDQ4635358zbMATH OpenOpenAlexFDO

Authors Saugata Basu, Cordian Riener

Publication date 16 April 2018

Published in Ordered Algebraic Structures and Related Topics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1608.06828

Mathematics Subject Classification ID

Topology of real algebraic varieties (14P25) Semialgebraic sets and related spaces (14P10) Effectivity, complexity and computational aspects of algebraic geometry (14Q20)

Abstract: Let $mathrmR$ be a real closed field and $mathrmDsubsetmathrmR$ an ordered domain. We consider the algorithmic problem of computing the generalized Euler-Poincar'e characteristic of real algebraic as well as semi-algebraic subsets of $mathrm{R}^k$, which are defined by symmetric polynomials with coefficients in $mathrmD$. We give algorithms for computing the generalized Euler-Poincar'e characteristic of such sets, whose complexities measured by the number the number of arithmetic operations in $mathrmD$, are polynomially bounded in terms of $k$ and the number of polynomials in the input, assuming that the degrees of the input polynomials are bounded by a constant. This is in contrast to the best complexity of the known algorithms for the same problems in the non-symmetric situation, which are singly exponential. This singly exponential complexity for the latter problem is unlikely to be improved because of hardness result ($$-hardness) coming from discrete complexity theory.

Recommendations

• Efficient algorithm for computing the Euler-Poincaré characteristic of a semi-algebraic set defined by few quadratic inequalities
• Algorithms for computing characters for symmetric spaces
• Computing characteristic polynomials of hyperplane arrangements with symmetries
• An algorithm to compute certain Euler characteristics and Chern-Schwartz-MacPherson classes
• Algorithms for the character theory of the symmetric group
• Efficient algorithms for computing the characteristic polynomial in a domain
• An algebraic formula for the Euler characteristic of some semi-algebraic sets
• A numerical approach for computing Euler characteristics of affine varieties
• Implementation of algorithms for computing characters for symmetric spaces
• Algorithms for Computations in Local Symmetric Spaces

Cites work

• scientific article; zbMATH DE number 4123876 (Why is no real title available?)
• scientific article; zbMATH DE number 1057764 (Why is no real title available?)
• scientific article; zbMATH DE number 1160037 (Why is no real title available?)
• A formula for the Euler characteristic of a real algebraic manifold
• Algorithms in real algebraic geometry
• Bounding the Betti numbers and computing the Euler-Poincaré characteristic of semi-algebraic sets defined by partly quadratic systems of polynomials
• Bounding the equivariant Betti numbers of symmetric semi-algebraic sets
• Computing roadmaps of semi-algebraic sets on a variety
• Computing the Betti numbers of semi-algebraic sets defined by partly quadratic systems of polynomials
• Computing the Euler-Poincaré characteristics of sign conditions
• Computing the first Betti number of a semi-algebraic set
• Computing the first few Betti numbers of semi-algebraic sets in single exponential time
• Constructible motivic functions and motivic integration
• Construction of roadmaps in semi-algebraic sets
• Counting connected components of a semialgebraic set in subexponential time
• Euler integration over definable functions
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
• On the Piano Movers problem. II: General techniques for computing topological properties of real algebraic manifolds
• On the Euler characteristic of semi-analytic and semi-algebraic sets
• On the degree and half-degree principle for symmetric polynomials
• On the positivity of symmetric polynomial functions. I: General results
• Operations on constructible functions

Cited in

(7)

• scientific article; zbMATH DE number 16648 (Why is no real title available?)
• An algorithm to compute certain Euler characteristics and Chern-Schwartz-MacPherson classes
• Efficient algorithm for computing the Euler-Poincaré characteristic of a semi-algebraic set defined by few quadratic inequalities
• On the equivariant Betti numbers of symmetric definable sets: vanishing, bounds and algorithms
• Faster real root decision algorithm for symmetric polynomials
• Computing the Euler-Poincaré characteristics of sign conditions
• Vandermonde varieties, mirrored spaces, and the cohomology of symmetric semi-algebraic sets

This page was built for publication: Efficient algorithms for computing the Euler-Poincaré characteristic of symmetric semi-algebraic sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4635358)