Properness defects of projections and computation of one point in each connected

component of a real algebraic set

Mohab Safey El Din, LIP6, Université Paris 6, France

Mohab.Safey@lip6.fr

Éric Schost, GAGE, École polytechnique, France Eric.Schost@polytechnique.fr

May 2, 2003

Abstract

Computing at least one point in each connected component of a real algebraic set is a basic subroutine to decide emptiness of semialgebraic sets, which is a fundamental algorithmic problem in effective real algebraic geometry. In this article, we propose a new algorithm for this task, which avoids a hypothesis of properness required in many of the previous methods.

We show how studying the set of non-properness of a linear projection enables to detect connected components of a real algebraic set without critical points. Our algorithm is based on this result and its practical counterpoint, using the triangular representation of algebraic varieties. Our experiments show its efficiency on a family of examples.

1 Introduction

Finding at least one point in each connected component of a semi-algebraic set, or at least deciding if it is empty, is a fundamental problem in effective real algebraic geometry, which appears in many academic or industrial applications: filter banks [17], robotics [31], celestial mechanics, etc…

A well known algorithm having such an output is Collins’ Cylindrical Algebraic Decomposition algorithm [12]. It has complexity doubly exponential in the number of variables, in terms of arithmetic operations and size of the output. In practice, the best implementations are limited to problems having less than 5 variables.

More recently, algorithms to compute at least one point in each connected component of a semi-algebraic set were proposed in [23, 24, 25, 7, 8, 9], with complexity simply exponential in the number of variables. These algorithms reduce this question to the computation of one point in each connected component of several real algebraic sets. Thus, designing efficient algorithms for this last question is crucial to deal efficiently with inequalities. This paper is in keeping with this framework.

The critical point method. We first briefly describe the state of the art of computing one point in each connected component of a real algebraic set.

A widely used method is the critical point method. It consists in studying a map that reaches an extremum on each connected component of the real algebraic set under consideration, and whose critical locus is zero-dimensional. Here are some declinations of this approach.

In [23, 24, 25, 7, 8, 9], the authors reduce the general case to the study of smooth and compact real algebraic sets, via several infinitesimal deformations. As is well known, any projection on a straight line reaches an extremum on each connected component of a compact real algebraic set. The above articles show how to choose a projection with zero-dimensional critical locus; this yields algorithms with complexities that are simply exponential in the number of variables.

A similar approach is studied in [6, 5], respectively for smooth compact hypersurfaces and smooth compact complete intersections. In both cases, the critical points of the projection on a generic line are shown to belong to a family of formal polar varieties. Studying these polar varieties allows to define a notion of intrinsic geometric degree for real algebraic systems. The resulting algorithms are based on the representation of polynomials by Straight-Line Programs; this yields a complexity that is polynomial in both the intrinsic geometric degree and the complexity of evaluation of the input system.

In [38, 4, 42], the authors utilize the square of the distance to a given point; such functions will simply be called distance functions in the sequel. This enables to drop the compactness assumption, since distance functions reach a minimum on each connected component of any real algebraic set. In [38], the singular case is treated by a single infinitesimal deformation, while in [4] it is treated by iteratively studying the real points of the singular locus. No complexity estimate is given in neither [38] nor [4]. Nevertheless, an extensive family of examples was studied in [39]; on these examples the iterative approach of [4] performed better than the one using an infinitesimal deformation.

Several of the algorithms mentioned above require to isolate the real solutions of zero-dimensional polynomial systems. Many solutions exist for this question; for completeness, we briefly review some of them.

A commonly used solution is the computation of a Gröbner basis [11, 18, 15, 16], possibly followed by the computation of a Rational Univariate Representation [1, 37]. We also mention the work of Giusti, Heintz, Lecerf, Pardo and collaborators [21, 20, 19, 22], which culminated in the design of the algorithm of geometric resolution, whose real counterpart was mentioned above. Through such approaches, isolating the real solutions of a zero-dimensional system is reduced to study the real roots of a univariate polynomial. For handling this task, we refer to [43, 41, 40].

Let us also mention the algorithms based on triangular sets, see [30, 29, 45, 28, 33, 34, 2] and [46] for a panoramic survey; the real closure of [36] is well adapted to this representation. Finally, symbolic-numeric techniques can also be used, see [14, 44] and references therein.

Projection functions in the non-compact case. The above algorithms detect the connected components of a real algebraic set by the presence of critical points, which are characterized by the vanishing of suitable minors of jacobian matrices. As we have seen, two approaches were considered, using either distance functions or projections; it turns out that both suffer practical difficulties.

On the one hand, the degrees of the minors arising when using a distance function limits the performance of the algorithm designed in [4]. This makes it desirable to use projection functions in the first place, since the jacobian determinants characterizing the critical locus of a projection have better properties, see the discussion in Section 6.

On the other hand, algorithms using projections apply only to compact varieties: already simple examples like hyperbolas show that some projections may have no critical points on non-compact varieties. Yet, the reduction of the general case to the compact situation by infinitesimal deformations burdens the algorithms of [23, 24, 25, 7, 8, 9], so that the practical performances of these algorithms do not reflect their good complexity.

Thus, using projection functions without compactification could lead to significant practical improvements. Our contribution in this article is to study such projections in the presence of non-compact connected components. From this geometric study, we deduce a new algorithm for the computation of one point in each connected component of a real algebraic set. Our first experiments show a promising behavior.

The set of properness of a dominant map. Our approach uses the notion of properness of a continuous map, which we now introduce, together with the notion of a dominant map.

• Let f : V → W be a map of topological spaces. The function f is said to be proper at w ∈ W if there is a neighborhood B of w such that f^{−1}(\overline{B}) is compact, where \overline{B} denotes the closure of B.

In this article, we consider functions between complex or real algebraic varieties. The notion of properness will be relative to the topologies induced by the metric topologies of ℂ or ℝ.

• A map of irreducible complex varieties f : V → W is said to be dominant if its image is dense in W, i.e. if the dimension of f(V) as a complex constructible set equals the dimension of W. We extend this definition to the case of a map V → W, where V is not necessarily irreducible. Then we require that the restriction of f to each irreducible component of V be dominant.

