Numerical decomposition of the rank-deficiency set of a matrix of multivariate polynomials

Daniel J. Bates ^{∗}  Jonathan D. Hauenstein ^{†}
Christopher Peterson ^{‡}  Andrew J. Sommese ^{§}

June 30, 2008

Abstract Let A be a matrix whose entries are algebraic functions defined on a reduced quasiprojective algebraic set X, e.g., multivariate polynomials defined on X := ℂ^{N}. The sets S_{k}(A), consisting of x ∈ X where the rank of the matrix function A(x) is at most k, arise in a variety of contexts. For example, in the description of both the singular locus of an algebraic set and its fine structure; in the description of the degeneracy locus of maps between algebraic sets; and in the computation of the irreducible decomposition of the support of coherent algebraic sheaves, e.g., supports of finite modules over polynomial rings. In this article we present a numerical algorithm to efficiently compute the sets S_{k}(A). Keywords. rank deficiency, matrix of polynomials, homotopy continuation, irreducible components, numerical algebraic geometry, polynomial system, Grassmannians. AMS Subject Classification. 13CXX, 14Q15, 14M15, 15A54, 65H10, 65H20, 65E05

∗Institute for Mathematics and Its Applications (IMA), University of Minnesota, Minneapolis, MN 55455 (dbates1@nd.edu, http://www.nd.edu/∼dbates1)

†Department of Mathematics, University of Notre Dame, Notre Dame, IN 46556 (jhauenst@nd.edu, http://www.nd.edu/∼jhauenst). This author was supported by the Duncan Chair of the University of Notre Dame; the University of Notre Dame Center for Applied Mathematics; and NSF grants DMS-0410047 and NSF DMS-0712910

‡Department of Mathematics, Colorado State University, Fort Collins, CO 80523 (peterson@math.colostate.edu, http://www.math.colostate.edu/∼peterson). This author was supported by NSF grant MSPA-MCS-0434351 and AFOSR-FA9550-08-1-0166

§Department of Mathematics, University of Notre Dame, Notre Dame, IN 46556 (sommese@nd.edu, http://www.nd.edu/∼sommese). This author was supported by the Duncan Chair of the University of Notre Dame; and NSF grants DMS-0410047 and NSF DMS-0712910

Introduction

Let A be an m × n matrix with polynomial entries, i.e.,

A(x) := [ \begin{matrix}p_{1,1}(x) & ⋯ & p_{1,n}(x) \\ ⋮ & ... & ⋮ \\ p_{m,1}(x) & ⋯ & p_{m,n}(x) \end{matrix} ]  (1)

with p_{i,j}(x) ∈ ℂ[x_{1}, x_{2}, …, x_{N}] for 1 ≤ i ≤ m, 1 ≤ j ≤ n; and where x := (x_{1}, x_{2}, …, x_{N}) ∈ ℂ^{N}.

The main contribution of this article is an efficient numerical algorithm to decompose the algebraic sets

S_{k}(A) := {x ∈ ℂ^{N} | rankA(x) ≤ k}  (2)

for each k from 0 to min{m, n}. By computing the sets S_{k}(A), we also compute the algebraic subsets of ℂ^{N} where the rank of A(x) equals k, i.e., S_{k}(A) \ S_{k−1}(A). By taking adjoints and relabeling if necessary, we may assume that m ≥ n. By convention, S_{−1}(A) := ∅.

We work in the general setting of finding the irreducible decompositions of sets of the form S_{k}(A_{V (f)}), where f is a system of polynomials defined on ℂ^{N}; V (f) denotes the common zeros of f; and A_{V (f)} denotes the restriction of the matrix of polynomials in Eq. 1 to V (f). One advantage of this generality is that many related problems may be restated in this context. For example, given a matrix Â(x) of homogeneous polynomials on ℙ^{N} with degrees of entries compatible with the rank of Â(x) being well defined for each x ∈ ℙ^{N}, the irreducible components of S_{k}(Â) may be computed by regarding Â as a matrix of polynomials on ℂ^{N+1} with f(x) a single linear equation on ℂ^{N+1} having general coefficients.

In §1, we present background material. Besides reviewing the general setup of Numerical Algebraic Geometry, we highlight several results we will use in the article. In §2 we give a description of random coordinate patches on Grassmannians. This is a useful generalization of random coordinate patches for projective space [18], see also [30, §3.7]. The generalization applies more broadly to rational homogeneous manifolds.

The strategy of the algorithm presented in §3 is to work with the system

[ \begin{matrix}f(x) \\ A(x) · ξ \end{matrix} ] = 0,  (3)

where

f(x) := [ f_{1}(x) ; ⋮ ; f_{m}(x) ]  (4)

is a system of polynomials on ℂ^{N} and where

A(x) · ξ  (5)

is a parameterized family of ξ-linear equations with

ξ := [ ξ_{1} ; ⋮ ; ξ_{n} ] ∈ ℙ^{n−1}.

This is a standard construct which has been used multiple times in numerical algebraic geometry, though in cases much weaker information was sought. For example, systems which include terms of the form A(x) · ξ = 0, have occurred for deflation [15] and [30]; and for the degeneracy set of a map from a curve to ℂ, [16] and [2].

Using Eq. 5, one can compute the components of the set S_{n−1}(A) as the images of the irreducible components of the reduced solution set of Eq. 3: this is straightforward using the numerical irreducible decomposition available in Bertini [1] or PHC [32]. The computation of the components of the remaining S_{k}(A) is more subtle.

A natural approach to computing the structure of the sets S_{k}(A) would be to decompose the projection map V (A(x) · ξ) → ℂ^{N} into sets of constant dimension. This can be done using fiber products [31]. However, since the fibers of the map V (A(x) · ξ) → ℂ^{N} are linear subspaces of ℂ^{N}, it is natural to use Grassmannians to parameterize fibers of a given dimension. This leads to a considerably simpler and more efficient algorithm than the general fiber product approach.

Let Grass(a, b) be the Grassmannian of a-dimensional vector subspaces of ℂ^{b}; and let

𝕋(n; k, N) := ℂ^{N} × Grass(n − k, n),

where n denotes the number of columns of A(x). We consider the algebraic subset

E_{k}(A) := {(x, y) ∈ 𝕋(n; k, N) | A(x) · y = 0} .

Let π : ℂ^{N} × Grass(n − k, n) → ℂ^{N} be the map obtained by restricting the product projection from ℂ^{N} × Grass(n − k, n) to ℂ^{N}. The irreducible components of S_{k}(A) that are not irreducible components of S_{k−1}(A) are precisely the images under π of irreducible components of E_{k}(A) on which π is generically one-to-one. Thus, the problem reduces to setting up a polynomial system to compute E_{k}(A).

To set up this system we construct a coordinate system on a Zariski open set U ⊂ Grass(n − k, n) such that every irreducible component of S_{k}(A) that is not an irreducible component of S_{k−1}(A) is the closure of the image of an irreducible component of E_{k}(A) under the product projection π. This construction uses the random coordinate patches described in §2 and leads to the system

A(x) · B · [ \begin{matrix}I_{n−k} \\ Ξ \end{matrix} ] = 0,  (6)

where B is a generic n × n unitary matrix; I_{n−k} is the (n − k) × (n − k) identity matrix; and where

Ξ := [ \begin{matrix}ξ_{1,1} & ⋯ & ξ_{1,n−k} \\ ⋮ & ... & ⋮ \\ ξ_{k,n−k} & ⋯ & ξ_{k,n−k} \end{matrix} ] ,

is an element of ℂ^{k×(n−k)}. The solution components of the reduced solution set of Eq. 6 give the desired decomposition of E_{k}(A).

The system

[ \begin{matrix}f(x) \\ A(x) · B · [ \begin{matrix}I_{n−k} \\ Ξ \end{matrix} ] \end{matrix} ] = 0  (7)

allows us to compute the decomposition of S_{k}(A(x)_{V (f)}).

In §4, we discuss several generalizations. For example, we may compute the decomposition of S_{k}(A(x)_{X}), where X is an irreducible component of V (f). We also show how to deal with more general A(x), e.g., A(x) having entries that are algebraic functions on algebraic sets, or when A(x) is a map between vector bundles.

In §5, we present several applications. For example, if f(x) is a system of polynomials on ℂ^{N}, then applying the algorithm of §3 to the Jacobian

Jf(x) := [ \begin{matrix}\frac{∂f_{1}}{∂x_{1}} (x) & … & \frac{∂f_{1}}{∂x_{N}} (x) \\ ⋮ & ... & ⋮ \\ \frac{∂f_{m}}{∂x_{1}} (x) & … & \frac{∂f_{m}}{∂x_{N}} (x) \end{matrix} ]  (8)

computes the decomposition of the singular set of the solution set f^{−1}(0) of f. Note in this case that n = N. We use f^{−1}(0) to denote the solution set of f(x) = 0 with its induced scheme-theoretic structure, i.e., the schemetheoretic fiber of f : ℂ^{N} → ℂ^{m}. If a component Z of V (f) occurs with multiplicity at least two, then Z is contained in the singular set of f^{−1}(0).

In §6, we give implementation details and computational results in the context of several specific examples.

In appendix A, we show how to compute the singular set, Sing(V (f)), of the reduced algebraic set V (f), i.e., of the solution set of the radical of the ideal generated by f(x). We first recall in §A.1 that given an irreducible component Z of a solution set V (f) of a system of polynomials, there is a classical prescription, e.g., given in [19], to construct a system of polynomials g with Z = V (g). Then in §A.2, a modified version of this construction is combined with the algorithm in §3 to give an algorithm to compute the singular set of V (f).

Contents

1 Background Material 6 1.1 Genericity and Randomness . . . . . . . . . . . . . . . . . . . 6 1.2 The Numerical Irreducible Decomposition . . . . . . . . . . . 7 1.3 Images of Algebraic Sets . . . . . . . . . . . . . . . . . . . . . 10

2 Random Coordinate Patches on Grassmannians 11

3 Finding Rank-Dropping Sets 13

4 Generalizations 15

5 Applications 17 5.1 Support of a Module . . . . . . . . . . . . . . . . . . . . . . . 17 5.2 Degeneracy Sets of the Differential of a Map . . . . . . . . . . 18 5.3 Singular Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

6 Implementation Details and Computational Results 19 6.1 Singular Set for a Matrix . . . . . . . . . . . . . . . . . . . . 19 6.2 Singular Set for a Hessian Matrix . . . . . . . . . . . . . . . . 20 6.3 Singular Solutions for a Polynomial System . . . . . . . . . . 20

A The Singular Set of the Reduction of an Algebraic Set 21 A.1 Equations Defining an Algebraic Set . . . . . . . . . . . . . . 21 A.2 Computing the Singular Set of the Reduction of an Algebraic

Set . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

1 Background Material

We work over the complex numbers. By an algebraic set we mean a possibly nonreduced quasiprojective algebraic set X. The reduction of X is denoted by X_{red}.

Let f be a system of polynomials

f(x) := [ f_{1}(x) ; ⋮ ; f_{N−k}(x) ] = 0  (9)

on ℂ^{N}. By f^{−1}(0) we denote the solution set of f with its possibly nonreduced structure. By V (f) we denote the reduced algebraic set f^{−1}(0)_{red}.

An algebraic set X is irreducible if it has no embedded components and if the smooth points of its reduction X_{red} are connected. By the dimension of X, we mean the maximum of the dimensions of the connected components of the set of smooth points of X_{red}. We say that an algebraic set is pure dimensional if it has no embedded components and if the connected components of the set of smooth points of X_{red} all have the same dimension. Given a function G : A → B between sets, we denote the restriction of G to a subset C ⊂ A by G_{C}.

The main approach of Numerical Algebraic Geometry is to use intersections with generic affine linear spaces to reduce problems about positive dimensional algebraic sets to finding isolated solutions by homotopy continuation.

The use of intersections with affine linear spaces has been a standard tool in algebraic geometry for well over a century, e.g., see [3]. Affine slices, e.g., lifting fibers, have been used in related ways in symbolic work, e.g., [9, 10, 14]. For further discussion of this, see [29, §2.3]

The book [30] is a good reference for on Numerical Algebraic Geometry.

1.1 Genericity and Randomness

A major source of efficiency in Numerical Algebraic Geometry is the use of randomness. Typically, there is an irreducible algebraic set Q, which serves as a parameter space, and some property P for an object corresponding to a point in Q. We need to choose a point q ∈ Q for which P is true, though it might not hold for all parameter values. We say the property P holds generically if it is true for a nonempty Zariski open set U of Q.

For example, the polynomial f(x, q) := qx − 1 may be regarded as a family of polynomials in the variable x with parameter q in the parameter space Q := ℂ. The property that “f(x, q) = 0 has a solution” is true except when q = 0. Thus, this property holds generically.

Some algorithms depend on choosing q ∈ U. We typically do this using a random number generator, and refer to the object depending on the parameter chosen, e.g., a coordinate patch, as random or generic, e.g., a random coordinate patch. If our random number generator truly determines a random complex number, the probability of choosing a point in Q for which the property and the algorithm fails would be zero, and hence such algorithms are called probability-one algorithms. Of course, the numbers available on a computer are finite, but with error checking and use of high precision arithmetic, such algorithms may be designed to work very well. These matters are discussed further in [30].

The parameter spaces Q which we use are usually defined over ℂ, but there are times when we restrict our choice of a random point q ∈ Q to lie in a special subset. For example, we might have a property P that holds generically for points in the parameter space ℂ^{∗} := ℂ \ {0}, but for reasons of numerical stability, we might prefer to choose q to be of absolute value 1. Since the subset of S^{1} := {q ∈ ℂ^{∗} | |q| = 1}, for which P fails, is closed and has Lebesgue measure zero, choosing q randomly from S^{1} is justified. A slight generalization of this situation, which occurs in this article, is when the parameter space Q is GL(n, ℂ), Here, for reasons of numerical stability, we choose q ∈ U(n), the unitary group acting on ℂ^{n}. Since the intersection of U(n) with any proper algebraic subset X of GL(n, ℂ), is a closed set of Lebesgue measure zero, choosing q randomly from U(n) is justified. Remark 1. Note that if a complex semisimple group G is our parameter space, as it is in Remark 3, we could, for similar reasons, choose q randomly in a maximal compact subgroup of G.

1.2 The Numerical Irreducible Decomposition

Given a system of polynomials f(x) as in Eq. 9, the irreducible decomposition of V (f) is the decomposition

V (f) = ∪_{i=1}^{dim V (f)}Z_{i} = ∪_{i=1}^{dim V (f)} ∪_{j∈I_{i}} Z_{i,j},

where Z_{i} is a pure i-dimensional algebraic set; each set I_{i} is finite; and the Z_{i,j} are irreducible algebraic sets with the property that Z_{i,j} ⊂ Z_{a,b} if and only if (i, j) = (a, b). The Numerical Irreducible Decomposition of V (f) is the collection of

1. linear equations L_{1}(x), …, L_{n}(x) general with respect to all the Z_{i,j};

2. the sets W_{i,j} consisting of the deg Z_{i,j} smooth points V (L_{1}, …, L_{i}) ∩ Z_{i,j} of Z_{i,j} for each nonnegative integer i ≤ dim V (f) and each j ∈ I_{i}.

The elements of the W_{i,j} are called witness points for Z_{i,j}. This decomposition is developed in [23, 24, 25, 26]. See also [30]. The programs Bertini [1] and PHC [27, 32] compute this decomposition. As an algorithm, we have

Algorithm NumIrredDecomp \underline{Input}: A system of polynomials \{f_{1}(x), …, f_{m}(x)\} on ℂ^{N}. \underline{Output}: The dimension d = dim V (f);

the dimensions dim_{i,j} and degrees deg_{i,j} of the irreducible components Z_{i,j} of V (f) for j ∈ I_{i} with nonnegative integers i ≤ d; linear equations L_{1}(x), …, L_{n}(x) general with respect to all the Z_{i,j}; and witness sets W_{i,j} consisting of the deg Z_{i,j} smooth points V (L_{1}, …, L_{i}) ∩ Z_{i,j} of Z_{i,j} for each nonnegative integer i ≤ dim V (f) and each j ∈ I_{i}.

The algorithm as implemented also outputs auxiliary information needed for further computation, e.g., deflated systems, as discussed following Algorithm 1, which is needed to track paths on components whose multiplicity is greater than one.

By varying the linear equations, it is computationally inexpensive to generate additional points on each Z_{i,j}.

The membership test from [24, 25] gives a computation of the multiplicity of a point on the reduction of an irreducible algebraic set. Since a smooth point is precisely one of multiplicity one, this gives a criterion for a point to be a smooth point of the reduction of an algebraic set. Since we need this criterion in this article, let us state it as an algorithm.

Algorithm 1. CheckSmoothness \underline{Input}: A system of polynomials \{f_{1}(x), …, f_{m}(x)\} on ℂ^{N}; and a point x^{∗} on an irreducible component Z of V (f). \underline{Output}: The multiplicity μ of x^{∗} on Z_{red}.

Compute a set W of witness points w_{1}, …, w_{deg Z_{red}} for linear equations L := {L_{1}, …, L_{dim Z}} general with respect to Z.

Choose a system of linear equations L̂ := {L̂_{1}, …, L̂_{dim Z}} satisfying L̂_{i}(x^{∗}) = 0 and which other than this are general with respect to the choices made in previous steps.

Choose a general complex number γ satisfying |γ| = 1. Compute the limits Ŵ := {ŵ_{1}, …, ŵ_{deg Z_{red}}} of the paths

Z ∩ V (tL(x) + γ(1 − t)L̂(x)) starting at W and traced as t goes from 1 to 0.

Set μ equal to the number of points of Ŵ equal to x^{∗}.

There are a number of numerical issues that must be dealt with in implementations of this algorithm. If Z is not generically reduced, then tracking must be done using a deflated system. Deflation for isolated points was developed in [15]: see also [8, 14, 20, 21]. For the deflation of irreducible components and the use of it for tracking paths see [30, §13.3.2 and §15.2.2]. Another numerical issue is how to decide equality. These matters are discussed in [30].

We need to compute generic fiber dimensions in the main algorithm of this article; the following suffices.

Algorithm FiberDimension \underline{Input}: A system of polynomials \{f_{1}(x), …, f_{m}(x)\} on ℂ^{N}; a polynomial map Φ : ℂ^{N} → ℂ^{s} with Φ(x) = (Φ_{1}(x), …, Φ_{s}(x)); and a point x^{∗} ∈ V (f). \underline{Output}: The dimension at x^{∗} of the fiber of Φ_{V (f)} containing x^{∗}.

This is a simple consequence of having NumIrredDecomp. First compute

NumIrredDecomp(f_{1}(x), …, f_{m}(x), Φ_{1}(x) − Φ_{1}(x^{∗}), …, Φ_{s}(x) − Φ_{s}(x^{∗})).

Now do a membership test using the witness sets from this computation to find which components of the Irreducible Decomposition of

V (f_{1}(x), …, f_{m}(x), Φ_{1}(x) − Φ_{1}(x^{∗}), …, Φ_{s}(x) − Φ_{s}(x^{∗}))

contain x^{∗}. The maximum of the dimensions dim_{i,j} among these components gives the desired dimension.

1.3 Images of Algebraic Sets

What is required for the numerical irreducible decomposition is data that allows us to carry out homotopy continuation. Often this is a system of equations on the Euclidean space which contains the algebraic set, but this is not necessary.

With deflation of a multiple k-dimensional component Z of a system f(x) = 0 [30, §13.3.2 and §15.2.2], we have a system of the form

D(f, Z) := [ \begin{matrix}f(x) \\ A(x) · [ \begin{matrix}1 \\ ξ \end{matrix} ] \\ c · ξ − 1 \end{matrix} ] = 0

with x ∈ ℂ^{N}; ξ ∈ ℂ^{n}; A(x) is a s × (n + 1) matrix of polynomials; and c a (n + N − s − k) × n matrix of constants. The key property of the system D(f, Z) is that there is a multiplicity one component Z′ of D(f, Z)^{−1}(0) which maps generically one-to-one onto Z under the product projection (x, ξ) → x. To carry out operations such as tracking a path on Z as a complementary linear space L moves, it suffice to track the path cut out on Z′ as the pullback of L to ℂ^{N+n} moves.

Similarly, assume that we have a system of polynomials

F(x_{1}, …, x_{N}; ξ_{1}, …, ξ_{n}) = 0

on ℂ^{N+n}. Let π : ℂ^{n+r} → ℂ^{r} denote the product projection. Let Z be an irreducible component of V (F). Given this information, it is straightforward to numerically work with the closure \overline{π(Z)} of the image of Z by lifting computations to Z.

This is the special situation that occurs in this article, assuming that each fiber of π_{Z} is a linear space but with possibly varying dimensions. Using FiberDimension, compute the dimension v of the fiber of π_{Z} containing a witness point of Z. Now choose v general linear equations L_{1}, …, L_{v} in the x variables. There is a unique component Z′ of Z ∩ V (L_{1}, …, L_{v}) which maps generically one-to-one onto π(Z). For numerical continuation this is as good as having the equations for \overline{π(Z)}.

In several algorithms we will manipulate irreducible components of an algebraic set. Numerically we always use the Numerical Irreducible Decomposition, but with the possibility that the equations are defined on an auxiliary space as above.

2 Random Coordinate Patches on Grassmannians

The Grassmannian Grass(a, b) parameterizes all a-dimensional vector subspaces of ℂ^{b}. When a = 1, this is the usual (b − 1)-dimensional projective space, ℙ^{b−1}. An a-dimensional vector subspace S of ℂ^{b} is specified uniquely by a linearly independent vectors v_{1}, …, v_{a} in ℂ^{b}. It is convenient to regard these as forming a b × a matrix

[ v_{1} ⋯ v_{a} ] .  (10)

Note that if v′_{1}, …, v′_{a} is a second basis of S, then there is an invertible a×a matrix T of complex numbers such that

[ v′_{1} ⋯ v′_{a} ] = [ v_{1} ⋯ v_{a} ] · T.

Grass(a, b) is an a(b−a)-dimensional projective manifold on which the group GL(b) of invertible b × b matrices g acts homogeneously under the action

[ v_{1} ⋯ v_{a} ] → g · [ v_{1} ⋯ v_{a} ] .

More details on Grassmannians may be found in [12, 13].

Random Coordinate Patches A basic numerical trick, first exploited in [18] to find isolated solutions in ℂ^{N} or ℙ^{N}, is to carry out all computation on a random Euclidean coordinate patch on ℙ^{N}. The advantage of this trick is that, with probability one, all solutions of the system are now finite, and so for the purposes of computation, points at infinity may be treated as finite (albeit such points are often highly singular). Though no patch can contain a positive dimensional solution component at infinity, a general coordinate patch meets every irreducible component of a solution set in a Zariski open set of the given component. For this reason, this same trick is widely used in Numerical Algebraic Geometry [30].

In this article, we have need of a random patch on a Grassmannian Grass(a, b) of linear vector subspaces ℂ^{a} ⊂ ℂ^{b}. A straightforward generalization of the above trick is to embed Grass(a, b) in P := ℙ^{\binom{b}{a}−1} and pullback a random patch from P. This patch is complicated to work with because of the number of variables involved and because of the nonlinearity of the conditions for a point to be on the patch.

There is a much better way to choose a random patch, which is particularly efficient for numerical computation. We present the approach and justification for choosing the patch in the following paragraphs.

Let B be a b × b unitary matrix. Then for a coordinate patch we take

B · [ \begin{matrix}1 & ⋯ & 0 \\ ⋮ & ... & ⋮ \\ 0 & ⋯ & 1 \\ ξ_{1,1} & ⋯ & ξ_{1,a} \\ ⋮ & ... & ⋮ \\ ξ_{b−a,1} & ⋯ & ξ_{b−a,a} \end{matrix} ] .  (11)

We often abbreviate this as

B · [ \begin{matrix}I_{a} \\ Ξ \end{matrix} ]

where I_{a} denotes the a × a identity matrix.

Theorem 2. Let W be an arbitrary algebraic set and let T denote an algebraic subset of W × Grass(a, b). Given a unitary matrix B, let U_{B} denote the Zariski open set of Grass(a, b) for which

B · [ \begin{matrix}I_{a} \\ Ξ \end{matrix} ]

are coordinates. There is an open dense subset U of the unitary matrices U(n) such that the Lebesgue measure of U(n) \ U is zero and such that for B ∈ U, (W × U_{B}) ∩ T is a non-empty Zariski open subset of T .

Proof. By the discussion in §1.1, it suffices to show this for generic B in the general linear group, GL(n, ℂ). For the closure of (W ×U_{B})∩T to not contain a component C of T is an algebraic condition, i.e., a condition picking out an algebraic subset of the General linear group. Let D_{C} denote this algebraic subset of GL(n, ℂ). The set, D_{C}, is a proper subset due to the fact that U_{B} may be chosen to contain any particular point of Grass(a, b). Let C denote the set of components of T . Since T has finitely many components, any invertible matrix B in the complement of ∪_{C∈C}D_{C} will suffice.

Remark 3. Let X be a rational homogeneous projective manifold. The Borel-Remmert characterization [5, 22] of such manifolds is that they are the compact Kähler manifolds X with a complex semisimple group G as biholomorphism group, and such that there is a parabolic subgroup P of G with X biholomorphic to G/P with its natural complex structure. Thus X possesses a conjugation with fixed points a maximal compact subgroup K with dim_{ℝ} K = dim_{ℂ} Aut(X). The analogous notion of a random coordinate patch would be the set gU, where g is a general element of K and U is any dense Bruhat Cell. More details on parabolic subgroups and Bruhat decompositions may be found in [6, §3 and §11]

3 Finding Rank-Dropping Sets

Let A be an m × n matrix with polynomial entries as in Eq. 1 and let f(x) denote the system as in Eq. 9. By taking adjoints and relabeling if necessary, we may assume without loss of generality that m ≥ n. Let S_{k}(A) := {x ∈ ℂ^{N} | rankA(x) ≤ k}. Since the rank of A(x) can be at most n, we may restrict ourselves to computing S_{k}(A) for k ≤ n.

For each k, S_{k}(A_{V (f)}) is algebraic since it is the solution set of the system comprised of f_{1}(x), …, f_{n}(x) plus the determinants of all k × k subminors of A. The irreducible components Z of S_{k}(A), with the property that rankA(x^{∗}) = k for a general point x^{∗} ∈ Z, are precisely the irreducible components of S_{k}(A), which are not components of S_{k−1}(A).

The sets S_{k}(A_{V (f)}) may theoretically be computed via Gröbner basis techniques by solving each of these systems with software such as CoCoA, Macaulay, or Singular [7, 17, 11]. However, for many applications, the system of determinants of all k × k subminors of A is impractically large and

complex. Such systems consist of \binom{m}{k}\binom{n}{k} equations with degrees consid-

erably larger than those of the entries of A. As a result, this approach will only work when both the size of A and the degrees of the entries of A are relatively small. We follow an alternative approach.

Our starting point is the system

[ \begin{matrix}p_{1,1}(x) & ⋯ & p_{1,n}(x) \\ ⋮ & ... & ⋮ \\ p_{m,1}(x) & ⋯ & p_{m,n}(x) \end{matrix} ] · [ ξ_{1} ; ⋮ ; ξ_{n} ] = 0  (12)

where [ξ_{1}, …, ξ_{n}] is a set of homogeneous coordinates on ℙ^{n−1}. We let T (A) denote the solution set of Eq. 12. Let π : T (A) → ℂ^{N} and σ : T (A) → ℙ^{n−1} denote the maps induced by the product projections of ℂ^{N} × ℙ^{n−1}.

We let T (A)_{y} ⊂ ℙ^{n−1} denote the solution set of the fiber of T (A) over y regarded as a subset of ℙ^{n−1}, i.e., T (A)_{y} = σ(π^{−1}(y)). In this setting, we have

y ∈ S_{k}(A) if and only if dim T (A)_{y} ≥ n − 1 − k.

While computing the irreducible decomposition of T (A) provides a great deal of information, it does not allow for the full determination of the sets

S_{k}(A) = {y ∈ ℂ^{N}| dim T (A)_{y} ≥ n − 1 − k}.

One could completely determine these sets by applying the fiber product algorithm as developed in [31]. However, since we want to find fibers of π that are points in Grass(n − k, n), there is a different approach which has the advantage of being computationally more efficient.

The approach is to consider the system

F_{k}(f) := [ \begin{matrix}f(x) \\ A(x) · B · [ \begin{matrix}I_{n−k} \\ Ξ \end{matrix} ] \end{matrix} ] = 0  (13)

where B is a random n × n unitary matrix; I_{n−k} is the (n − k) × (n − k) identity matrix; and Ξ is an k × (n − k) matrix of indeterminates ξ_{i,j}. The discussion in §2 gives the following result.

Theorem 4. Let A be an m × n matrix with polynomial entries in Eq. 1 and let f(x) denote the system as in Eq. 9. Assume that m ≥ n. For a generic B in the n × n unitary group, and a nonnegative integer k between 0 and n, let F_{k}(f) denote the system in Eq. 13. Let A_{k} denote the set of the irreducible components of S_{k}(A_{V (f)}), which are not irreducible components of S_{k−1}(A_{V (f)}). Let B_{k} denote the set made up of the closures of the images under π of the irreducible components Z of V (F_{k}(f)), such that the generic fiber of the projection from Z to ℂ^{N} is zero dimensional, i.e., such that A(x) is of rank k at the image under π of a witness point of Z. The sets in A_{k} are the maximal elements under set inclusion of the elements of B_{k}.

Note we can use a membership test to determine inclusion relations.

Algorithm 2. RankDropSet \underline{Input}: A system of polynomials \{f_{1}(x), …, f_{m}(x)\} on ℂ^{N};

a matrix of polynomials A(x) := [ \begin{matrix}p_{1,1}(x) & ⋯ & p_{1,n}(x) \\ ⋮ & ... & ⋮ \\ p_{m,1}(x) & ⋯ & p_{m,n}(x) \end{matrix} ] on ℂ^{N}; and

a nonnegative integer k. \underline{Output}: The Numerical Irreducible Decomposition of the set S_{k}(A_{V (f)}).

Choose a random unitary matrix B ∈ U(n).

Compute NumIrredDecomp of the system in Eq. 13.

Use FiberDimension to pick out the set Z of irreducible components Z

with fibers having generic fiber dimension zero. Output the projection of the components Z ∈ Z in ℂ^{N} × ℂ^{k(n−k)} to

ℂ^{N} under the product projection.

In line with the discussion of §1.3, we have not explicitly given the details of the standard steps to compute the full witness sets for the components output in the last line of the algorithm. For the convenience of the reader, we give a brief discussion of steps involved.

Fix an a-dimensional component Z ∈ Z with fiber dimension zero. Let L̂ denote the generic a-codimensional affine linear subspace of ℂ^{N+k(n−k)} with W_{Z} := L̂ ∩ Z the witness points of Z.

Under the product projection, ℂ^{N} × ℂ^{k(n−k)}, Z has, as image in ℂ^{N}, a dense constructible subset A of an algebraic subset B of ℂ^{N}. Choose a generic a-codimensional affine linear subspace L ⊂ ℂ^{N}. A contains a dense Zariski open subset O of B, see for example [30, Lemma 12.5.8 and 12.5.9]. L meets O in deg B points. The witness points L ∩ B for B may be simply computed from the known witness points W_{Z} of Z.

To do this, pull back L to an a-codimensional affine linear subspace L′ of ℂ^{N+k(n−k)}. Using a homotopy deforming L̂ to L′, we can, starting with the points W_{Z} find the set of points W′ := L′ ∩ Z. The images in ℂ^{N}, of the points W′, are the witness points L ∩ B.

4 Generalizations

Theorem 4 and the corresponding algorithm are stated for a matrix of polynomials on ℂ^{N}. These results hold much more generally.

Using Open Zariski Subsets Since we work with witness points, we can replace ℂ^{N} with a nontrivial Zariski open set U. Indeed, either

1. U meets a d-dimensional component Z of V (f) ⊂ ℂ^{N} in a nontrivial Zariski open set: or

2. U ∩ Z is empty.

In the first case, a generic N − d dimensional linear space that meets Z in deg Z points will with probability one meet Z ∩ U in deg Z points.

Restriction of A to an Irreducible Set Let f and A be as in §3. Let X be an irreducible component of V (f). It is straightforward to find S_{k}(A_{X}). We have found that each component Z of S_{k}(A_{V (f)}) is the closure of the image of an irreducible set Z′ from V (f) × Grass(n − k, n) under the product projection π with general fiber dimension zero. Using [28], we can find the irreducible components Z′′ of the sets Z′ ∩ [X × Grass(k, N)]. The set S_{k}(A_{X}) is precisely the union of the closures of the images under π of the components Z′′ with general fiber dimension under π equal to zero.

Algebraic Functions instead of Polynomials The results of §3 hold for the restriction of A(x), made up of algebraic functions defined on a Zariski open set U of ℂ^{N}, to the solution set of a system of polynomials f(x) = 0 defined on ℂ^{N}. For example, A(x) is a matrix of rational functions on ℂ^{N} and U is the complement on ℂ^{N} of the union of the pole sets of the entries of A(x). By clearing the denominators, we have reduced to a polynomial matrix.

Algebraic Vector Bundle Maps Let F and G be algebraic vector bundles of ranks n and m, respectively, defined on a quasiprojective manifold Y. Let A be an element of Hom(F, G), i.e., an algebraic section of F^{∗} ⊗_{ℂ} G. Let F be a section of an algebraic vector bundle H on Y and let X ⊂ Y be an algebraic subset of the set of zeroes of F. For each integer k ≥ 0, the set S_{k}(A) of points y ∈ Y where rank(A) ≤ k is an algebraic subset of Y. The set S_{k}(A_{X}) is also algebraic. By convention, S_{−1}(A) = ∅.

We wish to decompose S_{k}(A_{X}) into irreducible components. Since algebraic vector bundles are locally free in the Zariski topology, this general situation may be reduced to finding S_{k}(A_{V (f)}) ∩ U for a matrix A of polynomials on some Zariski open set U of ℂ^{N} and a system of polynomials f(x) = 0.

The only practical case of this generalization is the case where f is a system of homogeneous polynomials on ℙ^{N} and A(x) is a matrix of homogeneous polynomials whose degrees are compatible with the rank drop loci being considered to lie in ℙ^{N}.

To be explicit, let O_{ℙ^{N}}(k) denote the sheaf of algebraic sections of the k-th power of the hyperplane section bundle on ℙ^{N}, i.e., the rank one locally free coherent algebraic sheaf whose sections are the homogeneous polynomials of degree k. Consider an O_{ℙ^{N}} linear mapping A of the form

A : ⨁_{i=1}^{m} O_{ℙ^{N}}(a_{i}) → ⨁_{j=1}^{n} O_{ℙ^{N}}(b_{j}).  (14)

A is represented by a matrix of homogeneous polynomials with deg A_{i,j}(x) = b_{j} − a_{i}. For a matrix of this form, the rank of A(x) is well defined for any given point in projective space. Choosing a generic Euclidean coordinate patch U ≈ ℂ^{N} on ℙ^{N}, U meets each irreducible component of each S_{k}(A) in a Zariski open dense set.

To set up the equations, regard A as a matrix of homogeneous polynomials on ℂ^{N+1} and f as a system of homogeneous polynomials on ℂ^{N+1}. Let c · x − 1 be a general linear equation on ℂ^{N+1} with ℙ^{N} \ U defined by c · x = 0. The system for S_{k}(A_{V (f)}) is

[ \begin{matrix}f(x) \\ A(x) · B · [ \begin{matrix}I_{n−k} \\ Ξ \end{matrix} ] \\ c · x − 1 \end{matrix} ] = 0  (15)

where we regard A as an m × n matrix of polynomials on ℂ^{N+1} (thus x is a vector of N + 1 indeterminates); B is a random n × n unitary matrix; I_{n−k} is the (n − k) × (n − k) identity matrix; Ξ is a k × (n − k) matrix of indeterminates ξ_{i,j}; and c is a generic unit vector on ℂ^{N+1}.

5 Applications

We present three applications of our algorithm:

1. the numerical irreducible decomposition of the support of a finite module over a ring of algebraic functions, i.e., of a coherent algebraic sheaf on an algebraic set;

2. the decomposition into sets where the differential of an algebraic map is of constant rank: one special case of this is the computation of the singular set of an algebraic set; and

3. the singular set of an algebraic set.

In each of the following applications we work over ℂ^{N}. Generalizations, e.g., to quasiprojective manifolds, follow from the ideas outlined in §4.

5.1 Support of a Module

Let O_{alg,U} denote the sheaf of algebraic functions on a Zariski open set U ⊂ ℂ^{N}. A finitely generated coherent algebraic sheaf F is the quotient sheaf of an O_{alg,U}-linear map

⨁_{i=1}^{n} O_{alg,U} → ⨁_{i=1}^{m} O_{alg,U}.

Such a map is given by an m×n matrix of algebraic functions A(x). Entries

A_{i,j}(x) of A(x) are rational functions, which must be of the form \frac{p_{i,j}(x)}{q_{i,j}(x)} for

polynomials p_{i,j}(x) and q_{i,j}(x) with the solution set of q_{i,j}(x) = 0 contained in ℂ^{N} \U. Decomposing the support of F is the same as computing the sets S_{k}(A).

5.2 Degeneracy Sets of the Differential of a Map

Let X denote the solution set of a system of polynomials f(x) = 0 (as in Eq. 9) defined on ℂ^{N}. Let Jf(x) denote its Jacobian matrix as in Eq. 16. For simplicity, let π_{X} : X → ℂ^{M} be the restriction to X ⊂ ℂ^{N} of a surjective linear projection from π : ℂ^{N} → ℂ^{M}. Let n := N − M and let R denote an N × n matrix of orthonormal vectors spanning the n-dimensional vector subspace of ℂ^{N}, which is the fiber of π containing the origin of ℂ^{N}. If X is irreducible and π(X) is dense in ℂ^{M}, then the degeneracy for the map π_{X} is the set of points x^{∗} ∈ X where the rank of the (m × n)-matrix

Jf(x^{∗}) · R

is less than n.

5.3 Singular Sets

The special case in §5.2 when M = 0 is of special interest. For simplicity assume that we are trying to find the singular set of a possibly nonreduced pure k-dimensional algebraic set X defined by a system of N −k polynomials on ℂ^{N} as in Eq. 9, with Jacobian matrix

Jf(x) := [ \begin{matrix}\frac{∂f_{1}}{∂x_{1}} & ⋯ & \frac{∂f_{1}}{∂x_{N}} \\ ⋮ & ... & ⋮ \\ \frac{∂f_{N−k}}{∂x_{1}} & ⋯ & \frac{∂f_{N−k}}{∂x_{N}} \end{matrix} ] .  (16)

The singular set consists of those points x^{∗} ∈ X such that

rank_{x^{∗}}Jf(x) < N − k.

The results apply immediately to this situation. We codify this for use in the Appendix. For a matrix A, we denote the transpose by A^{T}.

Algorithm 3. FindSchemeTheoreticSingularSet \underline{Input}: A system of polynomials \{f_{1}(x), …, f_{N−k}(x)\} on ℂ^{N}; with V (f) pure k-dimensional. \underline{Output}: RankDropSet(f, (Jf)^{T} , N − k − 1).

Note that it may well turn out that the set produced by the previous algorithm is the singular set of V (f) = f^{−1}(0)_{red}. It is simple to check this. Given a witness point x^{∗} on a component Z of FindSchemeTheoreticSingularSet(f), we have that with probability one, Z ⊂ Sing(V (f)) if either x^{∗} is contained in more than one irreducible component of V (f) or x^{∗} is contained in a single component X of V (f) and CheckSmoothness(f, X, x^{∗}) > 1.

6 Implementation Details and Computational Results

The computational examples discussed here were run on an Opteron 250 processor running Linux using the numerical irreducible decomposition [23] implemented in the Bertini software package [1], which is under development by the first, second and fourth authors and Charles Wampler of GM Research and Development.

6.1 Singular Set for a Matrix

Consider the matrix

A(a, b, c, d, e, f) = [ \begin{matrix}0 & a & b & c \\ −a & 0 & d & e \\ −b & −d & 0 & f \\ −c & −e & −f & 0 \end{matrix} ]

Clearly, S_{0}(A) = {(0, 0, 0, 0, 0, 0)}. One can compute S_{1}(A) = S_{0}(A) and

S_{2}(A) = S_{3}(A) = {(a, b, c, d, e, f) : af + cd − be = 0}.

It should be noted that det(A) = (af + cd − be)^{2}.

Bertini identified the components numerically for S_{0}(A) in 0.03s, S_{1}(A) in 6.47 seconds, S_{2}(A) in 5.77 seconds, and S_{3}(A) in 0.40 seconds.

6.2 Singular Set for a Hessian Matrix

For a given polynomial g : ℂ^{N} → ℂ, consider computing the singular set of its Hessian matrix H_{g}(x) where

H_{g}(x)_{ij} = \frac{∂^{2}g}{∂x_{i}∂x_{j}} (x).

In particular, consider the polynomial g(x, y, z) = x^{3} + x^{2} + 2xy^{2} − y^{3} + 3yz^{2} + z^{3} which has the Hessian matrix

H_{g}(x, y, z) = [ \begin{matrix}6x + 2 & 4y & 0 \\ 4y & 4x − 6y & 6z \\ 0 & 6z & 6y + 6z \end{matrix} ] .

By inspection, S_{0}(H_{g}) = ∅. One can compute

S_{1}(H_{g}) = \{(0, 0, 0), (−\frac{1}{3}, 0, −\frac{2}{9}) , (−\frac{1}{3}, 0, 0)\}

and

S_{2}(H_{g}) = {(x, y, z) : det(H_{g}(x, y, z)) = 0}.

Bertini identified the components numerically for S_{0}(A) in 0.01 seconds, S_{1}(A) in 0.30 seconds, S_{2}(A) in 0.18 seconds.

6.3 Singular Solutions for a Polynomial System

Consider computing the singular solutions of the cyclic-4 system [4] given by

f(x_{1}, x_{2}, x_{3}, x_{4}) = [ \begin{matrix}x_{1} + x_{2} + x_{3} + x_{4} \\ x_{1}x_{2} + x_{2}x_{3} + x_{3}x_{4} + x_{4}x_{1} \\ x_{1}x_{2}x_{3} + x_{2}x_{3}x_{4} + x_{3}x_{4}x_{1} + x_{4}x_{1}x_{2} \\ x_{1}x_{2}x_{3}x_{4} − 1 \end{matrix} ] .

It is well-known that V (f) = {(x_{1}, x_{2}, x_{3}, x_{4}) : f(x_{1}, x_{2}, x_{3}, x_{4}) = 0} has two irreducible quadric curve components given by {(x_{1}, x_{2}, −x_{1}, −x_{2}) : x_{1}x_{2} = 1} and {(x_{1}, x_{2}, −x_{1}, −x_{2}) : x_{1}x_{2} = −1}. Denoting the Jacobian of f as Jf, for this system Sing(V (f)) = V (f) ∩ S_{2}(Jf) is the set of solutions of f with exceptional rank. The polynomial system that defines Sing(V (f)) consists of 12 polynomials in 8 variables. Bertini performed a full numerical irreducible decomposition on this system in 4.45 minutes to discover that Sing(V (f)) consists of 8 isolated points, namely

Sing(V (f)) = \{(a, \frac{1}{a}, −a, \frac{1}{a}) , (a, −\frac{1}{a}, −a, \frac{1}{a}) : a = ±1, ±\sqrt{−1}\} .

A The Singular Set of the Reduction of an Algebraic Set

Let f := {f_{1}(x), …, f_{m}(x)} denote a system of polynomials on ℂ^{N}. In this section we give an algorithm FindSingularSet, which starting with the input f, outputs a system of polynomials I satisfying Sing(V (f)) = V (I). Combined with DefiningEquations from §A.1, this constructs the singular set of any algebraic subset of ℂ^{N}. Repetition of FindSingularSet on its output I while dim V (I) ≥ 0 finds the sequence of sets

Sing(V (f)), Sing(Sing(V (f))_{red}), …

A.1 Equations Defining an Algebraic Set

In [23], the membership test for whether a solution x^{∗} of a polynomial system f(x) on ℂ^{N} as in Eq. 9 was based on the construction using interpolation of polynomials of appropriate polynomials vanishing on irreducible components of V (f). Using such polynomials as we do here is classical, e.g., [19].

Let us recall the construction. Let Z be a k-dimensional irreducible degree d component of V (f) and let S ⊂ ℂ^{N} be a finite set of points not contained in Z. Given a general projection π : ℂ^{N} → ℂ^{k+1}, π_{Z} is generically one-to-one and π(Z) is a degree d hypersurface not containing π(S). There is a degree d polynomial p_{π} on ℂ^{k+1}, unique up to multiplication by a non-zero complex number, with V (p_{π}) = π(Z). Thus composition p_{π}(π(x)) yields a degree d polynomial on ℂ^{N} that vanishes on Z but not at any point of S.

Now let us construct a system of polynomials g(x) such that Z = V (g). We follow the convention that the dimension of the empty set is −1.

Algorithm 4. DefiningEquations \underline{Input}: A system of polynomials \{f_{1}(x), …, f_{m}(x)\} on ℂ^{N}; and an irreducible component Z of V (f). \underline{Output}: A system F of polynomials on ℂ^{N} with the property that

Z = V (F).

Set K equal to the maximum dimension of the set of irreducible

components of V (f) other than Z. Set j = 0.

Set F_{j} := {f_{1}, …, f_{m}}.
while K ≥ 0 do

Set S equal a finite set consisting of one witness point from each component of V (F_{j}) except Z.

Set p equal to a degree d polynomial vanishing on Z, but not at

any point of S. Increment j by 1. Set F_{j} := F_{j−1} ∪ {p}. Set K equal to the maximum dimension of the set of

irreducible components of V (F_{j}) other than Z.

To see why the algorithm works, note that Z is still a component of V (F_{j}), and therefore if K ≠ −1, p is a nontrivial polynomial vanishing on Z and not identically zero on any other component of V (F_{j} ∪ {p}). Thus it follows that the maximum dimension of the set of irreducible components of V (F_{j}) other than Z is strictly less than the maximum dimension of the set of irreducible components of V (F_{j−1}).

We have the following classical result [19].

Lemma 5. Given a pure k-dimensional algebraic subset Z ⊂ ℂ^{N}, and a point x^{∗} ∈ Z \ Sing(Z), it follows that there are n − k degree d polynomials

p_{x^{∗},1}(x), …, p_{x^{∗},n−k}(x)

such that:

1. Z is a component of V (p_{x^{∗},1}(x), …, p_{x^{∗},n−k}(x)); and

2. the Jacobian matrix

[ \begin{matrix}\frac{∂p_{x^{∗},1}}{∂x_{1}} (x) & … & \frac{∂p_{x^{∗},1}}{∂x_{N}} (x) \\ ⋮ & ... & ⋮ \\ \frac{∂p_{x^{∗},N−k}}{∂x_{1}} (x) & … & \frac{∂p_{x^{∗},N−k}}{∂x_{N}} (x) \end{matrix} ]

evaluated at x^{∗} has rank N − k.

The proof proceeds by noting that N − k general projections π_{1}(x) = c_{1} · x, …, π_{N−k} := c_{N−k} · x from ℂ^{N} → ℂ^{k+1} give embeddings of Z in a Zariski open neighborhood of x^{∗} and the matrix

[ c_{1} ; ⋮ ; c_{N−k} ]

has rank N − k. For each i = 1, …, N − k, letting p_{i} denote a polynomial of degree d vanishing on π_{i}(Z), the polynomials p_{x^{∗},i} := p_{i}(π_{i}(x)) satisfy the conclusions of Lemma 5.

Combining DefiningEquations with the procedure outlined following Lemma 5, we have the following algorithm.

Algorithm 5. NormalCoordinates \underline{Input}: A system of polynomials \{f_{1}(x), …, f_{m}(x)\} on ℂ^{N}; an irreducible component Z of V (f); and a smooth point x^{∗} ∈ Z. \underline{Output}: A system F of polynomials on ℂ^{N} with the properties that

Z is an irreducible component of V (F) and F^{−1}(0) is reduced at x^{∗}.

A.2 Computing the Singular Set of the Reduction of an Algebraic Set

Algorithm 6. FindSingularSet \underline{Input}: A system of polynomials \{f_{1}(x), …, f_{m}(x)\} on ℂ^{N}; and a general point x^{∗} on a k-dimensional irreducible component Z of V (f). \underline{Output}: A system F of equations with Sing(V (f)) = V (F).

Set K := dim Z.

Set j = 0.

Set F_{j} := DefiningEquations(f, Z).

Set B := {Z}.

Set B′ equal to a set with one point x^{∗}, where x^{∗} is a witness point of Z. While K ≥ −1 do

Increment j to j + 1.

Set F_{j} := F_{j−1} ∪_{x^{∗}∈B′} NormalCoordinates(F, Z, x^{∗}) Compute A := FindSchemeTheoreticSingularSet(F_{j}). Use CheckSmoothness to find the set B of components A not

contained in Sing(Z). Set B′ equal to a set with exactly one witness point for each

component of B. Set K := max_{X∈B} dim X.

Output F_{j}.

References

[1] D.J. Bates, J.D. Hauenstein, A.J. Sommese, and C.W. Wampler. Bertini: Software for Numerical Algebraic Geometry. Available at

    www.nd.edu/∼sommese/bertini.

[2] D. Bates, C. Peterson, A.J. Sommese, and C.W. Wampler. Numerical computation of the genus of an irreducible curve within an algebraic set. 2007 preprint.

[3] M. Beltrametti and A.J. Sommese. The adjunction theory of complex projective varieties. Expositions in Mathematics, 16, Walter De Gruyter, Berlin, 1995.

[4] G. Björck and R. Fröberg. A faster way to count the solutions of inhomogeneous systems of algebraic equations, with applications to cyclic n-roots. Journal of Symbolic Computation 12 (1991), 329–336.

[5] A. Borel and R. Remmert. Über kompakte homogene Kählersche Mannigfaltigkeiten. Mathematische Annalen 145 (1961/1962), 429–439.

[6] A. Borel. Introduction aux groupes arithmétiques/ Publications de l’Institut de Mathématique de l’Université de Strasbourg, XV. Actualités Scientifiques et Industrielles, No. 1341, Hermann, Paris, (1969).

[7] CoCoATeam. CoCoA: a system for doing Computations in Commutative Algebra. Available at cocoa.dima.unige.it.

[8] B. Dayton and Z. Zeng. Computing the multiplicity structure in solving polynomial systems. Proceedings of ISSAC 2005 (Beijing, China), 116– 123, 2005.

[9] M. Giusti and J. Heinz. Kronecker’s smart, little black boxes. In Foundations of Computational Mathematics edited by DeVore, R.A. and Iserles, A. and Süli, E., volume 284 of London Mathematical Society Lecture Note Series, pages 69–104. Cambridge University Press, 2001.

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

[11] G.-M. Greuel, G. Pfister, and H. Schönemann. Singular 3.0. A Computer Algebra System for Polynomial Computations. Centre for Computer Algebra, University of Kaiserslautern (2005). Available at

www.singular.uni-kl.de.

[12] P.A. Griffiths and J. Harris. Principles of algebraic geometry. Wiley Classics Library, Reprint of the 1978 original, John Wiley & Sons Inc., New York, 1994.

[13] W.V.D. Hodge and D. Pedoe. Methods of algebraic geometry. Vol. II, Reprint of the 1952 original, Cambridge University Press, Cambridge, 1994.

[14] G. Lecerf, Computing the equidimensional decomposition of an algebraic closed set by means of lifting fibers, J. Complexity 19 (2003), 564–596.

[15] A. Leykin, J. Verschelde, and A. Zhao. Newton’s method with deflation for isolated singularities of polynomial systems. Theoretical Computer Science 359 (2006), 111-122.

[16] Y. Lu, D. Bates, A.J. Sommese, and C.W. Wampler. Finding all real points of a complex curve, In Algebra, Geometry and Their Interactions, edited by A. Corso, J. Migliore, and C. Polini. Contemporary Mathematics 448 (2007), 183–205, American Mathematical Society.

[17] D.R. Grayson and M.E. Stillman. Macaulay 2. A software system for research in algebraic geometry. Available at

www.math.uiuc.edu/Macaulay2/.

[18] A.P. Morgan. A transformation to avoid solutions at infinity for polynomial systems. Applied Mathematics and Computation 18 (1986), 77–86.

[19] D. Mumford. Varieties defined by quadratic equations. In Questions on Algebraic Varieties (C.I.M.E., III Ciclo, Varenna, 1969), 29–100. Edizioni Cremonese (1970), Rome.

[20] T. Ojika. Modified deflation algorithm for the solution of singular problems. I. A system of nonlinear algebraic equations. J. Math. Anal. Appl. 123 (1987), 199–221.

[21] T. Ojika, S. Watanabe, and T. Mitsui. Deflation algorithm for the multiple roots of a system of nonlinear equations. J. Math. Anal. Appl. 96 (1983), 463–479.

[22] A.J. Sommese. Holomorphic vector-fields on compact Kaehler manifolds. Mathematische Annalen 210 (1974), 75–82.

[23] A.J. Sommese, J. Verschelde and C.W. Wampler. Numerical decomposition of the solution sets of polynomial systems into irreducible components. SIAM Journal on Numerical Analysis 38 (2001), 2022–2046.

[24] A.J. Sommese, J. Verschelde and C.W. Wampler. Using Monodromy to Decompose Solution Sets of Polynomial Systems into Irreducible Components. Proceedings of the 2001 NATO Advance Research Conference, Eilat, Israel, on Applications of Algebraic Geometry to Coding Theory, Physics, and Computation, edited by C. Ciliberto, F. Hirzebruch, R. Miranda, and M. Teicher, (2001), 297–315.

[25] A.J. Sommese, J. Verschelde and C.W. Wampler, Symmetric functions applied to decomposing solution sets of polynomial systems, SIAM Journal on Numerical Analysis 40 (2002), 2026–2046.

[26] A.J. Sommese, J. Verschelde, and C.W. Wampler, A method for tracking singular paths with application to the numerical irreducible decomposition, in Algebraic Geometry, a Volume in Memory of Paolo Francia, edited by M.C. Beltrametti, F. Catanese, C. Ciliberto, A. Lanteri, C. Pedrini, pages 329–345, W. de Gruyter, 2002.

[27] A.J. Sommese, J. Verschelde, and C.W. Wampler, Numerical irreducible decomposition using PHCpack, in Algebra, Geometry, and Software Systems, edited by M. Joswig and N. Takayama, pages 109–130, Springer-Verlag 2003.

[28] A.J. Sommese, J. Verschelde, and C.W. Wampler, Homotopies for Intersecting Solution Components of Polynomial Systems, SIAM Journal on Numerical Analysis 42 (2004), 1552–1571.

[29] A.J. Sommese, J. Verschelde, and C.W. Wampler II. Solving Polynomial Systems Equation by Equation. In Algorithms in Algebraic Geometry, edited by A. Dickenstein, F.-O. Schreyer, and A.J. Sommese, volume 146 of IMA Volumes in Mathematics and Its Applications, pages 133–152, 2007, Springer Verlag.

[30] A. Sommese and C. Wampler. The Numerical Solution to Systems of Polynomials Arising in Engineering and Science. World Scientific, Singapore, 2005.

[31] A. Sommese and C. Wampler. Exceptional sets and fiber products. Foundations of Computational Mathematics 8 (2008), 171–196.

[32] J. Verschelde. Algorithm 795: PHCpack: a general-purpose solver for polynomial systems by homotopy continuation, ACM Transactions on Mathematical Software 25 (1999), 251–276. Software available at www.math.uic.edu/∼jan.