An official website of the United States government
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
This content will become publicly available on October 1, 2026
Ramification points of homotopies: Enumeration and general theory
Ramification points arise from singularities along solution paths of a homotopy. This paper considers ramification points of homotopies, elucidating the total number of ramification points and providing general theory regarding the properties of the set of ramification points over the same branch point. The general approach utilized in this paper is to view homotopies as lines in the parameter spaces of families of polynomial systems on a projective manifold. With this approach, the number of singularities of systems parameterized by pencils is computed under broad conditions. General conditions are given for when the singularities of the systems parameterized by a line in a space of polynomial systems have multiplicity two. General conditions are also given for there to be at most one singularity in the solution set of any system parameterized by such a line. Several examples are included to demonstrate the theoretical results.
more »
« less
- Award ID(s):
- 2331400
- PAR ID:
- 10652989
- Publisher / Repository:
- Advances in Geometry
- Date Published:
- Journal Name:
- Advances in Geometry
- Volume:
- 25
- Issue:
- 4
- ISSN:
- 1615-715X
- Page Range / eLocation ID:
- 505-527
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
null (Ed.)Uncertainty is an omnipresent issue in real-world optimization problems. This paper studies a fundamental problem concerning uncertainty, known as the β-robust scheduling problem. Given a set of identical machines and a set of jobs whose processing times follow a normal distribution, the goal is to assign jobs to machines such that the probability that all the jobs are completed by a given common due date is maximized. We give the first systematic study on the complexity and algorithms for this problem. A strong negative result is shown by ruling out the existence of any polynomial-time algorithm with a constant approximation ratio for the general problem unless P=NP. On the positive side, we provide the first FPT-AS (fixed parameter tractable approximation scheme) parameterized by the number of different kinds of jobs, which is a common parameter in scheduling problems. It returns a solution arbitrarily close to the optimal solution, provided that the job processing times follow a few different types of distributions. We further complement the theoretical results by implementing our algorithm. The experiments demonstrate that by choosing an appropriate approximation ratio, the algorithm can efficiently compute a near-optimal solution.more » « less
-
The approximate path synthesis of four-bar linkages with symmetric coupler curves is presented. This includes the formulation of a polynomial optimization problem, a characterization of the maximum number of critical points, a complete numerical solution by homotopy continuation, and application to the design of straight line generators. Our approach specifies a desired curve and finds several optimal four-bar linkages with a coupler trace that approximates it. The objective posed simultaneously enforces kinematic accuracy, loop closure, and leads to polynomial first order necessary conditions with a structure that remains the same for any desired trace leading to a generalized result. Ground pivot locations are set as chosen parameters, and it is shown that the objective has a maximum of 73 critical points. The theoretical work is applied to the design of straight line paths. Parameter homotopy runs are executed for 1440 different choices of ground pivots for a thorough exploration. These computations found the expected linkages, namely, Watt, Evans, Roberts, Chebyshev, and other previously unreported linkages which are organized into a 2D atlas using the UMAP algorithm.more » « less
-
The problem of geolocation of a radiofrequency transmitter via time difference of arrival (TDOA) and frequency difference of arrival (FDOA) is given as a system of polynomial equations. This allows for the use of homotopy continuation-based methods from numerical algebraic geometry. A novel geolocation algorithm employs numerical algebraic geometry techniques in conjunction with the random sample consensus (RANSAC) method. This is all developed and demonstrated in the setting of only FDOA measurements, without loss of generality. Additionally, the problem formulation as polynomial systems immediately provides lower bounds on the number of receivers or measurements required for the solution set to consist of only isolated points.more » « less
-
Given a set of points P and axis-aligned rectangles R in the plane, a point p ∈ P is called exposed if it lies outside all rectangles in R. In the max-exposure problem, given an integer parameter k, we want to delete k rectangles from R so as to maximize the number of exposed points. We show that the problem is NP-hard and assuming plausible complexity conjectures is also hard to approximate even when rectangles in R are translates of two fixed rectangles. However, if R only consists of translates of a single rectangle, we present a polynomial-time approximation scheme. For general rectangle range space, we present a simple O(k) bicriteria approximation algorithm; that is by deleting O(k2) rectangles, we can expose at least Ω(1/k) of the optimal number of points.more » « less
