Exceptional sets and fiber products

Andrew J. Sommese^{∗}  Charles W. Wampler^{†}

January 31, 2007

Abstract

Exceptional sets where fibers have dimensions higher than the generic fiber dimension are of interest in mathematics and in application areas, such as the theory of overconstrained mechanisms. We show that fiber products promote such sets to become irreducible components, whereupon they can be found using techniques from numerical algebraic geometry for computing the irreducible decomposition. However, such a decomposition may contain components other than the exceptional loci we seek. We show that each irreducible component of the exceptional loci gives rise to a main component in a fiber product of sufficiently high order, and we give procedures for identifying these components. The methods are illustrated by finding the rulings of a general quadric in ℂ^{3}. 2000 Mathematics Subject Classification. Primary 65H10; Secondary 14Q99, 68W30. Key words and phrases. Components of solutions, exceptional loci of algebraic maps, fiber products, homotopy continuation, irreducible components, numerical algebraic geometry, polynomial system, overconstrained mechanisms.

∗Department of Mathematics, University of Notre Dame, Notre Dame, IN 46556-4618, USA Email: sommese@nd.edu URL: http://www.nd.edu/∼sommese. This material is based upon work supported by the National Science Foundation under Grant No. 0105653 and Grant No. 0410047; the Duncan Chair of the University of Notre Dame; and the Institute for Mathematics and its Applications in Minneapolis (IMA)

†General Motors Research and Development, Mail Code 480-106-359, 30500 Mound Road, Warren, MI 48090-9055, U.S.A. Email: Charles.W.Wampler@gm.com. This material is based upon work supported by the National Science Foundation under Grant No.

0410047; General Motors Research and Development; and the Institute for Mathematics and its Applications in Minneapolis (IMA).

Introduction

Systems of polynomials on ℂ^{N+m} of the form

f(v; p) = [ f_{1}(v; p) ; ⋮ ; f_{n}(v; p) ] = 0,  (1)

where v ∈ ℂ^{N} are regarded as variables and p ∈ ℂ^{m} are regarded as parameters, arise naturally in engineering. For a particular p^{∗} ∈ ℂ^{m}, the fiber over p^{∗} is just the solution set of f(v; p^{∗}) = 0. It is a fundamental problem to compute the set of points (v; p) where the dimension of the fiber over p is a given nonnegative integer.

Our motivation for studying this problem is the classification of overconstrained mechanisms, e.g., [4, 14]. In that case, the parameters are quantities that will be constant once one builds the mechanism (such as the length of a link), the variables are joint displacements (such as the rotation of a hinge), and f(v; p) = 0 is the set of conditions that allow the links to be assembled, i.e., the loop closure equations. The fiber over a particular p^{∗} is the set of all joint configurations that the mechanism with parameters p^{∗} can attain. This set may consist of several irreducible components, i.e., different assembly modes, and the dimension of each irreducible component is the number of degrees of freedom of the mechanism in that assembly mode. As the parameters vary continuously, the number of assembly modes and their degrees of freedom stay constant on a Zariski open subset of the parameter space, but when the parameters satisfy certain additional algebraic conditions, the number of degrees of freedom of some assembly mode may increase. A generic point in a set of the type we seek corresponds to a mechanism in an assembly mode having a specified number of degrees of freedom.

We approach this problem by means of fiber products. For example, letting X ⊂ ℂ^{N+m} be the solution set of f(v; p) = 0 and letting π : X → Y := ℂ^{m} denote the projection induced by (v; p) ↦ p, we wish to find the decomposition of the set of points (v; p) ∈ ℂ^{N+m} where dim_{(v;p)} π^{−1}(p) = h for a given h. A key step in our approach is to form the fiber product X×_{Y} X of X with itself over Y, which is the set of solutions of the “doubled” system

[ \begin{matrix}f(v; p) \\ f(v′; p) \end{matrix} ] = 0  (2)

in the variables (v; v′; p) ∈ ℂ^{2N+m}. As we shall show, the operation of forming repeated fiber products has the effect of promoting certain interesting sets on X for the map π into irreducible components.

This property of repeated fiber products is key to our approach because of the existence of practical numerical methods for finding all irreducible components of the solution set of a polynomial system [7, 8, 13], one of the central problems of the field of numerical algebraic geometry, inaugurated in [12]. Consequently, a numerical algorithm for solving our problem can be constructed by forming repeated fiber products using multiple copies of the system in the pattern of Eq. 2 and then numerically finding the irreducible components of the resulting system’s solution set. For background on the use of homotopy continuation to solve polynomial systems, we suggest [3, 13]. Another very different symbolic approach in the case when the fibers are zero dimensional may be found in [1].

The scheme of the article is as follows.

In §1, we define, for a map π : X → Y between algebraic sets, the exceptional loci D_{h}(π) of points and fiber products ∏_{Y}^{k} X. We give examples showing how fiber products pick out exceptional sets. D_{h}(π) is the closure of points x of X where the fiber of π through x is h dimensional at x.

In §2, we present the theory underlying the algorithm, beginning with the definition of the main component of a fiber product. Given an algebraic map π : X → Y, Theorem 2.7 gives a quick way of checking when an irreducible algebraic subset W of a fiber product Π_{Y}^{k} X is a main component Z_{π}^{k} of an irreducible algebraic subset Z of X. A main result Corollary 2.14 we prove is that, given an irreducible component Z ⊂ D_{h}(π) for an algebraic map π : X → Y between irreducible algebraic sets satisfying \overline{π(X)} = Z, the main component Z_{π}^{k} of Z in the k-th fiber product ∏_{Y}^{k} X is an irreducible component for k sufficiently large, e.g., k ≥ codZ + 1. In Theorem 2.17, we prove an occasionally useful lower bound in the special case when X and Y are the same dimension. We show how to recognize the main component amongst the many possible components of the fiber product of the solution set of a system and how to recover the exceptional locus from its own fiber product.

In §3, we present numerical algorithms for finding exceptional loci based on the results of §2.

In §4, we illustrate the methodology on a simple example, numerically demonstrating the classical result that a quadric in ℂ^{3} is a doubly ruled surface.

Finally, in an Appendix, §A, we recall some background definitions and prove some lemmas about algebraic sets and mappings that are used in the article.

We would like to thank the referees for their helpful comments.

1 Exceptional loci of mappings and fiber products

We are interested in the irreducible components of certain exceptional loci associated to algebraic mappings between complex algebraic sets. The most important cases are maps between affine algebraic sets and maps between projective algebraic sets since these are what occur for applications. For this reason algebraic sets for us will always mean quasiprojective algebraic sets, i.e., algebraic sets of the form A \ B where B is a projective algebraic subset of a projective algebraic set A. We follow the convention that if π : X → Y is a map, and if Z ⊂ X is a subset, then π_{Z} denotes the restriction of π to Z. We have collected some definitions and facts we need in Appendix A.

Given an algebraic map π : X → Y between algebraic sets, we define D_{h}(π) to be the closure of the set of points x ∈ X such that dim_{x} π^{−1}(π(x)) = h. The sets D_{h}(π) are closed algebraic subsets of X. Moreover, by upper semicontinuity of dimension, e.g., [5, Corollary 3.16], [13, Theorem A.4.5], dim_{x} π^{−1}(π(x)) ≥ h for all x ∈ D_{h}(π).

Problem 1.1 For a given h, compute D_{h}(π) and decompose it into irreducible components.

The basic problem is that the irreducible components of D_{h}(π) are usually not irreducible components of X.

Example 1.2 Consider the system

[ \begin{matrix}p_{1} − v_{1} \\ p_{2} − v_{1}v_{2} \end{matrix} ] = 0.  (3)

The set of solutions X is isomorphic to ℂ^{2} under the map sending (z_{1}, z_{2}) ∈ ℂ^{2} to (v; p) = (z_{1}, z_{2}; z_{1}, z_{1}z_{2}) ∈ ℂ^{4}. Letting π : X → ℂ^{2} be the map induced by sending (v; p) ↦ p ∈ ℂ^{2}, we see that π(X) is dense in ℂ^{2} but not equal to ℂ^{2}. The inverse image of any point p = (p_{1}, p_{2}) ∈ ℂ^{2} with p_{1} ≠ 0 is the single point (v; p) = (p_{1}, p_{2}/p_{1}; p_{1}, p_{2}). The closure of the set of such points is D_{0}(π), which equals X. The exceptional point (0, 0) has the one-dimensional inverse image π^{−1}(0, 0) = {(0, z_{2}; 0, 0), z_{2} ∈ ℂ}, which is D_{1}(π). Since D_{1}(π) ⊂ D_{0}(π), D_{1}(π) is not an irreducible component of X.

The goal of this article is to establish an algorithm (based on the operation of taking fiber products) for solving Problem 1.1.

Given two algebraic maps π_{1} : X_{1} → Y, π_{2} : X_{2} → Y from algebraic sets X_{1}, X_{2} to an algebraic set Y, the fiber product

X_{1} ×_{Y} X_{2}

of X_{1} with X_{2} over Y is defined to be the algebraic set (π_{1} ×π_{2})^{−1}(Δ) where

1. Δ is the diagonal of Y × Y consisting of all points of the form (y, y) ∈ Y × Y; and

