Search for: All records

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. 

Let I = f1,..., fm ⊂ Q[x1,..., xn] be a zero dimensional radical ideal defined by polynomials given with exact rational coefficients. Assume that we are given approximations {z1,..., zk} ⊂ Cn for the common roots {ξ1,..., ξk} = V (I) ⊆ Cn. In this paper we show how to construct and certify the rational entries of Hermite matrices for I from the approximate roots {z1,..., zk}. When I is non-radical, we give methods to construct and certify Hermite matrices for √ I from the approximate roots. Furthermore, we use signatures of these Hermite matrices to give rational certificates of non-negativity of a given polynomial over a (possibly positive dimensional) real variety, as well as certificates that there is a real root within an ε distance from a given point z ∈ Qn. 

In this paper we provide a new method to certify that a nearby polynomial system has a singular isolated root and we compute its multiplicity structure. More precisely, given a polynomial system, we present a Newton iteration on an extended deflated system that locally converges, under regularity conditions, to a small deformation of f such that this deformed system has an exact singular root. The iteration simultaneously converges to the coordinates of the singular root and the coefficients of the so-called inverse system that describes the multiplicity structure at the root. We use α-theory test to certify the quadratic convergence, and to give bounds on the size of the deformation and on the approximation error. The approach relies on an analysis of the punctual Hilbert scheme, for which we provide a new description. We show in particular that some of its strata can be rationally parametrized and exploit these parametrizations in the certification. We show in numerical experimentation how the approximate inverse system can be computed as a starting point of the Newton iterations and the fast numerical convergence to the singular root with its multiplicity structure, certified by our criteria. 

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. 

In this paper we provide a new method to certify that a nearby polynomial system has a singular isolated root and we compute its multiplicity structure. More precisely, given a polynomial system f = (f1, ..., fN) ∈ C[x1, ..., xn]^N, we present a Newton iteration on an extended deflated system that locally converges, under regularity conditions, to a small deformation of f such that this deformed system has an exact singular root. The iteration simultaneously converges to the coordinates of the singular root and the coefficients of the so-called inverse system that describes the multiplicity structure at the root. We use α-theory test to certify the quadratic convergence, and to give bounds on the size of the deformation and on the approximation error. The approach relies on an analysis of the punctual Hilbert scheme, for which we provide a new description. We show in particular that some of its strata can be rationally parametrized and exploit these parametrizations in the certification. We show in numerical experimentation how the approximate inverse system can be computed as a starting point of the Newton iterations and the fast numerical convergence to the singular root with its multiplicity structure, certified by our criteria. 

Let 𝑓1,…,𝑓𝑚 be univariate polynomials with rational coefficients and I:=⟨𝑓1,…,𝑓𝑚⟩⊂ℚ[𝑥] be the ideal they generate. Assume that we are given approximations {𝑧1,…,𝑧𝑘}⊂ℚ[𝑖] for the common roots {𝜉1,…,𝜉𝑘}=𝑉(I)⊆ℂ . In this study, we describe a symbolic-numeric algorithm to construct a rational matrix, called Hermite matrix, from the approximate roots {𝑧1,…,𝑧𝑘} and certify that this matrix is the true Hermite matrix corresponding to the roots V(I) . Applications of Hermite matrices include counting and locating real roots of the polynomials and certifying their existence.