Let V ⊂ ℂ^{n} be an algebraic variety of dimension d and Π : V → ℂ^{d} a dominant projection. Then by the theorem of dimension of fibers, Π has generically finite fibers. In this situation, the following fundamental point is proven in [27]: the set of points of ℂ^{d} at which f is not proper is a hypersurface.

In this situation, we will denote by P_{Π} a squarefree polynomial defining the hypersurface of ℂ^{d} at which Π restricted to V is not proper. Our first result shows how P_{Π} can be used to obtain one point on each connected component of V ∩ ℝ^{n}.

Theorem 1 Let V ⊂ ℂ^{n} be an equidimensional algebraic variety of dimension d. Let Π be the projection:

\begin{aligned}Π : & ℂ^{n} & → & ℂ^{d} \\ & (x_{1}, …, x_{n}) & ↦ & (x_{1}, …, x_{d}). \end{aligned}

Suppose that the restriction of Π to V is dominant. Let D be a connected component of V ∩ ℝ^{n}, such that D contains no singular point of V, and no critical point for Π.

Let P_{Π} be a polynomial defining the set at which Π is not proper. Then there exists a connected component of the semi-algebraic set defined by P_{Π} ≠ 0 which is contained in Π(D).

As a consequence, given a variety V ⊂ ℂ^{n} and a projection Π satisfying the assumptions of Theorem 1, the connected components of V ∩ ℝ^{n} can be reached by:

• detecting the connected components which contain either singular points or critical points for Π;

• for all other connected components, computing one point in each connected component of P_{Π} ≠ 0; and, given such a point y, studying the fiber V ∩ Π^{−1}(y).

This dichotomy is the basis of our algorithm. To implement this idea, we will use an adapted representation of algebraic sets, the triangular set representation. Indeed, it turns out that the assumptions of Theorem 1 are readily checked using this kind of representation.

Triangular sets. The following definitions come from [3, 2, 34, 32]; for a detailed survey of such notions, we refer to [26]. We note that the triangular representation was already used in the article [4], in a similar context of real algebraic geometry.

Consider a lexicographic order on some variables X_{1}, …, X_{n}. Given a nonconstant polynomial P in ℚ[X_{1}, …, X_{n}], we call main variable of P and denote by mvar(P) the greatest variable appearing in P with respect to this order. With these notations, we define triangular sets as follows: a family T = (t_{d+1}, …, t_{n}) of non-constant polynomials in ℚ[X_{1}, …, X_{n}] is a triangular set if and only if mvar(t_{i}) ≠ mvar(t_{j}) for t_{i} ≠ t_{j}. The algebraic variables are the main variables of the polynomials in T ; the other variables are called transcendental.

Some additional conditions must be imposed to ensure a regular enough behavior. Natural restrictions lead to the notions of regular separable triangular sets, and a generalization thereof, strongly normalized triangular sets. Their definition relies on the notions of initials and separants, which we now introduce.

The initial of a polynomial P is its leading coefficient, when P is considered as univariate in its main variable. The separant of P is the polynomial ∂P /∂mvar(P). If T = (t_{d+1}, …, t_{n}) is a triangular set, we will denote by h_{i} the initial of t_{i}, and by s_{i} the separant of t_{i}, for i in {d + 1, …, n}.

• Let T be a triangular set and let h be the product of its initials. The saturated ideal of T is the saturation of T with respect to h:

sat(T ) = ⟨T ⟩ : h^{∞} = {P ∈ ℚ[X_{1}, …, X_{n}] | ∃n ∈ ℕ, h^{n}P ∈ ⟨T ⟩}

The quasi-component of T is the constructible set W (T ) = V (T )\V (h). Thus the zero-set of sat(T ) is the Zariski closure of W (T ), denoted by \overline{W (T )}.

• A triangular set T is regular if, for i in {d + 1, …, n}, the initial h_{i} does not divide zero in ℚ[X_{1}, …, mvar(t_{i−1})]/sat(t_{d+1}, …, t_{i−1}).

• A regular triangular set T is separable if, for i in {d + 1, …, n}, the separant s_{i} does not divide zero in ℚ[X_{1}, …, mvar(t_{i})]/sat(t_{d+1}, …, t_{i}).

• A regular and separable triangular set T is strongly normalized if for i in {d + 1, …, n}, the initial h_{i} depends only on the transcendental variables of T .

The following two results show that such triangular sets provide a useful tool for our initial question. The first fundamental fact is proven in [32]: if (P_{1}, …, P_{k}) is any family of polynomials, there exists strongly normalized triangular sets T_{1}, …, T_{ℓ} such that the equality V (P_{1}, …, P_{k}) = ∪_{i=1}^{ℓ}\overline{W (T_{i})} holds.

Thus, we can concentrate on the case of a variety given as the closure of the quasi-component of a strongly normalized triangular set. Then the second important fact is the translation of Theorem 1 to this context.

Theorem 2 Let T ⊂ ℚ[X_{1}, …, X_{n}] be a strongly normalized triangular set, and suppose that the transcendental variables of T are X_{1}, …, X_{d}. Let Π be the projection

\begin{aligned}Π : & ℂ^{n} & → & ℂ^{d} \\ & (x_{1}, …, x_{n}) & ↦ & (x_{1}, …, x_{d}) \end{aligned}

and s and h the product of respectively the separants and the initials of T . Let \overline{W (T )} be the Zariski closure of W (T ) and D a connected component of \overline{W (T )} ∩ ℝ^{n}.

If D ∩ V (s) is empty, then there exists a connected component of the semialgebraic set defined in ℝ^{d} by h ≠ 0 which is contained in Π(D).

This effective version of Theorem 1 is the key to design our algorithm. On input a polynomial family (P_{1}, …, P_{k}) in ℚ[X_{1}, …, X_{n}], this algorithm returns a set of zero-dimensional systems whose set of real roots intersect each connected component of the real algebraic set defined by P_{1} = … = P_{k} = 0. It can be sketched as follows:

We first compute a decomposition in strongly normalized triangular sets of the complex variety defined by P_{1} = … = P_{k} = 0. Then we apply Theorem 2 to each of these triangular sets: the connected components of the closure of its quasi-component are reached by studying both the intersection with the zero-set of the separants, and the hypersurface defined by the initials.

This algorithm requires to treat a semi-algebraic problem: compute at least one point in each connected component of a real semi-algebraic set defined by P ≠ 0, with P in ℚ[X_{1}, …, X_{d}]. There exist algorithms with simply exponential complexity for this task, see [23, 24, 25, 7, 8, 9]. Yet, it is far from obvious to obtain an efficient implementation of such algorithms. For our first experiments, we found it better to use the projection step of the Cylindrical Algebraic Decomposition algorithm.

Complexity issues and practical performances. In this paper, we do not give complexity results. The crucial problem is to bound the geometric degree of the intermediate varieties appearing in the algorithm. Indeed, these varieties describe nested singular loci; the crudest upper bound on their degrees is doubly exponential in the number of variables. On the other hand, we are not aware of any lower bound for this question.

Thus, the complexity of our algorithm in terms of size of the output is still a largely open problem, which should be solved before estimating its arithmetic complexity.

On the practical side, we compared our algorithm with the one from [4], which had shown by far the best performances in the comparative tests made in [39]. Most of the test-suite problems describe non-compact varieties, which prevents the comparison with the algorithm from [5].

These problems come mostly from academic or industrial applications of the FRISCO test-suite [10]. On almost all these tests, our algorithm ran faster than the one from [4]; we can also solve problems that were out of the reach of that algorithm.

Organization of the paper. Sections 2 and 3 are devoted to prove Theorems 1 and 2. The details of the main algorithm are presented in Section 4. Section 5 presents a solution for studying the complementary of a real hypersurface, which is inspired by the projection step of the Cylindrical Algebraic Decomposition. Finally, Section 6 presents our practical experiments.

2 Proof of Theorem 1

This section is devoted to prove Theorem 1. Let V ⊂ ℂ^{n} be an equidimensional variety and Π the projection:

\begin{aligned}Π : & ℂ^{n} & → & ℂ^{d} \\ & (x_{1}, …, x_{n}) & ↦ & (x_{1}, …, x_{d}). \end{aligned}

Suppose that the restriction of Π to V is dominant. Let D be a connected component of V ∩ℝ^{n} without singular point nor critical point for Π and let P_{Π} be a polynomial defining the set at which Π is not proper. Then Theorem 1 states that there exists a connected component S of the semi-algebraic set defined by P_{Π} ≠ 0 contained in Π(D).

Let us denote by U the image Π(D). The proof of Theorem 1 uses the following classical result on the properness defects of a continuous map.

Lemma 1 For all α in \overline{U} \ U, Π restricted to D is not proper at α.

Let α be in \overline{U} \ U, and suppose that Π is proper at α. Then there exists an open set B ⊂ ℝ^{d} containing α such that Π^{−1}(\overline{B}) is compact, where \overline{B} is the closure of B for the metric topology. This implies that U ∩ \overline{B} = Π(Π^{−1}(\overline{B}) ∩ D) is compact, hence closed. This contradicts the fact that α is in \overline{U} \ U. □

We can now prove Theorem 1. Let y be in U and x in D, such that Π(x) = y. By assumption, x is neither a critical point of Π restricted to V nor a singular point of V. Thus, from the implicit function theorem, there exists a neighborhood B of y included in U = Π(D), so U is open. We then deduce that there exists a connected component S of P_{Π} ≠ 0, such that U ∩ S ≠ ∅. Let us show that this implies that S ⊂ U, which will conclude the proof.

Indeed, suppose on the contrary that there exist y_{1} ∈ U ∩ S and y_{2} ∈ S \ U and let γ ⊂ S be a continuous path linking y_{1} and y_{2}. Since U is open, there exists y_{0} ∈ γ such that y_{0} ∈ \overline{U} \ U. From Lemma 1, Π restricted to V is not proper at y_{0}. Thus P_{Π}(y_{0}) = 0, which contradicts the fact that y_{0} is in S. □

3 Proof of Theorem 2

We now prove an effective version of Theorem 1, dedicated to the case when the variety V is the closure of the quasi-component of a strongly normalized triangular set. This is encapsulated in Theorem 2.

Let T ⊂ ℚ[X_{1}, …, X_{n}] be a strongly normalized triangular set, and suppose that the transcendental variables of T are X_{1}, …, X_{d}. Let Π be the projection

\begin{aligned}Π : & ℂ^{n} & → & ℂ^{d} \\ & (x_{1}, …, x_{n}) & ↦ & (x_{1}, …, x_{d}) \end{aligned}

and s and h the product of respectively the separants and the initials of T . Let \overline{W (T )} be the Zariski closure of W (T ) and D a connected component of \overline{W (T )} ∩ ℝ^{n}. If D ∩ V (s) is empty, then Theorem 2 asserts that there exists a connected component S of the semi-algebraic set defined by h ≠ 0 such that S is contained in Π(D).

Proving Theorem 2 requires to relate the singular points of \overline{W (T )}, the critical points of Π on \overline{W (T )} and the set of non-properness of Π to respectively the separants and the initials of T ; then we will apply Theorem 1 with this supplementary information. We use a series of intermediate results; the first of them is proven in [3] and [35].

Lemma 2 \overline{W (T )} is equidimensional of dimension d, and \overline{W (T )} ∩ V (s) has dimension less than d. Furthermore, the restriction of Π to \overline{W (T )} is dominant.

The next lemma gives an explicit characterization of a subvariety in \overline{W (T )} containing the singular points and the critical points of Π on \overline{W (T )}.

Lemma 3 The singular points of \overline{W (T )} and the critical points of Π on \overline{W (T )} are included in \overline{W (T )} ∩ V (s).

Proof. Let S be a finite family generating sat(T ), so that {T , S} also generates sat(T ). From Lemma 2, this ideal is radical and equidimensional of dimension d (see [3]), so the singular locus of \overline{W (T )} is contained in the zeroset of the n − d × n − d minors of the jacobian of {T , S}. The product s of the separants of T appears as one of these minors, which proves the first part of the proposition.