2. π_{1} × π_{2} is the induced map X_{1} × X_{2} → Y × Y.

Under the map (y, y) ↦ y, Δ is identified with Y and the composition of this map with π_{1} × π_{2} induces an algebraic map Π : X_{1} ×_{Y} X_{2} → Y. The fiber of Π over y ∈ Y is isomorphic to π_{1}^{−1}(y) × π_{2}^{−1}(y). Note that if there is an algebraic set W ⊂ Y such that π_{i}(X_{i}) ⊂ W for i = 1, 2, then X_{1} ×_{Y} X_{2} is isomorphic to X_{1} ×_{W} X_{2}.

Given k algebraic maps π_{i} : X_{i} → Y from algebraic sets X_{1}, …, X_{k} to an algebraic set Y, we can similarly define the fiber product (∏_{i=1}^{k} X_{i})_{Y}. We denote the induced projection of (∏_{i=1}^{k} X_{i})_{Y} onto the i-th factor by q_{i}.

When the X_{i} are all the same space X and the maps π_{i} are all the same map π : X → Y, we denote the k-th fiber product of X with itself over Y by ∏_{Y}^{k} X. As above, the map from ∏_{Y}^{k} X → X to the i-th factor is denoted q_{i}. The induced map from ∏_{Y}^{k} X → Y is denoted by Π_{k}, or simply by Π when k is clear from the context.

It is easy to describe the fiber product in terms of explicit systems of equations when the maps and algebraic sets coming into the definition are each described by a polynomial system of the form of Eq. 1. That is, we have, for i = 1, 2, polynomial systems f_{1}(v_{1}; p) = 0 and f_{2}(v_{2}; p) = 0 defined for (v_{i}; p) ∈ ℂ^{N_{i}} × ℂ^{m} giving rise to the maps π_{i} : X_{i} → ℂ^{m}. Letting Y = ℂ^{m}, the fiber product X_{1} ×_{Y} X_{2} is the affine algebraic subset of ℂ^{N_{1}} × ℂ^{N_{2}} × ℂ^{m} defined by

[ \begin{matrix}f_{1}(v_{1}; p) \\ f_{2}(v_{2}; p) \end{matrix} ] = 0  (4)

Higher fiber products, such as X_{1} ×_{Y} X_{2} ×_{Y} X_{3}, can be formulated in an analogous way.

Let us see what happens when we take the fiber product of the system given by Eq. (3) in Example 1.2 with itself.

Example 1.3 The fiber product of the system (3) with itself is

[ \begin{matrix}p_{1} − v_{11} \\ p_{2} − v_{11}v_{12} \\ p_{1} − v_{21} \\ p_{2} − v_{21}v_{22} \end{matrix} ] = 0.  (5)

The solution set of this system has two components:

1. (v_{11}, v_{12}; v_{21}, v_{22}; p_{1}, p_{2}) = {(λ, μ; λ, μ; λ, λμ), (λ, μ) ∈ ℂ^{2}}; and

2. (v_{11}, v_{12}; v_{21}, v_{22}; p_{1}, p_{2}) = {(0, λ; 0, μ; 0, 0), (λ, μ) ∈ ℂ^{2}}.

We see that these components correspond to the sets D_{0}(π) and D_{1}(π), respectively, in Example 1.2, but unlike D_{0}(π) and D_{1}(π), the second component here is not contained in the first.

Building on this example, we will see that we can solve Problem 1.1 by using fiber products.

Other exceptional loci also get picked out by using fiber products. Although we will not pursue it further in this article, let us give an example of this phenomena.

Example 1.4 Consider the classical example of a cubic curve with a simple node.

[ \begin{matrix}y_{1} − x^{2} + 1 \\ y_{2} − x^{3} + x \end{matrix} ] = 0.  (6)

This corresponds to the map π : ℂ → K, given by (x) ↦ (x^{2} − 1, x^{3} − x), where K ⊂ ℂ^{2} is the irreducible cubic y_{2}^{2} = y_{1}^{3} + y_{1}^{2}. Note the map gives a biholomorphism of ℂ \ {−1, 1} with K \ {(0, 0)}, and π(−1) = π(1) = (0, 0). Thus all fibers are 0-dimensional and D_{0}(π) is the whole solution set. But notice that the fiber product of the system (6) with itself

\begin{matrix}y_{1} − x_{1}^{2} + 1 \\ y_{2} − x_{1}^{3} + x_{1} \\ y_{1} − x_{2}^{2} + 1 \\ y_{2} − x_{2}^{3} + x_{2} \end{matrix}

has a solution set (x_{1}; x_{2}; y_{1}, y_{2}) = {(λ; λ; λ^{2}−1, λ^{3}−λ), λ ∈ ℂ} that projects to the whole curve K and additionally has two isolated points (1; −1; 0, 0) and (−1; 1; 0, 0) that project to the origin. Thus, the fiber product of the system with itself picks out the point (y_{1}, y_{2}) = (0, 0) where the number of points in the fiber π^{−1}(y) is greater than the number of points in the general fiber.

2 Using fiber products to pick out exceptional loci

In this section we assume that π : X → Y is an algebraic map between algebraic sets. We must keep track of certain irreducible sets in fiber products of X with itself. We start with some results on the behavior of irreducible sets under the operation of taking fiber products.

2.1 The main component of a fiber product

Given an algebraic map π : X → Y between algebraic sets, recall that we denote the k-fold fiber product

\underbrace{X ×_{Y} ⋯ ×_{Y} X}_{k factors}

by ∏_{Y}^{k} X. As we saw above in Example 1.3, if X is irreducible, it does not follow that ∏_{Y}^{k} X is irreducible. Nevertheless, given any irreducible algebraic subset Z of X, there is an irreducible algebraic subset Z_{π}^{k} of the fiber product ∏_{Y}^{k} Z ⊂ ∏_{Y}^{k} X that is in a precise sense the main component of ∏_{Y}^{k} Z. Using the natural inclusion ∏_{Y}^{k} Z ⊂ ∏_{Y}^{k} X, we regard Z_{π}^{k} as an algebraic subset of ∏_{Y}^{k} X. In the case that Z is an irreducible component of X, then Z_{π}^{k} is an irreducible component of the fiber product ∏_{Y}^{k} X. A main result of this article Corollary 2.14 guarantees that if Z is an irreducible component of D_{h}(π), then Z_{π}^{k} is an irreducible component of the fiber product ∏_{Y}^{k} X for k sufficiently large, e.g., for k ≥ codZ + 1.

Definition/Construction 2.1 Let us now give a definition/construction of the main component. Let Z be an irreducible algebraic set and let π : Z → Y be an algebraic map from Z to an algebraic set Y. Note that generically Z is smooth and π_{Z} : Z → π(Z) is well behaved. Precisely, by [13, Theorem A.4.20], there exists a Zariski open dense set U ⊂ Z such that

1. U consists of smooth points;

2. W := π(U) is a Zariski open dense set of \overline{π(Z)} consisting of smooth points;

3. π_{U} is of maximal rank;

4. π_{U} factors as the composition π_{U} = s ∘ r, where r : U → V is an algebraic map onto a quasiprojective manifold V with connected fibers, and s : V → W is a covering map.

The inclusion map i_{U} of U into Z induces an inclusion map of ∏_{W}^{k} U into ∏_{Y}^{k} Z. Since ∏_{V}^{k} U is a subset of ∏_{W}^{k} U, we have an embedding I_{U}^{k} : ∏_{V}^{k} U → ∏_{Y}^{k} Z. We define the main component Z_{π}^{k} of Z in ∏_{Y}^{k} Z to be the closure of the image under this inclusion of ∏_{V}^{k} U in ∏_{Y}^{k} Z.

Remark 2.2 Note that Z_{π}^{1} is simply Z and that the main component, U_{π}^{k}, of U in ∏_{W}^{k} U is by construction the image of ∏_{V}^{k} U in ∏_{W}^{k} U under the natural inclusion I_{U}^{k}.

Before we go further let us give an example of a main component. Let Z denote ℂ^{2} and Y be isomorphic to ℂ. Let f : Z → Y be the algebraic map (z_{1}, z_{2}) → z_{1}^{2}. Here U is the set of points on ℂ^{2} with nonzero first coordinate; W and V are both isomorphic to ℂ^{∗}, the set of nonzero complex numbers. The map r : U → V is given by r(z_{1}, z_{2}) = z_{1} and the map s : V → W is given by s(v) = v^{2}. The main component of Z ×_{Y} Z consists of all points (z_{1}, z_{2}; z′_{1}, z′_{2}) ∈ ℂ^{4} with z_{1} = z′_{1}. Note there is a second component of the fiber product consisting of all points (z_{1}, z_{2}; z′_{1}, z′_{2}) ∈ ℂ^{4} with z_{1} = −z′_{1}.

The first fact about the main component of an irreducible algebraic set is that it is an irreducible algebraic set.

Lemma 2.3 Let Z be an irreducible algebraic subset and let π : Z → Y be an algebraic map from Z to an algebraic set Y. Then the main component Z_{π}^{k} is irreducible.

