An official website of the United States government
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
Homotopies for Connected Components of Algebraic Sets with Application to Computing Critical Sets
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
- PAR ID:
- 10073093
- Date Published:
- Journal Name:
- MACIS 2017: Mathematical Aspects of Computer and Information Sciences
- 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
-
In this paper, we construct two spanning sets for the affine algebraic curvature tensors. We then prove that every 2-dimensional affine algebraic curvature tensor can be represented by a single element from either of the two spanning sets. This paper provides a means to study affine algebraic curvature tensors in a geometric and algebraic manner similar to previous studies of canonical algebraic curvature tensors.more » « less
-
For simulations of strong field ionization using time-dependent configuration with a complex absorbing potential (TDCI-CAP), standard molecular basis set must be augmented by several sets of diffuse functions to support the wavefunction as it is distorted by the strong field and interacts with the absorbing potential. Various sets of diffuse functions used in previous studies have been extended and evaluated for their ability to model the angular dependence of strong field ionization. These sets include diffuse s, p, d and f gaussian functions with selected even-tempered exponents of the form 0.0001×2n placed on each atom. For single-centered test cases, the largest contribution to the ionization rate is from functions with a maximum in the radial distribution close to the onset of the complex absorbing potential, while functions with smaller exponents also contributed to the rate. For molecules, diffuse functions on adjacent centers overlap strongly, leading to linear dependencies. The transformation to remove these linear dependencies mixes functions of different angular momenta making it difficult to assess the importance of individual s, p, d and f functions in simulating the rate for molecules. As an alternative, a hierarchy of diffuse basis sets was constructed starting with a small set and adding one or two functions at a time. These basis sets were evaluated for their ability to reproduce the rate and the shape of the angular dependence of strong field ionization. When combined with the aug-cc-pVTZ molecular basis set and an absorbing potential starting at 3.5 times the van der Waals radius for each atom, the most diffuse s, p, d and f functions need to have exponents of 0.0032, 0.0032, 0.0064 and 0.0064, respectively, or smaller. Strong field ionization from electronegative atoms such as oxygen required additional f functions with tight exponents of 0.0512 and 0.1024. Diffuse basis sets that perform well for the angular dependence of the ionization rate with a static field are equally effective for strong field ionization with a linearly polarized 7 cycle 800 nm pulse.more » « less
-
Megow, Nicole; Smith, Adam (Ed.)Maximum weight independent set (MWIS) admits a 1/k-approximation in inductively k-independent graphs [Karhan Akcoglu et al., 2002; Ye and Borodin, 2012] and a 1/(2k)-approximation in k-perfectly orientable graphs [Kammer and Tholey, 2014]. These are a parameterized class of graphs that generalize k-degenerate graphs, chordal graphs, and intersection graphs of various geometric shapes such as intervals, pseudo-disks, and several others [Ye and Borodin, 2012; Kammer and Tholey, 2014]. We consider a generalization of MWIS to a submodular objective. Given a graph G = (V,E) and a non-negative submodular function f: 2^V → ℝ_+, the goal is to approximately solve max_{S ∈ ℐ_G} f(S) where ℐ_G is the set of independent sets of G. We obtain an Ω(1/k)-approximation for this problem in the two mentioned graph classes. The first approach is via the multilinear relaxation framework and a simple contention resolution scheme, and this results in a randomized algorithm with approximation ratio at least 1/e(k+1). This approach also yields parallel (or low-adaptivity) approximations. Motivated by the goal of designing efficient and deterministic algorithms, we describe two other algorithms for inductively k-independent graphs that are inspired by work on streaming algorithms: a preemptive greedy algorithm and a primal-dual algorithm. In addition to being simpler and faster, these algorithms, in the monotone submodular case, yield the first deterministic constant factor approximations for various special cases that have been previously considered such as intersection graphs of intervals, disks and pseudo-disks.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- https://doi.org/10.1007/978-3-319-72453-9