Now, suppose that y is a critical point of the restriction of Π to the regular part of \overline{W (T )}. If the rank of the jacobian of T in y is less than n − d, then y ∈ V (s), and we are done. Suppose now that the rank of the jacobian of T in y equals n − d. Then the tangent space T_{y}\overline{W (T )} is the zero-set of grad_{y}(t_{d+1}), …, grad_{y}(t_{n}). Then y being critical for Π yields the inequality

dim(Span(u_{1}, …, u_{d}, grad_{y}(t_{d+1}), …, grad_{y}(t_{n}))) < n

where u_{1}, …, u_{d} are unitary vectors on the axes corresponding to the transcendental variables of T . In particular, the jacobian determinant of T with respect to the algebraic variables vanishes at y; i.e. y is in V (s). □

Lemma 4 Let Γ ⊂ ℂ^{d} be the set at which the restriction of Π to \overline{W (T )} is not proper. Then Γ is contained in the zero-set of h.

Proof. Consider the primary decomposition of sat(T ) in ℂ[X_{1}, …, X_{n}]: sat(T ) = ∩_{ℓ≤L}A_{ℓ}. Since sat(T ) is radical, all ideals A_{ℓ} are prime. Correspondingly, we write the decomposition of \overline{W (T )} into ℂ-irreducible components: \overline{W (T )} = ∪_{ℓ≤L}V_{ℓ}, where V_{ℓ} is the zero-set of A_{ℓ}.

We use this decomposition to apply a characterization from [27] of the set of non-properness, which is valid in the irreducible case. Let K = ℂ(X_{1}, …, X_{d}) denotes the rational function field on the set of transcendental variables, sat(T )_{K}, T_{K} and A_{ℓ,K} the extensions of the ideals sat(T ), T and A_{ℓ} in the ring K[X_{d+1}, …, X_{n}]. Since the restriction of Π to each V_{ℓ} is dominant, none of the ideals A_{ℓ} can contain a polynomial in ℂ[X_{1}, …, X_{d}]. From this, and using the definition of sat(T ), the following assertions come from a routine check:

• for all ℓ, A_{ℓ,K} is a prime ideal of dimension zero;

• two distinct ideals A_{ℓ,K} and A_{ℓ′,K} generate the unit ideal;

• K[X_{d+1}, …, X_{n}]/A_{ℓ,K} is isomorphic to the fraction field of ℂ[X_{1}, …, X_{n}]/A_{ℓ}. This is the function field of V_{ℓ}, denoted by ℂ(V_{ℓ});

• the ideal sat(T )_{K} coincides with T_{K}.

Thus using the Chinese Remainder Theorem, we deduce the following isomorphism:

K[X_{d+1}, …, X_{n}]/T_{K} ≃ ∏_{ℓ≤L} ℂ(V_{ℓ}).

For i in d + 1, …, n and ℓ ≤ L, let m_{i,ℓ} ∈ K[T] be the monic minimal polynomial of X_{i} in the extension K → ℂ(V_{ℓ}). We also let M_{i} be the monic minimal polynomial of X_{i} in K → K[X_{d+1}, …, X_{n}]/T_{K}. Then M_{i} is the LCM of the polynomials m_{i,ℓ}, for ℓ ≤ L.

Let now y be in ℂ^{d}, and suppose that the restriction of Π to \overline{W (T )} is not proper at y. Then there exists ℓ_{0} ≤ L such that the restriction of Π to V_{ℓ_{0}} is not proper at y. Then [27, Lemma 3.10] shows that there exists i_{0} in d + 1, …, n such that y cancels the denominator of one of the coefficients of m_{i_{0},ℓ_{0}}. By Gauss’ Lemma, y cancels the denominator of one of the coefficients of M_{i_{0}}.

On the other hand, after dividing the polynomials in T by h, we obtain polynomials in K[X_{d+1}, …, X_{n}] that are monic in their main variable. The possible necessary reductions to obtain a reduced Gröbner basis for T_{K} do not introduce new denominators. Therefore, all denominators that appear in the minimal polynomial M_{i_{0}} divide h. Thus y cancels h, which concludes the proof. □

We can now prove Theorem 2. Let D be a connected component of \overline{W (T )}∩ℝ^{n} be such that \overline{W (T )} ∩ V (s) = ∅. Then, from Lemma 3, D does not contain any critical point of Π restricted to the regular part of \overline{W (T )} nor any singular point of \overline{W (T )}. Moreover the restriction of Π to \overline{W (T )} is dominant.

Then, we can apply Theorem 1 to \overline{W (T )} and Π. Let Γ be the set of points at which the restriction of Π to \overline{W (T )} is not proper. From Lemma 4, Γ ⊂ V (h). Then, for all connected component S of ℝ^{d}\(Γ ∩ ℝ^{d}), there exists a connected component S′ of ℝ^{d} \ (V (h) ∩ ℝ^{d}) such that S′ ⊂ S. Thus, we are done. □

4 Description of the main algorithm

We now describe our main algorithm ConnectedComponents, which computes at least one point in each connected component of a real algebraic variety. Here is a rough sketch of this algorithm.

Given a family (P_{1}, …, P_{k}) ⊂ ℚ[X_{1}, …, X_{n}], we first decompose the zero-set of (P_{1}, …, P_{k}) by means of strongly normalized triangular sets (T_{1}, …, T_{ℓ}). For these triangular sets, denoted by T , we do the following:

• find a dominant projection Π by detecting the transcendental variables of T ,

• compute a set of generators of \overline{W (T )} ∩ V (s), and recursively call the algorithm for this new algebraic variety,

• compute at least one point in each connected component of the semialgebraic set defined by h ≠ 0, and study the fibers of Π above these points.

These operations are encapsulated in the following subroutines. The first of them is already described in [42]; the last one is described in Section 5.

• Decompose:

– Input: a polynomial family (P_{1}, …, P_{k}) in ℚ[X_{1}, …, X_{n}] and a lexicographic order on the variables.