Proof. We use the notation of the Definition/Construction 2.1. Since Z is irreducible, U is connected. Since V is connected with r having connected fibers, it follows that ∏_{V}^{k} U is connected. Since the fiber product ∏_{V}^{k} U is connected and smooth, it is irreducible. Since ∏_{V}^{k} U is irreducible, the closure of the image of ∏_{V}^{k} U in ∏_{Y}^{k} Z under I_{U}^{k} is also irreducible by Lemma A.2. □

If Z is an irreducible algebraic subset of an algebraic set X and π : X → Y is an algebraic map from X to an algebraic set Y, then we have the restriction π_{Z} : Z → Y of π to Z, and accordingly there exists the main component Z_{π_{Z}}^{k} of ∏_{Y}^{k} Z. Using the embedding ∏_{Y}^{k} Z in ∏_{Y}^{k} X, we see that Z_{π_{Z}}^{k} may be regarded as the main component of Z in ∏_{Y}^{k} X. We often abuse notation and denote Z_{π_{Z}}^{k} by Z_{π}^{k}: this causes no confusion in this article.

The following is our first characterization of main components.

Lemma 2.4 Let π : Z → Y be an algebraic map from an irreducible algebraic set Z to an algebraic set Y. There is a Zariski dense open set of y ∈ Y such that the fiber of the map Π_{k|Z_{π}^{k}} over y is

⋃_{i=1}^{ℓ} K_{i}^{k}

where ⋃_{i=1}^{ℓ} K_{i} is the irreducible decomposition of π^{−1}(y).

Proof. We use the notation of the Definition/Construction 2.1: it is straightforward to check the characterization asserted in the Lemma is true for the map π_{U} : U → W.

For a given point y ∈ Y, the fiber of the induced map Π_{k} : ∏_{Y}^{k} Z → Y is π^{−1}(y) × ⋯ × π^{−1}(y). If the irreducible decomposition of π^{−1}(y) is K_{1} ∪ ⋯ ∪ K_{ℓ}, then the irreducible decomposition of Π_{k}^{−1}(y) is

⋃_{(i_{1},...,i_{k})∈{1,...,ℓ}^{k}} K_{i_{1}} × ⋯ × K_{i_{k}}.  (7)

Using [13, Corollary A.4.12], it follows that for y in a Zariski open dense set of Y, the fiber is pure-dimensional. Using this and counting dimensions as in Lemma A.3, we see that for y in a Zariski open dense set of Y, π^{−1}(y)∩U is Zariski open and dense in π^{−1}(y) and thus that for y in a Zariski open dense set of Y, Π_{k}^{−1}(y) ∩ ∏_{Y}^{k} U is Zariski open and dense in Π_{k}^{−1}(y). Using this and the fact that the characterization is true for π_{U} : U → W, we are done. □

Lemma 2.5 For an irreducible subset Z ⊆ X and an algebraic map π : X → Y between algebraic sets, the main component Z_{π}^{k} satisfies the following:

1. Z_{π}^{k} is taken to itself under the natural action of the symmetric group S_{k} on ∏_{Y}^{k} X;

2. the dimension of Z_{π}^{k} is kh + b where b = dim \overline{π(Z)} and h = dim Z − b;

3. the image of the induced map from ∏_{Y}^{k} Z ⊂ ∏_{Y}^{k} X onto any one of the factors X is Z; and

4. if z ∈ Z, then (z, …, z) ∈ Z_{π}^{k}.

Proof. This follows from the fact that, using the notation from the definition of Z_{π}^{k} above, the image of ∏_{V}^{k} U in ∏_{Y}^{k} Z is a Zariski open dense set of Z_{π}^{k} and the fibers of the map r : U → V are connected.

Since the image of the induced map from ∏_{V}^{k} U onto any one of the factors U, in the construction of the main component is equal to U, we conclude that the image of the induced map from ∏_{Y}^{k} Z ⊂ ∏_{Y}^{k} X onto any one of the factors X is Z.

□

The sets Z_{π}^{k} are well behaved. For example, Z_{π}^{a+b} is the irreducible component of Z_{π}^{a} ×_{Y} Z_{π}^{b} that contains Z embedded under the diagonal map.

Note that if dim \overline{π(Z)} = dim Z, then Z_{π}^{k} equals the image of Z in ∏_{Y}^{k} Z under the diagonal map.

Remark 2.6 Note that Z_{π}^{k} need not be the largest or the smallest dimensional irreducible component of the fiber product ∏_{Y}^{k} Z. We illustrate this by considering two specific cases, as follows.

Case 1 Let Z := ℂ^{3} and let π : ℂ^{3} → ℂ^{4} be given by (z_{1}, z_{2}, z_{3}) ↦ (z_{1}, z_{2}, z_{1}z_{3}, z_{2}z_{3}). Then, Z_{π}^{2} = {(z; z′) ∈ ℂ^{3} ×ℂ^{3}|z = z′}, so dim Z_{π}^{2} = 3. There is another component W = {(0, 0, λ; 0, 0, μ), (λ, μ) ∈ ℂ^{2}} of dimension 2. Thus, in this case Z_{π}^{2} is the largest component.

Case 2 Let Z := ℂ^{3} and let π : ℂ^{3} → ℂ^{3} be given by (z_{1}, z_{2}, z_{3}) ↦ (z_{1}, z_{1}z_{2}, z_{1}z_{3}). Then, Z_{π}^{2} is the same in Case 1, but this time there is a second component W = {(0, λ, μ; 0, λ′, μ′), (λ, μ, λ′, μ′) ∈ ℂ^{4}}. Thus,

in this case dim Z_{π}^{2} = 3 < dim W = 4.

Other examples could be constructed such that Z_{π}^{2} is neither the largest nor the smallest irreducible component. Simply knowing the dimension of an irreducible component in a fiber product is not sufficient for recognizing main components.

Lemma 2.5 allows one to recognize which irreducible sets in ∏_{Y}^{k} X are main components of irreducible subsets of X. This is formalized as follows.

Theorem 2.7 Let π : X → Y be an algebraic map between algebraic sets. For a positive integer k, an irreducible algebraic subset W ⊂ ∏_{Y}^{k} X is the main component Z_{π}^{k} of some irreducible algebraic subset Z ⊆ X if and only if:

1. W is taken to itself under the natural action of the symmetric group S_{k} on ∏_{Y}^{k} X;

2. the dimension of W is kh+b where b equals the dimension of the closure of the image of W in Y, and b + h is the dimension of the image of W in X under any one of the k induced projections q_{i} : ∏_{Y}^{k} X → X; and

3. given a generic point (w_{1}, …, w_{k}) of W ⊂ ∏_{Y}^{k} X, it follows that (w_{1}, …, w_{1}) ∈ W.

If these conditions are satisfied Z = q_{i}(W) for any i.

Proof. Necessity is just Lemma 2.5. To prove the sufficiency, we must show that W = Z_{π}^{k} for Z ⊂ X. If this is true then q_{i}(W) = Z for any i. By the first condition of the theorem we see that the sets q_{i}(W) are all equal. Since W is irreducible then, by Lemma A.2, so is the set Z := q_{i}(W).

Thus we must show that W = Z_{π}^{k}. Choose a general point β of the closure T of the image of W in Y and let W_{β} be the fiber of W over β. Let K_{1}, …, K_{ℓ} be the irreducible components of the fiber over β of the restriction π_{Z} of the map π restricted to the image Z of W in X under any of the q_{i} for i = 1, …, k. All of the components are all of the same dimension h = dim Z − dim T by [13, Corollary A.4.12]. For a general point β of T, it also follows that the irreducible components of the fiber Z_{β}^{k} over β of the map Π_{k} : Π_{T}^{k} Z → T are of dimension kh and given by Eq. 7. By the definition of Z we have that W ⊂ Π_{T}^{k} Z and W_{β} ⊂ Z_{β}^{k}. By the dimension condition that dim W = kh + b, we see that all the components of W_{β} are of dimension kh and thus components of Z_{β}^{k}. By Lemma A.3 and Lemma 2.4, it suffices to show that at least one of the components of W_{β} is of the form K_{i}^{k} for some i = 1, …, ℓ. This follows from Lemma A.4. □

In § 3, we will use procedures from numerical algebraic geometry to compute irreducible components of fiber products. Theorem 2.7 then gives a way to recognize which of these are main components so that the corresponding exceptional loci can be identified. We shall return to this in § 3.

2.2 Splitting off exceptional loci

We start with a simple lemma that characterizes components of the exceptional loci.

Lemma 2.8 Let π : X → Y be an algebraic map between algebraic sets, and let Z denote an irreducible algebraic subset of X. Then Z is an irreducible component of D_{h}(π) if and only if there is a Zariski open dense set U ⊂ Z such that:

1. for x ∈ U, it follows that dim_{x} π^{−1}(π(x)) = h; and

2. for some y ∈ U there is an open set V ⊂ X in the complex topology that contains y and such that for y′ ∈ V \ Z, dim_{y′} π^{−1}(π(y′)) < h.

Proof. If Z is a component of D_{h}(π) and U is taken as the Zariski open dense subset of Z not meeting any other components of ∪_{j≥h}D_{j}(π), then the conclusions are clear.

