An official website of the United States government
Abstract A standard question in real algebraic geometry is to compute the number of connected components of a real algebraic variety in affine space. This manuscript provides algorithms for computing the number of connected components, the Euler characteristic, and deciding the connectivity between two points for a smooth manifold arising as the complement of a real hypersurface of a real algebraic variety. When considering the complement of the set of singular points of a real algebraic variety, this yields an approach for determining smooth connectivity in a real algebraic variety. The method is based upon gradient ascent/descent paths on the real algebraic variety inspired by a method proposed by Hong, Rohal, Safey El Din, and Schost for complements of real hypersurfaces. Several examples are included to demonstrate the approach.
more »
« less
Smooth points on semi-algebraic sets
Many algorithms for determining properties of semi-algebraic sets rely upon the ability to compute smooth points [1]. We present a simple procedure based on computing the critical points of some well-chosen function that guarantees the computation of smooth points in each connected bounded component of a real atomic semi-algebraic set. Our technique is intuitive in principal, performs well on previously difficult examples, and is straightforward to implement using existing numerical algebraic geometry software. The practical efficiency of our approach is demonstrated by solving a conjecture on the number of equilibria of the Kuramoto model for then= 4 case. We also apply our method to design an efficient algorithm to compute the real dimension of algebraic sets, the original motivation for this research.
more »
« less
- Award ID(s):
- 1813340
- PAR ID:
- 10473737
- Publisher / Repository:
- ACM
- Date Published:
- Journal Name:
- ACM Communications in Computer Algebra
- Volume:
- 54
- Issue:
- 3
- ISSN:
- 1932-2240
- Page Range / eLocation ID:
- 105 to 108
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Let $$\R$$ be a real closed field and $$\C$$ the algebraic closure of $$\R$$. We give an algorithm for computing a semi-algebraic basis for the first homology group, $$\HH_1(S,\mathbb{F})$$, with coefficients in a field $$\FF$$, of any given semi-algebraic set $$S \subset \R^k$$ defined by a closed formula. The complexity of the algorithm is bounded singly exponentially. More precisely, if the given quantifier-free formula involves $$s$$ polynomials whose degrees are bounded by $$d$$, the complexity of the algorithm is bounded by $$(s d)^{k^{O(1)}}$$. This algorithm generalizes well known algorithms having singly exponential complexity for computing a semi-algebraic basis of the zero-th homology group of semi-algebraic sets, which is equivalent to the problem of computing a set of points meeting every semi-algebraically connected component of the given semi-algebraic set at a unique point. It is not known how to compute such a basis for the higher homology groups with singly exponential complexity. As an intermediate step in our algorithm we construct a semi-algebraic subset $$\Gamma$$ of the given semi-algebraic set $$S$$, such that $$\HH_q(S,\Gamma) = 0$$ for $q=0,1$. We relate this construction to a basic theorem in complex algebraic geometry stating that for any affine variety $$X$$ of dimension $$n$$, there exists Zariski closed subsets \[ Z^{(n-1)} \supset \cdots \supset Z^{(1)} \supset Z^{(0)} \] with $$\dim_\C Z^{(i)} \leq i$, and $$\HH_q(X,Z^{(i)}) = 0$$ for $$0 \leq q \leq i$$. We conjecture a quantitative version of this result in the semi-algebraic category, with $$X$$ and $$Z^{(i)}$$ replaced by closed semi-algebraic sets. We make initial progress on this conjecture by proving the existence of $$Z^{(0)}$$ and $$Z^{(1)}$$ with complexity bounded singly exponentially (previously, such an algorithm was known only for constructing $$Z^{(0)}$$).more » « less
-
Given a polynomial system f, this article provides a general construction for homotopies that yield at least one point of each con- nected component on the set of solutions of f = 0. This algorithmic approach is then used to compute a superset of the isolated points in the image of an algebraic set which arises in many applications, such as com- puting critical sets used in the decomposition of real algebraic sets. An example is presented which demonstrates the efficiency of this approach.more » « less
-
Abstract We develop a general approach to prove K-stability of Fano varieties. The new theory is used to (a) prove the existence of Kähler-Einstein metrics on all smooth Fano hypersurfaces of Fano index two, (b) compute the stability thresholds for hypersurfaces at generalised Eckardt points and for cubic surfaces at all points, and (c) provide a new algebraic proof of Tian’s criterion for K-stability, amongst other applications.more » « less
-
Abstract Let be a simple algebraic group over an algebraically closed field . Let be a finite group acting on . We classify and compute the local types of ‐bundles on a smooth projective ‐curve in terms of the first nonabelian group cohomology of the stabilizer groups at the tamely ramified points with coefficients in . When , we prove that any generically simply connected parahoric Bruhat–Tits group scheme can arise from a ‐bundle. We also prove a local version of this theorem, that is, parahoric group schemes over the formal disc arise from constant group schemes via tamely ramified coverings.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1145/3457341.3457347