– Output: couples of polynomial systems in ℚ[X_{1}, …, X_{n}], ([G_{1}, T_{1}], …, [G_{ℓ}, T_{ℓ}]) such that V (P_{1}, …, P_{k}) = ∪_{i=1}^{ℓ}V (G_{i}) and for i in {1, …, ℓ}, T_{i} is a strongly normalized triangular set such that sat(T_{i}) = ⟨G_{i}⟩.

• TranscendentalVariables:

– Input: a triangular set T ⊂ ℚ[X_{1}, …, X_{n}].

– Output: the indices of the transcendental variables of T .

• Critical:

– Input: a couple G, T of polynomial systems in ℚ[X_{1}, …, X_{n}], such that T is a strongly normalized triangular set satisfying sat(T ) = ⟨G⟩.

– Output: the reunion of G and the product of the separants of T .

• Compute-P_{Π}:

– Input: a strongly normalized triangular set T ⊂ ℚ[X_{1}, …, X_{n}].

– Output: the square-free part of the product of the initials of T .

   • SemiAlgebraicFibers:

– Input: a polynomial P in ℚ[X_{1}, …, X_{d}].

– Output: a list of points in ℚ^{d} intersecting each connected component of the semi-algebraic set defined by P ≠ 0.

With these notations, we can describe the algorithm ConnectedComponents.

                      Algorithm ConnectedComponents

• Input: a polynomial family (P_{1}, …, P_{k}) ⊂ ℚ[X_{1}, …, X_{n}].

• Output: a family of zero-dimensional systems whose set of real solutions intersects each connected component of V (P_{1}, …, P_{k}) ∩ ℝ^{n}.

1. list:=Decompose(P_{1}, …, P_{k})

    2. result:=[]

3. While list≠ [] do

• [G, T ]:=First(list), list:=list\[G, T ].

• If dim(G) = 0 then result:=result∪G

• Else

             – result:=result ∪ ConnectedComponents(Critical(G, T ))

– P_{Π}:=Compute-P_{Π}(T )

             – R:=SemiAlgebraicFibers(P_{Π})
             – I:=TranscendentalVariables(T )
             – result:=result ∪_{r∈R} ConnectedComponents(G ∪ {X_{i} − r_{i}}_{i∈I}).

4. return result.

Theorem 3 Algorithm ConnectedComponents halts. It returns a family of zero-dimensional polynomial systems whose real solutions intersect each connected component of the real algebraic set V (P_{1}, …, P_{k}) ∩ ℝ^{n}.

Proving that algorithm ConnectedComponents halts requires the following result.

Lemma 5 Let T ⊂ ℚ[X_{1}, …, X_{n}] be a regular separable triangular set, Π the projection on the affine subspace containing the axes of the transcendental variables of T and y a point in this subspace. Then the dimension of \overline{W (T )}∩ Π^{−1}(y) is less than the dimension of \overline{W (T )}.

Proof. Suppose on the contrary that \overline{W (T )}∩Π^{−1}(y) has the same dimension as \overline{W (T )}. This implies that there exists an irreducible component V′ of \overline{W (T )} such that dim(Π^{−1}(y) ∩ V′) = dim(V′). Thus, since V′ is irreducible, for all x ∈ V′, Π(x) = y. This contradicts the fact that the restriction of Π to V′ is dominant. □

We can then prove Theorem 3. We proceed by induction on the dimension d of V (P_{1}, …, P_{k}). If d = 0, then halting and correctness are readily verified. So we may consider that this is also the case for 0, …, d − 1, and prove that halting and correctness hold in dimension d.

First, we prove that the algorithm ends. It is enough to show that all recursive calls are done on systems of dimension less than d, but this assertion is precisely the content of Lemma 2 and Lemma 5. Thus, we conclude by proving correctness.

Let D be a connected component of V (P_{1}, …, P_{k}) ∩ ℝ^{n}. There exists a couple of polynomial families [G, T ] in Decompose(P_{1}, …, P_{k}) such that D contains a connected component D′ of V (G). Consider the pass in the while loop corresponding to [G, T ]. If G has dimension zero, then the conclusion obviously holds.

Else, suppose D′ ∩ V (s) (where s is the product of the separants of T ) is not empty, let I be the set of indices of transcendental variables of T , and Π be the projection on these variables. Then, there exists a connected component of the real algebraic variety defined by the output of Critical([G, T ], I) which is contained in D′.