Assume now that Z was not a component of D_{h}(π). The condition, that dim_{x} π^{−1}(π(x)) = h for a dense set of x, implies that Z ⊂ D_{h}(π). If Z is not a component of D_{h}(π), then it is a proper closed set of a component of D_{h}(π), and therefore each point x ∈ Z has points of D_{h}(π) in arbitrarily small complex neighborhoods of x as a point in X. □

Remark 2.9 In Lemma 2.8, it is only needed that U is a complex open set.

Theorem 2.10 Let π : X → Y be an algebraic map between algebraic sets, and let Z denote an irreducible component of D_{h}(π). Then, letting Π_{k} denote the induced mapping from ∏_{Y}^{k} X to Y, Z_{π}^{k} is an irreducible component of D_{kh}(Π_{k}) of dimension (k − 1)h + dim Z.

Proof. Straightforward. □

When k is not large enough, Z_{π}^{k} is not yet an irreducible component of ∏_{Y}^{k} X. One might hope that Z_{π}^{k} would be contained in some other main component W_{π}^{k} that is an irreducible component of ∏_{Y}^{k} X. If that were true, we could restrict all our attention at every k to just main components of ∏_{Y}^{k} X. Example 2.11 shows this is not true.

Example 2.11 Let X ⊂ ℂ^{4} be the solution set of f(v; a, b, c) := av^{2}+bv+c with the map π : (v; a, b, c) ↦ (a, b, c), so Y := \overline{π(X)} = ℂ^{3}. X is an irreducible hypersurface, so dim X = 3. The fibers of X for the map π are as follows:

1. over general (a, b, c), two points given by the quadratic formula; 2. over general points in V (b^{2} − 4ac), a single point with v = −b/(2a);

3. over points (0, b, c) with b ≠ 0, a single point with v = −c/b;

4. over points (0, 0, c) with c ≠ 0, the empty set; and

5. over (0, 0, 0), the one dimensional set Z = {(λ; 0, 0, 0), λ ∈ ℂ}.

The set D_{0}(π) is the whole set X, while D_{1}(π) = Z ⊂ X. The fiber product X ×_{Y} X is the set V (av_{1}^{2} + bv_{1} + c, av_{2}^{2} + bv_{2} + c) ⊂ ℂ × ℂ × ℂ^{3}, which has two irreducible components

• X_{π}^{2} := {(λ; λ; α, β, −αλ^{2} − βλ), (λ, α, β) ∈ ℂ^{3}}, and

• W := {(λ; μ; α, −α(λ + μ), αλμ), (λ, μ, α) ∈ ℂ^{3}}.

Meanwhile the main component Z_{π}^{2} ⊂ X ×_{Y} X is the two-dimensional set

{(λ; μ; 0, 0, 0), (λ, μ) ∈ ℂ^{2}}.

Clearly, Z_{π}^{2} lies in W and not in the main component X_{π}^{2}. This shows that when forming successive fiber products to find D_{1}(π), it is not sufficient to look only at main components of the intermediate stages. As an aside, we note that taking another fiber product will promote Z_{π}^{3} to an irreducible component of ∏_{Y}^{3} X.

Because of phenomena like that of Example 2.11, we need to know some structural facts about the irreducible components of ∏_{Y}^{k} X. To facilitate the discussion, we define the following notations.

• For 1 ≤ i ≤ k, let q_{i} : ∏_{Y}^{k} X → X denote the projection (x_{1}, …, x_{k}) ↦ (x_{i}).

• Let Π_{k} : ∏_{Y}^{k} X → Y denote π ∘ q_{i} (it is the same for any 1 ≤ i ≤ k).

• For an irreducible algebraic subset W ⊂ ∏_{Y}^{k} X, let b(W) denote dim Π_{k}(W) and let h_{i}(W) denote the generic fiber dimension of π : \overline{q_{i}(W)} → Y.

• With W as above, let Φ(W) = (b(W), max_{1≤j≤k}{h_{j}(W)}). We call the pair of nonnegative integers (b, h) = Φ(W) the “type” of W.

• Define the partial ordering ≺ on pairs of nonnegative integers as (b, h) ≺ (b′, h′) if b + h < b′ + h′ and h > h′.

For an irreducible algebraic set Z ⊂ X, the type (b, h) = Φ(Z) is b = dim \overline{π(Z)} and h = dim Z − b, which agrees with the above definition for k = 1. Moreover, Φ(Z_{π}^{k}) = Φ(Z).

Lemma 2.12 Let π : X → Y be a dominant algebraic map between irreducible algebraic sets, and let W denote an irreducible algebraic subset of ∏_{Y}^{k} X. Then the generic fiber dimension H(W) of Π_{k} : W → Y satisfies H(W) ≤ h_{1}(W) + ⋯ + h_{k}(W), and dim W = b(W) + H(W).

Proof. Straightforward. □

Theorem 2.13 Let π : X → Y be a dominant algebraic map between irreducible algebraic sets. Let Z denote an irreducible algebraic subset of D_{h}(π) with (b, h) = Φ(Z). Assume that Z_{π}^{k} is a proper subset of an irreducible component W of ∏_{Y}^{k} X. Then b(W) > b and h_{i}(W) < h for 1 ≤ i ≤ k. Moreover dim W ≤ dim W_{π}^{k} for some irreducible subset W of X that contains Z as a proper subset and satisfies \overline{Π_{k}(W)} = \overline{π(W)}.

Proof. First note that for each i, W_{i} := \overline{q_{i}(W)} is an irreducible subset of X containing Z. Since Z is an irreducible component of π^{−1}(\overline{π(Z)}), it follows that either b < b(W) or Z = \overline{q_{i}(W)} for each W. Since the latter gives the contradiction that Z_{π}^{k} = W, we conclude that b < b(W).

Using property 2) of Lemma 2.8, we conclude that h(\overline{q_{i}(W)}) < h(Z) = h for all i. Letting W be one of the \overline{q_{i}(W)} of largest dimension, we conclude that dim W ≤ b(W) + h(\overline{q_{1}(W)}) + ⋯ + h(\overline{q_{k}(W)}) ≤ dim W_{π}^{k}. □

Given Z as in Theorem 2.13, besides the bound

kh + b = dim Z_{π}^{k} < dim W,

the types (b′, h′) of irreducible components W of ∏_{Y}^{k} X that contain Z_{π}^{k} as a proper algebraic subset satisfy (b, h) ≺ (b′h′). We record this observation and the important bound it gives on what is the largest fiber product we need to consider.

Corollary 2.14 Let π : X → Y be a dominant algebraic map between irreducible algebraic sets. Let Z be an irreducible component of D_{h}(π) of type (b, h). If Z_{π}^{k} is a proper subset of an irreducible component W of ∏_{Y}^{k} X of type (b′, h′), then we have (b, h) ≺ (b′, h′). Moreover, Z_{π}^{k} is an irreducible component of ∏_{Y}^{k} X for