Now, suppose D′ ∩ V (s) = ∅. Then, from Theorem 2, there exists a connected component S of the semi-algebraic set defined by h ≠ 0 (where h is the product of the initials of T ) contained in Π(D′). Then the output of SemiAlgebraicFibers(h) contains a point y such that y ∈ Π(D). Thus, V (G ∩ V (Π^{−1}(y)) meets D′. This proves the theorem. □

5 Studying the complementary of an hypersurface

In this section, we present an algorithm with the following specification:

• Input: a polynomial P in ℚ[X_{1}, …, X_{d}].

• Output: a finite set of points in ℚ^{d} which intersects each connected component of the semi-algebraic set defined by P ≠ 0.

This algorithm is based on the projection step of cylindrical algebraic decomposition [12], and thus inherits its doubly exponential complexity. On the other hand, this algorithm is easy to implement, and most of our experiments took place in low dimension d, where its practical behavior was quite satisfying.

Consider the order on the variables X_{1} < ⋯ < X_{d}. We denote by PROJCAD the subroutine whose specification is:

• Input: a finite set of polynomials (P_{1}, …, P_{k}) ⊂ ℚ[X_{1}, …, X_{d}].

• Output: if d = 1, (P_{1}, …, P_{k}); else a list of polynomials in ℚ[X_{1}, …, X_{d−1}] containing:

– all the non-zero coefficients of all the polynomials P ∈ (P_{1}, …, P_{k}) when they are considered as univariate in X_{d},

– all the non-zero subresultant coefficients associated to all the couples of polynomials (P_{i}, P_{j}) ⊂ (P_{1}, …, P_{k})^{2}, when these polynomials are considered as univariate in X_{d},

– all the non-zero subresultant coefficients associated to all the couples (P, ∂P/∂X_{d}) where P ∈ (P_{1}, …, P_{k}) is considered as univariate in X_{d}.

Proposition 1 Let (P_{1}, …, P_{k}) ⊂ ℚ[X_{1}, …, X_{d}] for d > 1, S a semialgebraic set defined by:

P_{1} σ_{1} 0, …, P_{k} σ_{k} 0, where σ_{i} ∈ {>, <},

and S a connected component of S.

Consider (Q_{1}, …, Q_{ℓ}) = PROJCAD([P_{1}, …, P_{k}]) and Π : ℝ^{d} → ℝ^{d−1} the projection on the affine subspace containing the axis of X_{1}, …, X_{d−1}. There exists Σ′ ∈ {>, <}^{ℓ} and a connected component S′ of the semi-algebraic set defined by:

Q_{1} σ′_{1} 0, …, Q_{ℓ} σ′_{ℓ} 0, where (σ′_{1}, …, σ′_{ℓ}) = Σ′

such that S′ ⊂ Π(S).

Proof. From [13, Theorem 2.12, page 26], if C is a connected subset of ℝ^{d−1} on which the sign of the polynomials in PROJCAD([P_{1}, …, P_{k}]) is constant, there exist semi-algebraic and continuous functions ξ_{1}, …, ξ_{ℓ} : C → ℝ such that the graphs of the ξ_{i} or the bands of the cylinders between these graphs are connected semi-algebraic sets on which the signs of (P_{1}, …, P_{k}) is constant.

Thus, if C ∩ Π(S) ≠ ∅, then either one of these graphs or one of these bands is contained in S. Thus, C ⊂ Π(S).

Now, consider the finite family of all connected components of the semialgebraic sets defined by all the admissible sign conditions on the polynomials in PROJCAD([P_{1}, …, P_{k}]). This defines a partition of ℝ^{d−1}. The above reasoning shows that Π(S) is the union of some of these connected components.

Since Π(S) has dimension d − 1, there exists one of these connected components on which all polynomials in PROJCAD([P_{1}, …, P_{k}]) never vanish. This ends the proof. □

This proposition yields the following lifting process from ℝ^{ℓ−1} to ℝ^{ℓ}. Consider (Q_{1}, …, Q_{k}) ⊂ ℚ[X_{1}, …, X_{ℓ}], and a list of points ℝ ⊂ ℚ^{ℓ−1} intersecting each connected component of the semi-algebraic set of ℝ^{ℓ−1} defined by:

∀Q ∈ PROJCAD([Q_{1}, …, Q_{k}]), Q ≠ 0.

Then computing one rational value between each real root of Q_{1}, …, Q_{k} above each point r ∈ R_{ℓ−1} gives one point in each connected component of the semi-algebraic set in ℝ^{ℓ−1} defined by

Q_{1} ≠ 0, …, Q_{k} ≠ 0.

Let now (P_{1}, …, P_{k}) be polynomials in ℚ[X_{1}, …, X_{d}]. By iterating the operator PROJCAD, we obtain a finite set of univariate polynomials L. Computing at least one point in each connected component of the semi-algebraic set defined by ∀Q ∈ L, Q ≠ 0 is immediate. We can then deduce one point in each connected component of the semi-algebraic set in ℝ^{d} defined by

P_{1} ≠ 0, …, P_{k} ≠ 0

by iterating the above lifting process.

6 Experimental results

In this section, we present the experimental results of a first implementation

of the algorithm ConnectedComponents.

6.1 Methodology

In [4], the authors propose an algorithm computing at least one point on each connected component of a real algebraic set, which is based on the computation of the critical points of a distance function and treats the singular case by the iterated study of the nested singular loci. In [39], it turned out to perform better on a series of examples that the one proposed in [38]. So, we will compare ConnectedComponents with this algorithm.

As explained in the introduction, algorithms computing one point in each connected component of a real algebraic set are basic tools to decide the emptiness of semi-algebraic sets. This motivates the fact that we will not only focus on the computation times but also on the quality of the output, expressed as the sum of the degrees of the zero-dimensional systems we obtain, and the maximum of these degrees.

The polynomial systems used to perform these experiments come from academic or industrial applications. Most of them can be found in the FRISCO test-suite, see [10].

6.2 Software

The following subroutines are shared by ConnectedComponents and the algorithm proposed in [4].

• Decompose: this subroutine is implemented by splitting lexicographic Gröbner bases using the techniques of [2] as described in [42]. The Gröbner bases computations are done using the software AGb, implemented in C++ by J.-C. Faugère.

• ZeroDimensionalSolving: this algorithm takes a Gröbner base generating a zero-dimensional ideal and computes a Rational Univariate Representation via the algorithm proposed in [37] from which the isolation of real roots is performed. The software used to perform these computations is RS, which is implemented in C by F. Rouillier.

The layout of the algorithms is implemented in the Computer Algebra System Maple. For the algorithm proposed in [4], it manages the computation of the minors of a jacobian matrix characterizing the critical points of a distance function. For the algorithm ConnectedComponents, it manages the subresultant computations required to implement the subroutine

SemiAlgebraicFibers.

Table 1: Computation times

    System Vars/Dim/Degree Distance  ConnectedComponents

Neural  4/1/24  8  10
Wang  10/1/114  10  17
Buchberger  8/4/6  10  6
Butcher  8/3/3  9  6
Vermeer  5/1/26  3  6
Donati  4/1/10  3  3
Euler  10/3/2  12  15
DiscPb  4/2/4  940  45
Prodecco  5/2/2  137  137
Hairer-2  13/2/25  ∞  32
F633  10/2/32  ∞  91
F744  12/1/40  ∞  80
F855  14/1/52  ∞  1020

Maple is linked to AGb and RS via the Gb/Maple interface package provided by J.-C. Faugère.

The computations have been performed on a Bi-Pentium III 800 MHz with 1 Go of RAM.

6.3 Results

In Table 1, we give the computations times of the algorithm proposed in [4], which is named Distance in the tables, and the algorithm ConnectedComponents. The timings are given in seconds, and they include the isolation of the real solutions of the zero-dimensional systems. We precise the number of variables, and the dimension and the degree of the ideal generated by all systems. The sign ∞ means that no result was obtained after 2 days of computation.

For these systems, the algorithm ConnectedComponents solves more problems than the one proposed in [4]. Moreover, the computation times are almost always better for our algorithm.

The following discussion gives a partial explanation for this behavior. The critical locus of a regular application is characterized by the vanishing of minors in a jacobian matrix. In the case of the algorithm ConnectedComponents, this jacobian matrix is triangular, thus no linear algebra is required and a factorization of such minors is immediately obtained. For the algorithm pro-

Table 2: Size of the output

     System  Distance          ConnectedComponents

Neural  225 [54, 44, 36, 21,  222 [54, 12^{2}, 36, 21, 15^{2},
15^{3}, 13, 6^{2}]  8^{2}, 6^{4}, 4^{2}, 3^{3}]
Wang 168 [48, 24, 12^{8}] 144 [32^{2}, 8^{2}, 4^{16}]
Buchberger 53 [12, 10, 6^{2}, 5, 4^{2}, 2, 1^{4}]  13 [2^{6}, 1]
Butcher  14 [3, 2, 1^{9}]  6 [3, 2, 1]
Vermeer  84 [38^{2}, 8]  56 [8^{5}, 6^{2}, 4]
Donati  175 [175]  119 [41, 20, 10^{5}, 8]
Euler  29 [7^{2}, 4, 2, 1^{9}]  11 [1^{11}]
DiscPb 1235 [477, 371, 170, 119,  74 [15, 8^{2}, 4^{7}, 2^{7}, 1]

51, 15, 7^{4}, 3, 1]

Prodecco 58 [36, 18, 1^{4}] 55 [36, 18, 1]
Hairer-2  44 [1^{44}]
F633  220 [6^{3}, 4^{9}, 3^{2}, 2^{75}, 1^{10}]
F744  216 [24, 16, 12^{6}, 9^{2}, 4^{20}, 3^{2}]
F855  298 [24, 16, 12^{7}, 9^{2}, 6, 4^{36}, 3^{2}]

posed in [4], the jacobian matrix is not triangular. The computation of the required minors is not a limitating step, but their size does not allow their exploitation in an elimination algorithm. For example, for the system F744, the minors have about 10000 monomials and degree 54.

On these systems, the execution time of the subroutine SemiAlgebraicFibers is negligible before the rest of the execution time. Indeed, on these examples, the initials of the triangular sets have low degrees and low number of variables.

Now, let us compare the size of the output of the algorithms we consider. In Table 2 and Table 3, we give respectively the degrees of the zero-dimensional systems we obtain, and the number of real solutions.

For both algorithms, the first number given in Table 2 is the sum of the degrees of the zero-dimensional systems. It is followed by the list of the degrees of these systems in a decreasing order. In this list, a notation such as δ^{n} indicates the presence of n systems of degree δ.

On these examples, algorithm ConnectedComponents returns a set of zerodimensional systems whose sum of degrees is always less than the one returned by the algorithm proposed in [4]. Moreover, the same remark holds for the maximum degree of the zero-dimensional systems returned by both

Table 3: Number of real solutions

System Distance ConnectedComponents
Neural  59  56
Wang  16  16
Buchberger  21  7
Butcher  12  4
Vermeer  24  20
Donati  8  11
Euler  19  11
DiscPb  54  24
Prodecco  28  25
Hairer-2  44
F633  162
F744  52
F855  192

algorithm, up to one example. Thus, the output of algorithm ConnectedComponents seems to be more exploitable than the one of algorithm proposed in [4].

References

[1] M. E. Alonso, E. Becker, M.-F. Roy, and T. Wörmann. Zeroes, multiplicities and idempotents for zerodimensional systems. In Algorithms in Algebraic Geometry and Applications. Proceedings MEGA’94, volume 142 of Progress in Mathematics, pages 1–15. Birkhäuser, 1996.

[2] P. Aubry. Ensembles triangulaires de polynômes et résolution de systèmes algébriques. PhD thesis, Université Paris 6, 1999.

[3] P. Aubry, D. Lazard, and M. Moreno Maza. On the theories of triangular sets. Journal of Symbolic Computation, Special Issue on Polynomial Elimination, 28:105–124, 1999.

[4] P. Aubry, F. Rouillier, and M. Safey El Din. Real solving for positive dimensional systems. Rapport de recherche, Laboratoire d’Informatique de Paris 6, September 2000.

[5] B. Bank, M. Giusti, J. Heintz, and G.-M. Mbakop. Polar varieties and efficient real equation solving : the hypersurface case. Journal of complexity, 13(1):5–27, 1997.

[6] B. Bank, M. Giusti, J. Heintz, and G.-M. Mbakop. Polar varieties and efficient real elimination. Mathematische Zeitschrift, 238(1):115–144, 2001.

[7] S. Basu. Algorithms in semi-algebraic geometry. PhD thesis, New-York University, 1996.

[8] S. Basu, R. Pollack, and M.-F. Roy. On the combinatorial and algebraic complexity of quantifier elimination. Journal of ACM, 43(6):1002–1045, 1996.

[9] S. Basu, R. Pollack, and M.-F. Roy. A new algorithm to find a point in every cell defined by a family of polynomials. In B. Caviness and J. Johnson, editors, Quantifier elimination and cylindrical algebraic decomposition, Texts and monographs in symbolic computation. Springer-Verlag, 1998.

[10] D. Bini and B. Mourrain. The frisco test-suite.

http://www-sop.inria.fr/saga/POL/, 2000.

[11] B. Buchberger. Gröbner bases: An algoritmic method in polynomial ideal theory. In Multidimensional System Theory, pages 374–383. Reidel, Dordrecht, 1985.

[12] G. E. Collins. Quantifier elimination for real closed fields by cylindrical algebraic decomposition. Lecture notes in computer science, 33:515–532, 1975.

[13] M. Coste. Introduction à la géométrie semi-algébrique. Polycopié, Institut de Recherche Mathématique de Rennes.

[14] I. Z. Emiris and B. Mourrain. Matrices in elimination theory. Journal of Symbolic Computation, 28(1-2):3–43, 1999.

[15] J.-C. Faugère. A new efficient algorithm for computing Gröbner bases (F_{4}). Journal of Pure and Applied Algebra, 139(1-3):61–88, 1999. Effective methods in algebraic geometry (Saint-Malo, 1998).

[16] J.-C. Faugère. A new efficient algorithm for computing Gröbner bases without reduction to zero (F5). In Proceedings of ISSAC 2002, pages 75 – 83. ACM Press, 2002.

[17] J.-C. Faugère, F. Moreau de Saint Martin, and F. Rouillier. Design of regular nonseparable bidimensional wavelets using groebner basis techniques. IEEE SP Transactions, Special Issue on Theory and Applications of Filter Banks and Wavelets, 46(4):845–856, April 1998.

[18] J.C. Faugère, P. Gianni, D. Lazard, and T. Mora. Efficient computation of zero-dimensional Gröbner bases by change of ordering. Journal of Symbolic Computation, 16(4):329–344, 1993.

[19] M. Giusti, K. Hägele, J. Heintz, J.-E Morais, J.-L. Montaña, and L.-M. Pardo. Lower bounds for Diophantine approximation. In Proceedings of MEGA’96, number 117, 118 in Journal of Pure and Applied Algebra, pages 277–317, 1997.

[20] M. Giusti, J. Heintz, J.-E. Morais, J. Morgenstern, and L.-M. Pardo. Straight-line programs in geometric elimination theory. Journal of Pure and Applied Algebra, 124:101–146, 1998.

[21] M. Giusti, J. Heintz, J.-E. Morais, and L.-M. Pardo. When polynomial equation systems can be solved fast? In Proceedings of AAECC-11, volume 948 of Lecture Notes in Computer Science, pages 205–231. Springer, 1995.

[22] M. Giusti, G. Lecerf, and B. Salvy. A Gröbner free alternative for polynomial system solving. Journal of Complexity, 17(1):154–211, 2001.

[23] D. Grigoriev and N. Vorobjov. Solving systems of polynomials inequalities in subexponential time. Journal of symbolic computation, 5:37–64, 1988.

[24] J. Heintz, M.-F. Roy, and P. Solerno. On the complexity of semialgebraic sets. In Proceedings IFIP, 1989.

[25] J. Heintz, M.-F. Roy, and P. Solerno. On the theoretical and practical complexity of the existential theory of the reals. The Computer Journal, 36(5):427–431, 1993.

[26] E. Hubert. Notes on triangular sets and triangulation-decomposition algorithms I:Polynomial systems. In F. Winkler, editor, Symbolic and Numerical Scientific Computations. Springer, to appear.

[27] Z. Jelonek. Testing sets for properness of polynomial mappings. Mathematische Annalen, 315(1):1–35, 1999.

[28] M. Kalkbrener. Three contributions to elimination theory. PhD thesis, Kepler University, Linz, 1991.

[29] D. Lazard. A new method for solvong algebraic systems of positive dimension. Disc. Appl. Math., 33:147–160, 1991.

[30] D. Lazard. Solving zero-dimensional algebraic systems. Journal of symbolic computation, 13:117–133, 1992.

[31] D. Lazard. Stewart platform and Gröbner bases. In Parenti-Castelli V. and Lenaric J., editors, Proceedings of the third international workshop on advances of robot kinematics, pages 136–142. Ferrare, 1992.

[32] F. Lemaire. Contribution à l’algorithmique en algèbre différentielle. PhD thesis, Université des Sciences et Technologies de Lille, 2002.

[33] M. Moreno Maza and R. Rioboo. Polynomial gcd computations over tower of algebraic extensions. In G. Cohen, M. Giusti, and T. Mora, editors, Proceedings AAECC-11, number 948 in Lecture Notes in Computer Science, pages 365–382. Springer, 1995.

[34] M. Moreno Maza. Calculs de pgcd au-dessus des tours d’extensions simples et résolution des systèmes d’équations algébriques. PhD thesis, Université Paris 6, 1997.

[35] S. Morrison. The differential ideal [P] : M^{∞}. J. Symb Comp., 28:631– 656, 1999.

[36] R. Rioboo. Towards faster real algebraic numbers. In Proceedings of ISSAC 2002, pages 221–228. ACM Press, 2002.

[37] F. Rouillier. Solving zero-dimensional systems through the rational univariate representation. Journal of Applicable Algebra in Engineering, Communication and Computing, 9(5):433–461, 1999.

[38] F. Rouillier, M.-F. Roy, and M. Safey El Din. Finding at least one point in each connected component of a real algebraic set defined by a single equation. Journal of Complexity, 16:716–750, 2000.

[39] F. Rouillier, M. Safey El Din, and É. Schost. Solving the birkhoff interpolation problem via the critical point method : an experimental study. In Proceedings of ADG’2000, 2000.

[40] F. Rouillier and P. Zimmermann. Efficient Isolation of a Polynomial Real Roots. Rapport de recherche, INRIA, February 2001.

[41] M.-F. Roy. Basic algorithms in real algebraic geometry : from sturm’s theorem to the existential theory of reals. In Lectures on real geometry in memoriam of Mario Raimondo, volume 23 of Expositions in mathematics, pages 1–67. New-York, de Gruyter, 1996.

[42] M. Safey El Din. Résolution réelle des systèmes polynomiaux de dimension positive. PhD thesis, Université Paris 6, January 2001.

[43] J. Uspensky. Theory of equations. Mc Graw-Hill, 1948.

[44] J. Verschelde. Algorithm 795: Phcpack: A general-purpose solver for polynomial systems by homotopy continuation. ACM Transactions on Mathematical Software, 25(2):251–276, 1999.

[45] D. Wang. An elimination method for polynomial systems. J. Symb. Comp., 16:83–114, 1993.

[46] D. Wang. Elimination Methods. Springer Verlag, 2001.