k ≥ \{ \begin{matrix}dim X − dim Z + 1, & if h = h(X) + 1 or dim Z = dim X − 1; \\ dim X − dim Z, & otherwise. \end{matrix} Proof. Since Z_{π}^{k} is properly contained in W, we must have dim Z_{π}^{k} = b + kh < dim W. Theorem 2.13 implies both b < b′ and h > h′. Altogether, these imply (b, h) ≺ (b′, h′). Moreover, Lemma 2.12 implies dim W ≤ b′+kh′ and Theorem 2.13 implies that either Φ(W) = Φ(X) or (b′, h′) ≺ Φ(X). Since h > h′, for large enough k, there can be no such W with b + kh < b′ + kh′, so Z_{π}^{k} must be an irreducible component of ∏_{Y}^{k} X. In particular, this occurs for k ≥ (b′ − b)/(h − h′). Let (B, H) = Φ(X). For a given (b, h), the worst case for k is the maximum of (b′ − b)/(h − h′) over all (b′, h′) such that either (b, h) ≺ (b′, h′) ≺ (B, H) or (b′, h′) = (B, H). When h = H + 1 or dim Z = dim X − 1, the first set is empty, so the worst case is (b′, h′) = (B, H), from which it follows that k ≥ dim X − dim Z + 1 suffices. Otherwise, one may confirm that the worst case occurs for h′ = h − 1, b′ + h′ = B + H − 1, so k ≥ dim X − dim Z suffices. □

When k is large enough that Z_{π}^{k} is an irreducible component of ∏_{Y}^{k} X, we say that Z has been promoted to irreducibility in ∏_{Y}^{k} X. Using this language, we may state the following upper bound on the number of fiber product operations necessary to find all the exceptional loci in X.

Corollary 2.15 Under the same assumptions as Corollary 2.14, all irreducible components of D_{h}(π) that could be contained in X for any h will be promoted to irreducibility in ∏_{Y}^{k} X for k ≥ b(X).

Proof. The worst case among all (b, h) ≺ (B, H) = Φ(X) for the bound given in Corollary 2.14 occurs when b = 0 and h = H + 1. □

This corollary implies that to find all exceptional loci, we will never have to form a fiber product beyond k = b(X), as that already suffices.

Table 1 illustrates Corollary 2.14 for the case Φ(X) = (8, 2). We place a 1 in location (8, 2) to indicate that for k = 1, ∏_{Y}^{k} X = X. Notice that in accordance with Corollary 2.15, the worst case of k = 8 occurs for (b, h) = (0, 3).

2.3 A special bound

Though we often need to go to the k-th fiber product for the k predicted in Corollary 2.14 before a given component of D_{h}(π) becomes an irreducible component of the fiber product, it can happen for a smaller k. Here is an example illustrating this.

Table 1: Bound on k for promotion to irreducibility for (b, h) ≺ Φ(X) = (8, 2).

h\b 0 1 2 3 4 5 6 7 8
9 2
8 2 2
7 3 2 2
6 4 3 2 2
5 5 4 3 2 2
4 6 5 4 3 2 2
3 8 7 6 5 4 3 2
2  1

Example 2.16 Consider the system of equations on ℂ^{7}:

[ \begin{matrix}y_{1} − x_{1} \\ y_{2} − x_{2} \\ y_{3} − x_{1}x_{3} \\ y_{4} − x_{2}x_{3} \end{matrix} ] = 0.  (8)

The solution set X is parameterized by ℂ^{3}. We let π denote the restriction to X of the projection

(x_{1}, x_{2}, x_{3}, y_{1}, y_{2}, y_{3}, y_{4}) ↦ (y_{1}, y_{2}, y_{3}, y_{4}).

All fibers of the map π : X → π(X) have cardinality one except for the fiber Z over (0, 0, 0, 0), which is the x_{3}-axis. Using Theorem 2.13, we know that the one dimensional component Z of D_{1}(π) will lead to a 3-dimensional irreducible component of X ×_{Y} X ×_{Y} X. The fiber product Z ×_{Y} Z is in fact a two dimensional irreducible component of X ×_{Y} X.

Examples 2.16 suggests the following useful criterion that applies in the important special situation dim X = dim π(X).

Theorem 2.17 Let π : X → Y be a dominant algebraic map between irreducible algebraic sets of the same dimension. Assume that Y is locally irreducible, e.g., Y = ℂ^{m}. Let Z denote a proper irreducible algebraic subset of D_{h}(π) and assume that h is the smallest positive integer such that D_{h}(π) ≠ ∅. Assume that the general fiber of π consists of d points. Then Z_{π}^{k} is an irreducible component of ∏_{Y}^{k} X for k ≥ d + 1.

Proof. Note that for j ≤ k and each set map

ϕ : {1, …, k} → {1, …, j}

we have maps I_{ϕ} : ∏_{Y}^{j} X → ∏_{Y}^{k} X sending the j-tuple (x_{1}, …, x_{j}) to a k-tuple (x_{ϕ(1)}, …, x_{ϕ(k)}). Note that if k ≥ d + 1, then the union U of the images of all these maps contains all points of the fiber over y of ∏_{Y}^{k} X → Y. Moreover, by [5, (3.10)], U contains every 0-dimensional component of any fiber of ∏_{Y}^{k} X → Y. But, given k general points of an irreducible component of a general fiber of Z → \overline{π(Z)}, we see by counting dimensions that U does not contain Z_{π}^{k}. Thus if Z_{π}^{k} is not an irreducible component of ∏_{Y}^{k} X, it follows from Theorem 2.13 that it is contained as a proper algebraic subset of an irreducible component W ⊂ ∏_{Y}^{k} X of dimension ≤ dim W for some irreducible subset W of X that contains Z as a proper subset and satisfies \overline{π(W)} = \overline{π(W)}. Since U contains all 0-dimensional components of fibers of ∏_{Y}^{k} X → Y, we conclude that W has all fibers positive dimensional. From this we contradict that Z is a proper subset of W, and that Z is a proper irreducible algebraic subset of D_{h}(π) with m the smallest positive integer such that D_{h}(π) ≠ ∅. □

3 The Algorithm

Let us assume the set X ⊂ ℂ^{N+m} to be studied is the solution set of a polynomial system f(v; p) : ℂ^{N+m} → ℂ^{m}, as in Eq. 1, with the projection map π : (v; p) ↦ p. If instead the map is given in the form π′ : v ↦ g(v), we convert it to the assumed form as f(v; p) = p − g(v). In this way, Y becomes the natural projection of X to ℂ^{n}, and points in the kth fiber product, ∏_{Y}^{k} X, lie in ℂ^{kN+m} with coordinates (x_{1}, …, x_{k}; p). Accordingly, the projection Π_{k} : ℂ^{kN+m} → ℂ^{m} is just (x_{1}, …, x_{k}; p) ↦ (p) and for i = 1, …, k, the maps q_{i} : ℂ^{kN+m} → ℂ^{N+m} are given by (x_{1}, …, x_{k}; p) ↦ (x_{i}; p). Note that for x ∈ ∏_{Y}^{k} X, Π_{k}(x) = π(q_{i}(x)) for i = 1, …, k. In the following, it will be useful to use the Jacobian matrices for these projections, namely dπ = [0_{m×N} I_{m}], dΠ_{k} = [0_{m×kN} I_{m}], and

dq_{i} = [ \begin{matrix}0_{N×(i−1)N} & I_{N} & 0_{N×(k−i)N} & 0_{N×m} \\ 0_{m×(i−1)N} & 0_{m×N} & 0_{m×(k−i)N} & I_{m} \end{matrix} ] ,

where 0_{i×j} is an i × j matrix of zeros and I_{j} is a j × j identity matrix. Clearly, dπ · dq_{i} = dΠ_{k} for i = 1, …, k.

Recall that within the framework of numerical algebraic geometry, algebraic sets are represented by witness sets. A witness set for pure dimensional algebraic set A ⊂ ℂ^{n} consists of deg A isolated points in the intersection A∩L, where L ⊂ ℂ^{n} is a general linear subspace of dimension dim L = codA. If A is not pure dimensional, then a witness set for A consists of a collection of witness sets for its pure dimensional pieces.

To build algorithms to solve Problem 1.1, i.e., to find the exceptional loci of X, we will use the following procedures from numerical algebraic geometry.

Irreducible Decomposition For a polynomial system f(x), find witness sets for the irreducible components of the solution set of f(x) = 0 [7, 13].

Deflation Suppose w is a witness point for an irreducible component A ⊂ f^{−1}(0) and suppose L(x) is the system of linear equations that isolates w in A. Then, w is a solution of the augmented system F (x) = {f(x), L(x)}. If A is a reduced component, then the Jacobian matrix ∂F/∂x has full rank and deflation trivially returns f(x). Otherwise, deflation returns a new system f̂(x, λ) that has an irreducible component Â that is reduced and projects to A under the natural projection (x, λ) ↦ (x), along with the points in Â that project to the witness points of A. Deflation for isolated solutions of polynomial systems is discussed in [2] and its use in connection with deflating nonreduced components was introduced in [13, §13.3.2].

Sampling Suppose we have a witness set w = A ∩ L for a pure dimensional algebraic set A. Given a new target slicing space L′, where L and L′ both have dimension equal to codA, Sampling follows the continuation paths from w to the points w′ = A ∩ L′ as L is continuously moved to L′ along a general path in the Grassmannian of linear spaces of dimension codA.

Membership Test Given a witness set w for a pure i-dimensional algebraic set A ⊂ ℂ^{n}, one may determine whether z ∈ ℂ^{n} is in A by generating a general linear subspace L′ of dimension n − i that contains z and running the Sampling algorithm to obtain w′ = A ∩ L′. Then, z ∈ A if and only if z ∈ w′. There is a second way of checking membership, that is sometimes useful in practical examples. Given a point p ∈ w in a witness set for A, then z ∈ A if there exists an irreducible algebraic set B such that {p, z} ∈ B, and B ⊂ X, e.g., a generic point b ∈ B satisfies the system f(v; p) = 0. This criteria is used with B a linear space in the example in §4.

Before giving a full algorithm for Problem 1.1, it will be helpful to first define new sub-algorithms, Image Dimension, Base Dimension, Fiber Dimension, and Main Component.

Image Dimension determines the dimension of the image of an irreducible algebraic set A ⊂ V (f) under a projection map π, i.e., determines dim \overline{π(A)}, given a witness set for A. For convenience, let us denote this as ImDim_{π}(A). The procedure is to first apply Deflation to get Â having a generically maximal rank projection π̂ such that A = π̂(Â). (If the Jacobian matrix of f is already maximal rank at a witness point of A, then Â = A and π̂ is the identity.) At a general point of Â, e.g., at one of the deflated witness points, say ŵ, find a basis B for the tangent space of Â using standard linear algebra, that is, B = ker(df̂(ŵ)), where ker() finds the kernel (null space) of a matrix. Then, ImDim_{π}(A) = rank(dΠ_{k} · dπ̂ · B).

The Base Dimension b(W) of an irreducible component W ⊂ ∏_{Y}^{k} X is just b(W) = ImDim_{Π_{k}}(W).

For 1 ≤ i ≤ k, the ith Fiber Dimension h_{i}(W) of an irreducible component W ⊂ ∏_{Y}^{k} X is h_{i}(W) = ImDim_{q_{i}}(W) − b(W).

When W is nonreduced, the base dimension and fiber dimension calculations both need a deflation of W. In an efficient implementation, the deflation can be generated just once to serve both purposes.

Main Component is based on Theorem 2.7. We suppose that we have a witness set for an irreducible component W of ∏_{Y}^{k} X, and we wish to determine if it is a main component W_{π}^{k} for some irreducible set W ⊂ X. We proceed by testing the conditions set out in Theorem 2.7, as follows.

1. Check if W is invariant under the symmetric group S_{k}. To do so, we note that two generators are sufficient to generate all of S_{k}, namely interchanging the first two elements, (x_{1}, x_{2}, x_{3}, …, x_{k}) ↦ (x_{2}, x_{1}, x_{3}, …, x_{k}), and cyclicly advancing all the elements, (x_{1}, x_{2}, …, x_{k}) ↦ (x_{k}, x_{1}, …, x_{k−1}). Denote these generators as S and S′. Let w be one of the witness points for W. Use the Membership Test to see if S(w) and S′(w) are in W. If so, the first check passes.

2. Compute the Base Dimension b(W) and Fiber Dimension h_{i}(W), 1 ≤ i ≤ k. All the h_{i}(W) must be equal. If not, the test fails. If so, let h(W) = h_{i}(W), and check that dim W = b(W) + kh(W).

3. For one witness point (w_{1}, …, w_{k}) of W, use Membership Test to see if (w_{1}, …, w_{1}) ∈ W.

It is sufficient to test all of these at a single witness point, because the witness points are cut out generically, so if the tests pass for one witness point, they must pass for all the witness points. If and only if all these conditions are met, W is a main component W_{π}^{k}. As an aside, we note that one may subsequently test if a point z ∈ ℂ^{n} is in the set W associated to W by testing if the k-tuple (z, …, z) is in W using the Membership Test.

A basic algorithm for finding exceptional loci simply uses Corollary 2.15. In brief, one could proceed as follows.

1. Compute the numerical irreducible decomposition of f^{−1}(0). This produces a list of irreducible components, say X_{1}, …, X_{r}, each represented by a witness set.

2. Use Image Dimension to find ImDim_{π}(X_{i}), i = 1, …, r. Let k be the maximum of these.

3. Form the fiber product system F_{k}(v_{1}, …, v_{k}; p) := {f(v_{1}; p), …, f(v_{k}; p)} and compute the decomposition of its solution set into irreducibles, say W_{1}, …, W_{s}.

4. Use Main Component to detect which of W_{1}, …, W_{s} are main components, thereby also finding the associated sets W_{i} such that W_{i} = (W_{i})_{π}^{k}. These are the irreducible exceptional loci.

We have used the fact that once the main component of an irreducible exceptional locus has been promoted to irreducibility, it remains so for higher fiber products. Thus, in step 2, we determine a k that is large enough to promote all the exceptional sets to irreducibility.

Example 3.1 Using the algorithm on Example 2.11, one finds that the system has one irreducible component X = V (av^{2} + bv + c) with a base dimension b(X) = 3. Thus, we proceed by forming the tripled system on ℂ^{6}

[ \begin{matrix}av_{1}^{2} + bv_{1} + c \\ av_{2}^{2} + bv_{2} + c \\ av_{3}^{2} + bv_{3} + c \end{matrix} ] = 0,

and compute its irreducible decomposition. The total degree is 27, so the cascade algorithm has 27 paths, eight of which stop at stage 1 of the cascade as degenerate points at infinity, and the other 19 proceed all the way to stage 3 of the cascade. These are all nonsingular, so they are witness points for the codimension 3 irreducible components of X ×_{Y} X ×_{Y} X viewed as a subset of ℂ^{6}. Of these, 3 are of the form v_{1} = v_{2} = v_{3}, and 5 each are of the form v_{1} = v_{2} ≠ v_{3}, v_{2} = v_{3} ≠ v_{1}, and v_{3} = v_{1} ≠ v_{2}. This leaves just one witness point of the form v_{1} ≠ v_{2} ≠ v_{3} for which a = b = c = 0. Only this witness point passes the Main Component test, and it represents the exceptional locus D_{1}(π) given by (v; a, b, c) = (λ; 0, 0, 0), λ ∈ ℂ.

The foregoing algorithm is not practical for many systems of interest, because the total degree of the fiber product system F_{k} will be too large. Clearly, it is wasteful to use the same worst case k to find every irreducible exceptional locus, as some might appear for a much smaller k than others. Moreover, the system F_{k} will have solution components that mix up the irreducibles X_{1}, …, X_{r} when it is sufficient to examine only the unmixed fiber products ∏_{Y}^{k} X_{i}. Finally, as seen in Example 3.1, the basic algorithm finds many components of ∏_{Y}^{k} X that cannot be main components because they have unequal dimensions under the projections q_{i}.

It is likely that a better approach can be devised by using diagonal intersections (see [9, 10, 11]) to sequentially build up ∏_{Y}^{k} X_{i} for k = 2, then k = 3, etc., stopping according to the more refined conditions of Corollary 2.14. By repeatedly applying diagonal intersections with the same component, one avoids mixing fibers across the different components.

If one is interested only in exceptional loci having certain base and fiber dimension pairs, then a more refined approach is possible. For any particular (b, h) pair of interest, Corollary 2.14 gives an upper bound, say k, on the number of fiber products necessary to promote any such set, say Z, to irreducibility. Moreover, we can slice out isolated points of the main component Z_{π}^{k} by intersecting it with a linear space of the form

L_{b,h,k} = ⋂_{i=1}^{b} L_{i}(π) ⋂_{i=1}^{h} L_{i}^{1}(q_{1}) ⋯ ⋂_{i=1}^{h} L_{i}^{k}(q_{k}),  (9)

where each L_{i}(π) and L_{i}^{j}(q_{j}) is the pullback of a generic hyperplane in the image space of the indicated projection. This can be relatively efficient because the structured slice respects a natural sparsity of the problem, hence multihomogenization or sparse polytope methods can come into play. Let us call this a “multislice” approach. A multislice can contain points on sets other than main components, so the points must still be checked using Main Component.

The multislice technique can be used repeatedly to target each possible pair (b, h) ≺ (B, H). In many cases, this can result in fewer total homotopy paths than required by the basic algorithm.

4 Example: Rulings on a Quadric

This section reports on the application of fiber products to study rulings on a quadric surface in ℂ^{3}. The calculations were done using an extension of HomLab, a suite of routines written in Matlab as an accompaniment to the book [13]. The routines run in double precision and use a power series endgame to accurately compute singular endpoints. CPU times are reported for an HP x4000 with a 2GHz Xeon CPU running Windows XP.

A classic result from algebraic geometry is that most quadric surfaces in ℂ^{3}, e.g., the ones that have smooth closure in ℙ^{3}, are doubly ruled. This serves as a good test example for our fiber product approach: we know that a random line hits a general quadric in two isolated points, and we wish to find the lines that lie entirely in the surface. Let q(x) : ℂ^{3} → ℂ be a quadric polynomial, whose coefficients are chosen at random from ℙ^{9}. To parameterize the lines in ℂ^{3}, we use a vector u ∈ ℂ^{3} along the line and a point v ∈ ℂ^{3} on the line, so the points x ∈ ℂ^{3} that lie on the line are those that satisfy the system

u × (x − v) = 0,  (10)

where “×” denotes the vector cross product (outer product) operator in three-space. (This vector equation is a system of three scalar equations, but it places at most two constraints on x, because u^{T} (u × (x − v)) = 0 for any x.)

The system we wish to analyze is

f(x; u, v) = {q(x), u × (x − v)} = 0.  (11)

The projection of interest is π : (x; u, v) ↦ (u, v). We know that D_{0}(π) consists of two points of V (q) over each generic point in (u, v) ∈ ℂ^{6}. Rulings of V (q) are points in D_{1}(π).

So as to test the fiber product algorithm, let us proceed as if we know nothing of the classical theory of rulings on quadrics. We begin by computing an irreducible decomposition of V (f) ⊂ ℂ^{9}. This is a system of four quadratic equations, so Irreducible Decomposition using the cascade algorithm of [6],[13, chap.14] initiates with 16 paths. The cascade results at each dimension are as follows, where “Dim” is dimension, “Paths” is the number of solution paths used to check that dimension, #Ŵ is the number of points found in the witness superset, #Ŵ_{sing} is the number of these whose Jacobian is less than full rank, #N is the number of nonsolutions that carry over to the next level of the cascade, #∞ is the number of paths ending at infinity, \overline{nfe} is the average number of function evaluations per path, and “nfe” is the total number of function evaluations for all the paths at that dimension. The total run time is about 22 sec, using a “tableau” description of f expanded into its monomials.

Dim Paths #Ŵ #Ŵ_{sing} #N #∞ \overline{nfe}  nfe
8  16  0  0  10  6 151.63 2426
7  10  0  0  10  0  57.20 572
6  10  6  0  4  0  65.60 656
5  4  4  4  0  0  69.25 277

The top dimensional component is dimension 6 and degree 6 with all nonsingular witness points. The 4 singular points at dimension 5 are “junk,” that is, they lie in the set found at dimension 6.

Let Z = V (f). The above calculation shows that dim Z = 6 and subsequent trace testing shows that it is one irreducible set. To reduce the total degree of the system before forming fiber products, it is useful to “square up” f using random linear combinations of the equations. Since Z is codimension 3, three linear combinations of the functions in f are sufficient to have Z as a component. That is, we use

f̂(x; u, v) = R · ( \begin{matrix}q(x) \\ u × (x − v) \end{matrix} )

where R ∈ ℂ^{3×4} is chosen at random. This is a system of 3 quadratic polynomials, and Z is an irreducible component of V (f̂).

Next, we use Image Dimension to find that B = b(Z) = 6, hence H = h(Z) = 0. We know from Corollary 2.15 that finding the irreducible decomposition of ∏_{Y}^{6} Z will suffice to find all exceptional loci. However, it is clear that the lowest possible base dimension is b = 2, because if (u, v, x) is a solution, so is (λu, v + μu, x) for any (λ, μ) ∈ ℂ^{2}. Accordingly, just analyzing ∏_{Y}^{4} Z will suffice.

However, since dim π(Z) = dim Z, it may be that Theorem 2.17 gives a tighter bound on the number of fiber products we need. In fact, we know that a general line strikes a general quadric in two points, so Theorem 2.17 Table 2: Bound on k for promotion to irreducibility for rulings on a quadric.

h\b 2 3 4 5 6
2 2 2
1 3^{∗} 3 2
0  1

∗ reduced from 4 by Theorem 2.17.

applies with d = 2. Accordingly, ∏_{Y}^{3} Z suffices to find the lowest nonempty D_{h}(π).

This preparatory work, summarized in Table 2, tells us that if rulings exist on the quadric, then they will be discovered by an irreducible decomposition of ∏_{Y}^{3} Z. The 9 polynomials for the fiber product are:

F̂(x_{1}, x_{2}, x_{3}; u, v) = \{ \begin{matrix}f̂(x_{1}; u, v) \\ f̂(x_{2}; u, v) \\ f̂(x_{3}; u, v) \end{matrix} \} ,  (12)

We use F̂ to distinguish this system from the system F of 12 polynomials that would result from using f instead of f̂.

The results of the cascade algorithm for generating witness supersets are as follows. The calculation required about 14 minutes of CPU.

Dim Paths #Ŵ #Ŵ_{sing} #N #∞  \overline{nfe}  nfe
14  512  0  0  280 232 249.02 127498
13  280  0  0  280 0  59.77 16736
12  280  0  0  280 0  54.06 15137
11  280  0  0  280 0  63.51 17782
10  280  0  0  280 0  61.01 17083
9  280  8  0  272 0  67.86 19002
8  272  32  24  240 0  84.92 23099
7  240  80  80  160 0  82.03 19688
6  160 160  80  0  0  73.03 11684

The highest dimensional set is dimension 9 having degree 8. Examination of the witness points reveals immediately that u = 0 for all these points. It is clear that this is the set which we denote as U, defined as U = {0} × ℂ^{3} × V (q(x_{1})) × V (q(x_{2})) × V (q(x_{3})). It is not a ruling, as u = 0 does not correspond to a line, but it nonetheless reveals this component in D_{2}(π) having base dimension b(U) = 3 and fiber dimension h(U) = 2.

At dimension 8, there are 32 candidate witness points, 24 of which are singular. The singular ones are all in U. The remaining 8 are figments of the randomization: they lie in V (F̂) but not in V (F). These are of no interest to us.

At dimension 7, there are 80 candidate witness points, all singular. These break up into 48 in U and 32 that are not in V (F).

Finally, at dimension 6 we have the candidate witness points of greatest interest. Eighty of 160 are singular, again with 48 in U and 32 not in V (F). This leaves 80 nonsingular witness points.

The next step is to check the 80 points against the conditions x_{1} = x_{2}, x_{2} = x_{3}, and x_{3} = x_{1}. Any point satisfying one of these conditions is not of interest, as a general slice of the main component will have independent x_{i} from the fiber. A check shows that there are 18 points that satisfy each of x_{1} = x_{2} ≠ x_{3}, x_{2} = x_{3} ≠ x_{1}, and x_{3} = x_{1} ≠ x_{2}. Six more satisfy x_{1} = x_{2} = x_{3}. These are nothing more than the original degree 6 set Z with (u, v, x) mapped to (u, v, x, x, x).

This leaves just 20 witness points as candidates for rulings of the quadric. All have x_{1} ≠ x_{2} ≠ x_{3} ≠ x_{1}. Using Image Dimension and Fiber Dimension, we find that all have b = 3 and h_{1} = h_{2} = h_{3} = 1. Monodromy with traces shows that the points break up into two irreducible components of degree 10 each: call these sets W_{1} and W_{2}. We use Membership Test on one point (u, v, x_{1}, x_{2}, x_{3}) of each of them to verify that (u, v, x_{2}, x_{1}, x_{3}) and (u, v, x_{3}, x_{1}, x_{2}) are also on the component. Finally, we need to check that point (u, v, x_{1}, x_{1}, x_{1}) is in the set. In principle, we could also use a homotopy membership test for this, but (u, v, x_{1}, x_{1}, x_{1}) is a highly singular point, which makes accurate path tracking difficult. Instead, we may use the fact that since h = 1, the fibers must be lines, so it suffices to check that for random α, β,

F̂(u, v, x_{1}, (1 − α)x_{1} + αx_{2}, (1 − β)x_{1} + βx_{3}) = 0.

This equality holds and thereby confirms that the closure of the set includes the point (u, v, x_{1}, x_{1}, x_{1}) in the limit as (α, β) → (0, 0). These conditions are satisfied for a test point from each of W_{1} and W_{2}, thus showing that both are the main components of a set in D_{1}(π).

Under the equivalence (u, v) ≡ (λu, v + μu) for our representation of lines in ℂ^{3}, the base dimension b(W_{i}) = 3, i = 1, 2, implies that these are each a one dimensional family of distinct lines. A one dimensional family of rulings sweeps out a two dimensional surface, so its closure must be equal to the closure of the whole quadric. Altogether, this shows that there are two rulings of the quadric, each being degree 10 in the formulation we study here.

None of the checking or sorting steps takes more than a 10 seconds of CPU; the computation is completely dominated by the cascade generation of the witness supersets.

5 Conclusions and Discussion

Exceptional sets where fibers have dimensions higher than the generic fiber dimension are of interest in mathematics and in application areas, such as the theory of overconstrained mechanisms. We show that fiber products promote such sets to become irreducible components, whereupon they can be found using techniques from numerical algebraic geometry for computing the irreducible decomposition. We provide an upper bound on the number of fiber products necessary to promote an exceptional set to irreducibility, depending on the base and fiber dimensions of a generic fiber and of the exceptional set. In any case, the Bth fiber product, where B = b(X), will promote even the smallest exceptional set in X to irreducibility. When b(X) = dim X, then the (d+1)th fiber product, where d is the cardinality of a generic fiber, is guaranteed to promote the exceptional set of smallest fiber dimension to irreducibility. This can sometimes provide a tighter bound and thereby limit the amount of computation.

An irreducible decomposition of a fiber product may contain components other than the exceptional loci we seek. We show that each irreducible component of the exceptional loci has a corresponding main component in a fiber product of sufficiently high order, and we give procedures for identifying these components. The methods are illustrated by finding the rulings of a general quadric in ℂ^{3}.

The largest drawback of our approach is the rapid escalation of the total degree of the system of equations as successive fiber products become necessary. The simplistic approach of finding the irreducible decomposition of a fiber product ∏_{Y}^{k} X with k set to the worst case is too expensive for many systems of practical interest. Our future work will concentrate on how to best use successive diagonal homotopies to eliminate unproductive calculations and how to integrate this with the multislice technique for targeting one (b, h) pair at a time.

A Some background on algebraic sets

In this appendix, we collect some definitions and lemmas that are needed throughout this article, particularly in the definition and characterization of the main component of a fiber product of an algebraic set with itself.

By a Zariski open set U of an algebraic set X is meant a set of the form X \ A where A is an algebraic subset of X. The Zariski open sets form a topology, which usually has many fewer open sets than the usual complex topology induced on X as a subset of ℂ^{N} or ℙ^{N}. We refer [13, §12.1.1] for more on these two topologies.

In this article we ignore multiplicities, i.e., we only deal with reduced algebraic sets. Thus for example, the set defined by z^{2} = 0 on ℂ^{2} is the same as the set defined by z = 0 on ℂ. Although we ignore multiplicities, the algorithms in this article work with sets of arbitrary multiplicity. Numerical computations with sets of multiplicity at least two may be reduced to computations with multiplicity one sets, at the expense of an increase in the number of variables, by the use of deflation, see [2] and [13, §10.5] for the isolated case and [13, §13.3.2] for the positive dimensional case.

Let π : X → Y be an algebraic map between algebraic sets, i.e.,

1. X and Y are algebraic sets; and

2. π is an algebraic map, i.e., π is a map whose graph Γ is an algebraic subset of X × Y with the map Γ → X, induced by the product projection, an isomorphism.

Example A.1 For a typical example of how an algebraic map between affine algebraic sets arises, let X be the set of solutions of the system f(v; p) of polynomials on ℂ^{N+m} from Eq. 1 with v ∈ ℂ^{N} and p ∈ ℂ^{m}. Letting π denote the restriction to X of the projection ℂ^{N} × ℂ^{m} → ℂ^{m} given by (v; p) ↦ p, we have by Chevalley’s Theorem, as discussed above, that π(X) is a constructible algebraic set. Note that the closure \overline{π(X)} of π(X), which as discussed above is the same in either the Zariski or complex topology, is an algebraic subset of ℂ^{m} and hence affine. Taking Y to be any affine algebraic subset of ℂ^{m} containing \overline{π(X)}, e.g., \overline{π(X)} or ℂ^{m}, gives an example.

The constructible sets on an algebraic set X are the sets obtained from the algebraic subsets by closing up under the operations of complementation and finite unions. These sets include the Zariski open sets plus many other sets, e.g.,

{(x, y) ∈ ℂ^{2}|x ≠ 0} ∪ {(0, 0)} .

Given an algebraic map f : X → Y between algebraic sets, the image π(X) need not be an algebraic set, but it is always constructible by Chevalley’s Theorem [13, Theorem 12.5.6]. Given a constructible subset C ⊂ X of an algebraic set X, the closure \overline{C} of C in either the Zariski or complex topology are the same, and there is a Zariski open and dense subset U ⊂ \overline{C} that is contained in C. These results, which are discussed in [13, §12.5] allow us quickly reduce questions about constructible sets to questions about algebraic sets.

General or generic points play a key role in applications of numerical analysis to the solution of polynomial systems. Classically, there are different interpretations of what this means. Referring to [13, Chapter 4] for details, we summarize what this means. Roughly speaking, a general or generic point of an irreducible algebraic set X is a point in a Zariski open and dense set U ⊂ X such that some finite set of properties hold for points of U. For example, given polynomial f_{1}(x), …, f_{n}(x) on ℂ^{N} such that there are no common solutions of the f_{i}(x), Bertini’s Theorem states that there is a nonempty Zariski open set U ⊂ ℂ^{n} such that for (c_{1}, …, c_{n}) ∈ U, the solution set of c_{1}f_{1}(x)+⋯+c_{n}f_{n}(x) is either empty or a smooth codimension one algebraic set. Finite intersections of nonempty Zariski open subsets of an irreducible Zariski open set are nonempty Zariski open, and hence dense. Typically in constructions we successively restrict to smaller and smaller Zariski open sets on which successively stronger properties hold. Though it is not without interest what the detailed properties of these sets are, a major strength of numerical methods is that a numerically computed “random point” on an irreducible algebraic set behaves for practical purposes like a general point theoretically should behave.

As we successively go to smaller and smaller Zariski open sets, we typically retain the same name for the set.

Lemma A.2 Let f : A → B be an algebraic map from an algebraic set A to an algebraic set B. Then the closure \overline{f(A)} of f(A) in the complex and Zariski topology are the same. If A is irreducible, then so is the algebraic set \overline{f(A)}

Proof. The first assertion follows from Chevalley’s Theorem [13, Theorem 12.5.6] and [13, Lemma 12.5.3]. The irreducibility statement is [13, Corollary 12.5.7]. □

Lemma A.3 Let Z_{1} and Z_{2} be irreducible algebraic subsets of an algebraic set X. Let π : X → Y be an algebraic map from X to an algebraic set Y. Assume that π_{Z_{1}} is a dominant map, i.e., that π(Z_{1}) is dense in Y. Then either Z_{1} = Z_{2} or there is a Zariski open and dense set V ⊂ Y such that given y ∈ V, π_{Z_{1}}^{−1}(y) and π_{Z_{2}}^{−1}(y) have no common irreducible components.

Proof. Y is irreducible by Lemma A.2. In the course of the proof we will intersect a finite number of Zariski open and dense subsets of Y: such an intersection remains Zariski open and dense.

If π(Z_{2}) is not dense in Y, the conclusion is immediate. Therefore we can assume without loss of generality that both of π_{Z_{1}} and π_{Z_{2}} are dominant. Thus by [13, Corollary A.4.12], for i = 1, 2, there is a Zariski open and dense set V_{i} of Y such that for y ∈ V,

1. dim Z_{i} = dim Y + dim π_{Z_{i}}^{−1}(y); and

2. π_{Z_{i}}^{−1}(y) is pure dimensional, i.e., each component of π_{Z_{i}}^{−1}(y) has the same dimension.

These properties hold for the Zariski open and dense set V_{3} := V_{1} ∩V_{2}. From these properties we see that π_{Z_{1}}^{−1}(y) and π_{Z_{2}}^{−1}(y) having a common irreducible component for a Zariski open and dense set of y ∈ Y would imply that dim Z_{1} = dim Z_{2}. Thus if Z_{1} ≠ Z_{2} it follows that the intersection Z′ of Z_{1} and Z_{2} is of dimension strictly less that dim Z_{1}. Applying [13, Corollary A.4.12] to π_{W} for any irreducible component W of Z′, we conclude that dim π_{W}^{−1}(y) < dim π_{Z_{1}}^{−1}(y) and hence also dim π_{Z′}^{−1}(y) < dim π_{Z_{1}}^{−1}(y) for a Zariski open and dense set of y ∈ Y. Since π_{Z′}^{−1}(y) and π_{Z_{1}}^{−1}(y) are pure dimensional for a Zariski open and dense set of y ∈ Y, they can have no common components. □

Lemma A.4 Let G = K_{1} ∪ … ∪ K_{ℓ} be a decomposition of an algebraic set into irreducible components. Then an irreducible component K of G^{k} is of the form K_{i}^{k} for some i = 1, …, ℓ if and only if given a general point (x_{1}, …, x_{k}) ∈ K it follows that (x_{1}, …, x_{1}) ∈ K.

Proof. The “only if” half of the lemma is immediate. So we assume that given a general point (x_{1}, …, x_{k}) ∈ K it follows that (x_{1}, …, x_{1}) ∈ K. We need to show that K is of the form K_{i}^{k}.

The irreducible components of G^{k} are of the form

K_{i_{1}} × ⋯ × K_{i_{k}}

for (i_{1}, …, i_{k}) ∈ {1, …, ℓ}^{k}. Since none of the K_{i} belong to the union of the remaining K_{i}, it follows that a general point of anyone of the K_{i} does not belong to any of the remaining K_{i}. Therefore the only sets of the form K_{i_{1}} × ⋯ × K_{i_{k}} satisfying the hypothesis of the lemma are of the ones of the form K_{i}^{k}. □

References

[1] D. Lazard and F. Rouillier. Solving parametric polynomial systems. INRIA Research report 5322, October 2004.

[2] A. Leykin, J. Verschelde, and A. Zhao. Newton’s method with deflation for isolated singularities of polynomial systems. Theoret. Comput. Sci. 359 (2006), 111–122.

[3] T.-Y. Li. Numerical solution of polynomial systems by homotopy continuation methods. Handbook of numerical analysis, Vol. XI, 209–304, North-Holland, Amsterdam (2003).

[4] C. Mavroidis and B. Roth. Analysis of overconstrained mechanisms. ASME Journal of Mechanical Design 117 (1995), 69–74.

[5] D. Mumford. Algebraic Geometry I, Grundlehren Math. Wiss. 221, Springer-Verlag, New York, (1976).

[6] A.J. Sommese and J. Verschelde. Numerical homotopies to compute generic points on positive dimensional algebraic sets. Journal of Complexity 16(3):572–602, 2000.

[7] A.J. Sommese, J. Verschelde and C.W. Wampler. Numerical decomposition of the solution sets of polynomial systems into irreducible components. SIAM J. Numer. Anal. 38(6):2022–2046, 2001.

[8] A.J. Sommese, J. Verschelde and C.W. Wampler. Symmetric functions applied to decomposing solution sets of polynomial systems. SIAM J. Numer. Anal. 40(6):2026–2046, 2002.

[9] A.J. Sommese, J. Verschelde, and C.W. Wampler. Homotopies for Intersecting Solution Components of Polynomial Systems. SIAM J. Numer. Anal. 42(4):1552–1571, 2004.

[10] A.J. Sommese, J. Verschelde, and C.W. Wampler. An intrinsic homotopy for intersecting algebraic varieties. Journal of Complexity 21:593– 608, 2005.

[11] A.J. Sommese, J. Verschelde, and C.W. Wampler. Solving Polynomial Systems Equation by Equation.

[12] A.J. Sommese and C.W. Wampler. Numerical algebraic geometry. In The Mathematics of Numerical Analysis, edited by J. Renegar, M. Shub, and S. Smale, volume 32 of Lectures in Applied Mathematics, pages 749–763, 1996. Proceedings of the AMS-SIAM Summer Seminar in Applied Mathematics, Park City, Utah, July 17-August 11, 1995, Park City, Utah.

[13] A.J. Sommese and C.W. Wampler. Numerical solution of systems of polynomials arising in engineering and science. World Scientific, Singapore (2005).

[14] K. Waldron. A study of overconstrained linkage geometry by solution of the closure equations—Part I. Method of study. Mechanism and Machine Theory 8 (1973), 95–104.