Homotopies for Intersecting Solution Components of Polynomial Systems.
We show how to use numerical continuation to compute the intersection $C=A\cap B$ of two algebraic sets A and B, where A, B, and C are numerically represented by witness sets. En route to this result, we first show how to find the irreducible decomposition of a system of polynomials restricted to an algebraic set. The intersection of components A and B then follows by considering the decomposition of the diagonal system of equations u restricted to {u,v}$\in$ A $\times$ B. An offshoot of this new approach is that one can solve a large system of equations by finding the solution components of its subsystems and then intersecting these.  It also allows one to find the intersection of two components of the two polynomial systems, which is not possible with any previous numerical continuation approach.
Introduction
. In a series of papers [12, 13, 14, 15, 17], we have proposed
numerical continuation algorithms that use witness sets as the basic construct for
representing solution components of a system of polynomial equations on C N . Witness
sets are the central concept of a young subject that we call numerical algebraic
geometry, which uses numerical continuation [1, 2] and generalizes earlier work in
computing isolated solutions of polynomial systems [8, 9]. The main concern of this
paper is to provide an algorithm for computing the intersection of two solution components
A, B from two possibly identical polynomial systems f, g, whose witness sets
have been given. It is important to realize that naively combining f, g into one system
{f, g} is not su#cient, even if we were willing to put aside the potentially
prohibitive size of the combined system. For example, suppose A is the line x
as a solution component of is the line x 1 - x as a solution
component of which is the isolated point (0, 0),
does not appear as an irreducible component of the system
Questions involving intersection of components arise naturally in applications.
Just as a single polynomial in one variable has multiple roots, a system of polynomial
equations in several variables can have multiple solution components; these components
can even appear at di#erent dimensions (points, curves, surfaces, etc.) from
the same set of equations. We may wish to find the intersection of just one of those
components with another algebraic set. In our new approach, only the degrees of the
components being intersected come into play in the determination of the number of
paths followed by the homotopies that we use. This is important since the degree of
# The authors acknowledge the support of the Volkswagen-Stiftung (RiP-program at Oberwolfach).
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 the Duncan Chair of
the University of Notre Dame.
# Department of Mathematics, Statistics, and Computer Science, University of Illinois at Chicago,
851 South Morgan (M/C 249), Chicago, IL 60607-7045, USA Email: jan@math.uic.edu or
jan.verschelde@na-net.ornl.gov URL: http://www.math.uic.edu/-jan. This material is based upon
work supported by the National Science Foundation under Grant No. 0105739 and Grant No. 0134611.
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.
a component of a given system of polynomials is typically much less than the number
of paths required to find even all isolated solutions of the given system.
Viewed another way, the intersection operation is required for a Boolean algebra
of constructible algebraic sets; a complete Boolean algebra also requires the operations
of union and complement. Suppose W is a witness set for a component X. There
are several probability-one algorithms for deciding if a point x # C N is a member of
X, using numerical continuation and the data in W . (We review witness sets and
membership tests in -2.) The complement operation is just the logical inversion of
a membership test, and the union operation is just a union of witness sets, utilizing
membership tests to eliminate duplications. However, the operation of intersection is
more di#cult.
In our previous work, we have shown how to find the solution set of a system
of polynomial equations as a union of witness sets, and further, we have shown how
to decompose these into witness sets for the irreducible components. Said another
way, this solves the problem of intersecting a collection of hypersurfaces defined by
polynomial equations. But this does not give us an e#ective means of computing the
intersection of two components represented by witness sets.
Our first step in creating an algorithm for the intersection of components is to
generalize an earlier algorithm for generating the witness sets for the solution set of
a system of polynomial equations on C N . The generalization instead considers the
polynomial equations restricted to an algebraic set. The intersection of components
A and B then follows by considering the decomposition of the diagonal system of
equations restricted to {u, v} # A - B. Hence, we call the intersection
algorithm the diagonal homotopy.
This paper is organized as follows. First, in -2, we review the definition of a witness
set and its role in finding the numerical irreducible decomposition of the solution
set of a system of polynomial equations. In -3 we introduce a slight generalization
of the randomization procedure of [17], and in -4 we give a general construction of
homotopies. These sections give the basic definitions and results that will be needed
later in the article.
The original algorithm for constructing witness supersets was given in [17]. A
much more e#cient algorithm for constructing witness supersets was given in [12] by
means of an embedding theorem. In -5, we show how to carry out the generalization
of [12] to the case of a system of polynomials on a pure N-dimensional algebraic
set i.e., an algebraic subset of C m all of whose irreducible components
are N-dimensional. We call this the "abstract embedding theorem" because it does
not rely on any specific numerical description of X. In this generality we lose some
control of multiplicities. However, since our main objective is to find the underlying
reduced algebraic solution components, this loss of multiplicity information is of minor
importance.
In -6 we show how to implement the abstract embedding theorem numerically.
We need only the information about X that would be produced by the algorithm for
the numerical irreducible decomposition of a polynomial system f , for which X is an
irreducible component of the solution set of f .
In -7 we specialize to the situation where we have two polynomial systems f
and g on C N and we wish to describe the irreducible decompositions of A # B where
A is an irreducible component of V (f) and B is an irreducible component of V (g).
Computational experiments are discussed in -8.
In

Appendix

-A, we give some further discussion of the method of constructing
homotopies described in -4.
In

Appendix

-B, we give the proof of Theorem 5.1 from -5.
We would like to thank the referees for their helpful suggestions.
2. Witness Sets. We begin by reviewing the basics of numerical algebraic ge-
ometry, wherein the most fundamental concept is a witness set. We refer the reader to
[13, 15, 17] for more details on irreducible components, the irreducible decomposition,
and reduced algebraic sets.
Given a system of polynomials on C N
we denote the underlying point set # x # C N
set f -1 (0) (with all multiplicity information that comes with f -1 (0) ignored). A pure
i-dimensional algebraic subset X of V (f) is a subset X # V (f) equal to the closure
of a union of i-dimensional connected components of the smooth points of V (f ). We
emphasize that X is reduced, i.e., that we are ignoring the multiplicity of X within
numerically by a witness set, defined as follows.
Definition 2.1. A witness set for a pure i-dimensional algebraic set X # V (f) #
C N consists of:
1. the dimension, i, of X;
2. the polynomial system f(x);
3. a general (N - i)-dimensional a#ne linear subspace LN-i # C N ; and
4. the set of deg X distinct points
In other words, a witness set W for X is the ordered set
use the notation V (W ) to denote the component represented by W ; in the current
This definition is useful because it allows us to numerically represent and manipulate
the irreducible decomposition of the solution set of a polynomial system. Let
us quickly review that concept before describing our new results. Everything we say
is over the complex numbers, e.g., even if the polynomials have real coe#cients, we
always deal with the sets of solutions on complex Euclidean space.
We start with a system of polynomials f on C N as in (2.1) above. Let V (f) denote
the set of solutions of f on C N , i.e., the set of points x # C N such that
The set Z := V (f) is an a#ne algebraic set and decomposes into a union of distinct
irreducible components. Recall that an algebraic set X is irreducible if and only if
the Zariski open dense subset of manifold points on X is connected. We have the
decomposition
dim Z
dim Z
where
1. For each i, Z i := (# j#I i
2. the sets I i are finite and each Z i,j is irreducible of dimension
3. Z i,j is not contained in a union of a collection of the Z a,b unless Z i,j occurs
in the collection.
Any collection of irreducible components Z i,j having the same dimension, i, can
be numerically represented by a witness set. A "numerical irreducible decomposition"
is a list having one witness set W i,j for the reduction of each irreducible component
Z i,j .
In a series of papers [12, 13, 14, 15, 17], we showed how to compute a numerical
irreducible decomposition of Z := V (f ). The approach is to intertwine two numerical
algorithms: a witness generating algorithm, which finds a superset of witness points
for each pure-dimensional algebraic set Z i , and a decomposition algorithm, which
eliminates spurious points from the superset and breaks it into irreducible compo-
nents. To be more precise, at each dimension the witness generating
algorithm gives a finite set of points
where LN-i # C N is a general (N - i)-dimensional a#ne linear subspace. The second
algorithm decomposes the
1.
into the disjoint union
consists of the deg Z i,j points of LN-i # Z
and
2. J dim
The points Z i,j along with the dimension i, the system of equations f , and the linear
subspace LN-i , form a witness set for the irreducible component Z i,j .
The key theoretical advance of this paper is to observe that the previous algorithms
for numerical irreducible decomposition still work with restrictions of a polynomial
system to a pure-dimensional algebraic set. Only the first algorithm constructing
the witness point supersets
needs to be generalized. The decomposition algorithms
starting with the witness point supersets
are proved in the papers [13, 14, 15] in
su#cient generality to cover the present situation.
The above implicitly assumed that the components Z i,j are reduced, i.e., of multiplicity
one in f -1 (0). The algorithms in [12, 17] in fact produce sets Z i,j consisting
of deg Z i,j distinct points each repeated - i,j times, where - i,j is greater than or equal
to the multiplicity of Z i,j in f -1 (0). Moreover the multiplicity of Z i,j is one if and
only if - Unfortunately, in the algorithm in this article we can only assert that
irreducible component Z i,j .
As we mentioned in the introduction, an important aspect of a witness set X is
that we can use it to test a point for membership in the algebraic set
represents. This stems from the fact that we can sample X by continuously perturbing
the linear slice and numerically tracking its intersection with X, starting from the
witness points in X . Several di#erent membership tests can be employed. At one
expensive extreme, by sampling and fitting, we might compute a set of polynomials,
whose set of common zeroes is exactly X. A much more e#cient "probability-one"
test for a point x # C N to be in X is whether the pullback from C dim X+1 of a deg X
defining polynomial for #(X) # C dim X+1 is zero on x, where # is a general linear
projection from C N to C dim X+1 . Finally, a very di#erent sort, and quite e#cient
test, for x # C N to be in X is to see whether x is one of the images of the set X
under the homotopy taking LN-i to a general (N - i)-dimensional linear subspace of
C N that contains x. This test depends on the real-one-dimensional path between the
general linear subspaces to remain general, which occurs with probability one.
3. Randomizing Systems. Randomization is a key element of our approach.
This section introduces some notation for randomized systems and gives a lemma
describing their most important properties. Given a system of n equations defined on
C N , as in Eq.(2.1), and a positive integer k, we define a randomization operation
where # is chosen generically from C k-n . Note that k does not have to equal n.
Gaussian elimination does not change the ideal generated by #f(x). Therefore, when
equivalent to the system consisting of f(x) plus k -n identically zero
equations. For the same reason, when k # n, #f(x) is equivalent to the system
I
where I k is the k - k identity matrix. Consequently, we may without loss of generality
assume that R(f(x); k) is of the form of Eq.(3.2) with a generic choice of
This form allows us to take some advantage of the original equations.
For example, if and the original equations had total degrees d 1 # d 2 # d n ,
then the total degree of the original form of R(f(x); N) is d N
1 , but the total degree of
the modified form is d 1 d 2 - dN .
The following lemma gives the main properties of randomization.
Lemma 3.1. Let
be a system of restrictions of n polynomials on C m to a pure N-dimensional a#ne
algebraic set X # C m . Assume that k # min{n, N}. Assume that f does not vanish
on any component of X. The following conclusions follow.
1. The dimension of any component of V (R(f(x); k)) is # N - k.
2. The irreducible components of V (R(f(x); k)) and V (f) of dimension greater
than N-k are the same, and the irreducible (N -k)-dimensional components
of V (f) are components of V (R(f(x); k)).
Proof. This variant of Bertini's Theorem follows by the same type of reasoning
as the analogous result in [12, 17] for systems of N polynomials on C N . For the
convenience of the reader, we give a proof.
The first conclusion is simply [11, Corollary 3.14].
the second conclusion will follow if we show that all
irreducible components V (R(f(x); k)) # (X \ V (f)) have dimension N - k. Thus it
su#ces to show that if V (f) is empty, then it follows that all irreducible components
have dimension N - k. This is immediate from Theorem B.1.
4. Construction of Homotopies. Our algorithm for intersecting algebraic varieties
is based on constructing homotopies to solve a system of polynomial equations
restricted to an algebraic set. This is a generalization of existing homotopies, which
have until now always worked on complex Euclidean space, C m . Accordingly, in this
section we give a very general construction for homotopies on varieties.
be an irreducible N-dimensional a#ne algebraic set and let Y be an
irreducible r-dimensional smooth algebraic set with r # 1. Let
be a system of N algebraic functions on In practice, Y is a parameter space
defining a family of systems of interest, and for any one member of the family, we
wish to find its solution points in X.
More precisely, suppose we have some parameter value y # Y for which we want
to find a finite set F # of solutions of the system f(x, y # such that all the isolated
solutions of f(x, y # are contained in F # . A procedure to do this proceeds in a
number of steps in the same manner as if Y is C N .
1. Choose a point y # Y for which we can find the isolated solutions F # of
and the number of isolated solutions is the maximum number
D for any system f(x, as a system in the x variables. We assume here
that y #= y # , since otherwise we are done.
2. Construct a smooth connected algebraic curve B # Y which contains y # and
y # . (Typically Y is a Euclidean space and we choose B equal to the complex
line joining the points y # and y # .)
3. Construct a di#erentiable mapping c : [0, is an interval
or the unit circle, c(0, and where there is a positive
integer K such that given any point y # c([0, 1] - #) not equal to y # or y # ,
it follows that c -1 (y # ) has at most K inverse images.
4. Choose a random # and starting with the isolated solutions F # of
use "homotopy continuation" of the system f(x, c(t,
to continue from the solutions F # at solutions F # at
Let us show that if we can make the choices specified by this procedure, we will find a
finite set F # of solutions of the system f(x, y # such that all the isolated solutions
of f(x, y # are contained in F # . In Appendix A we show how to relax item (2)
so that the procedure can be carried in all situations where Y is irreducible.
It may well happen that the solution sets of f(x, some or all the y # Y
also contain positive dimensional solution components. Nevertheless, the number D
in item (1) exists and is finite by general results, e.g., [10]. Now choose B as in
item (2) above. Lemma A.1 guarantees that for all but a finite number of points
isolated solutions, and that the closure of the union of the
isolated solutions of f(x, -
y runs over B is an algebraic curve B which surjects
generically D-to-one onto B. Since the set of points in B over which this mapping is
not a covering is an algebraic set and hence finite, the procedure is seen to work.
Remark 4.1. Algebraic functions on an a#ne algebraic set X # C m are the
restrictions of polynomials from C m . If by deg f i we denote a degree of a polynomial
on C m restricting to f i , it follows that the number D above is at most deg X -
. From this it further follows that if we can find a y # such that f(x, y #
has deg X -# N
isolated solutions, we can use y # .
Remark 4.2. Lemma A.1, which justifies the above procedure, is strong enough
to yield the algorithms we need to construct witness points. However, the lemma is
too weak to relate the multiplicity of the points as they appear in these algorithms to
the multiplicity of the components that they represent. See App. A for more details.
5. An

Abstract

Embedding Theorem. The object of this section is to present
Theorem 5.1, a generalization of the main theorem of [12]. We are aiming for the
same results as in that article except that C N is replaced by a pure N-dimensional
a#ne algebraic set X. We call the generalization in this section "abstract," because
we do not specify an explicit description of X; a numerical version is the topic of the
next section. Since the proof of Theorem 5.1 follows the same line of reasoning of
[12], we only state and discuss the parts of that article that need changes. Before we
can state the theorem, we need some notation.
5.1. Definitions. Let X # C m be a reduced pure N-dimensional a#ne algebraic
set, i.e., an a#ne algebraic subset of C m , all of whose irreducible components are of
multiplicity one and dimension N . We assume that we have a system of restrictions
of polynomials on C m to X
We assume that f does not vanish identically on any irreducible component of X. We
will occasionally abuse notation and use the same notation f i to denote the polynomial
on C m and its restriction to X. In line with this abuse, we let
xm
denote both the coordinates on C m and the restrictions of the coordinates to X.
Let Y denote the matrix space C N-(1+m+N) , with submatrices denoted as
We have the stratification of Y
is the subspace of Y obtained by setting the last N - i rows of Y equal to
0, and we define # as the corresponding projection. Note in particular that
YN is Y, whereas Y 0 is a N - (1 +m+N) matrix of zeroes. Defining e i as the N -N
matrix of all zeros except a 1 in the i-th diagonal element and letting P
we can explicitly write # i (Y to be the N -N matrix with all
entries zero. This notation will be useful in defining a homotopy below.
We let
z :=
z N
denote coordinates on C N .
5.2. Embedding and Cascade. For we define the
system
z -A 0 -A 1 x
which admits the embeddings
We often refer to E i (f)(x, z, Y ) by E i or E i (f ). We regard E i as a family of systems of
equations on X - C N parameterized by Y i . Note that
1. the E i are the restrictions of systems EN to Y i ; and
2. the E i can be identified with systems on X - C i with coordinates z 1 , . , z i
on C i . (This is because z naturally identified
with the system f .
For i from 1 to N and # i # C | we define a cascade of homotopies
that connect the embedded systems:
# .
The nonzero parts of the three terms in the lower block of this expression occupy
separate rows, with only the i-th row depending on t. At
is equivalent to E i (x, z, Y ) (they di#er only in that the i-th row of the lower block
has been scaled by # i ), and at
allows us to compute solutions to the embedded systems by continuation, as described
in the next paragraph.
For i from 1 to N , F i denotes the solutions to In the case of
we make the convention that F 0 is the empty set. Of course, like E i , F i depends
on Y # Y. We do not emphasize the dependence since the thrust of the main result
is that a generic choice of Y , which is done once and for all using a random number
generator in implementations, has a number of nice properties:
1. the solutions F i of are nonsingular and isolated and equal to the set
of solutions of
2. the solutions of
3. for all u # F i and but a finite number of # i , there is a unique continuous map
s
(a) s u
(c) the Jacobian of H i (x, z, t, Y, # i ) with respect to (x, z) is invertible at
4. The limits of the functions s u (t) as t # 0, which exist by the last properties,
consists of the set F i-1 plus a finite set
The collection of sets
contains the witness points for the
irreducible decomposition of f -1 (0). This is stated formally in the following theorem,
a generalization of the main theorem of [12].
Theorem 5.1. Let f be the restriction of a system of N polynomials on C m to
a pure N-dimensional a#ne algebraic set X # C m . Assume that f is not identically
zero on any irreducible component of X and that
If j is the largest integer with
nonempty, then the dimension of f -1 (0) is j.
Moreover given any irreducible component W of f -1 (0) of dimension i # j, then,
the finite set,
contains deg(W red ) generic points of W red , each counted # W times,
where # W is a positive integer, and W red is the reduction of W . The remaining points
on components of f -1 (0) of dimension > i.
Theorem 5.1 is a consequence of Lemma A.1 and Lemmas B.2 and B.4 in the
appendices.
6. Numerical Embedding. In this section we show how to numerically implement
the algorithm of -5. We assume that we have f and X # C m as in Theorem 5.
We assume that we have a system of polynomials on C m
such that X is a union of dimension N irreducible components of V (g). Once and
for all choose a randomized system of m - N polynomials G(x) := R(g(x); m-N ).
By Lemma 3.1 we know that X is a union of dimension N irreducible components of
(G).
We further assume that we begin with a witness set for X; that is, we know
its dimension N , and have found the deg X smooth isolated witness points
Lm-N #X for a general linear subspace Lm-N of dimension m-N . (This will be on
hand after computing the numerical irreducible decomposition of
To convert the "abstract" systems of the previous section to systems we can
compute with, we append G. Thus regarding the f i as polynomials on C m , we replace
which by abuse we still call E i (f ). We let
denote the original E i (f) without the
G(x): we only use this in Equations 6.6 and 6.7.
To start the algorithm we need to solve EN Assume the total degree of
f i as a polynomial on C m is d i for each i.
Choosing linear forms
on C m , we want them to have the good property that for any choice of integers i j in
1, . , d j for each j in 1, . , N , the solution set
of the system of restrictions
to X of the linear equations
consists of deg X nonsingular isolated solutions, and moreover S i 1 ,.,i N # S k1 ,.,k N
# C N denote a general linear
projection. As discussed in [14], #X is proper and (deg X)-to-one. Let B be the proper
algebraic subset such that #X is an unramified cover when restricted to X\# -1 (B). By
composing with # we have reduced to the straightforward observation that choosing
linear functions L i on C N for i from 1 to d 1
that
1. the unique zero of the linear functions L
for distinct
between 1 and d 1 dN vanishes at a general point of C N
\ B; and
2. given any N + 1 of the d 1 linear functions, there are no solutions
on C N .
The system
has d 1 - dN - deg X nonsingular isolated solutions w# contained in X reg , the Zariski
open set of smooth points of X. By homotopy continuation tracking from Lm-N to
each of the d 1 - dN linear systems that occur in the system
L(x), we can compute
all the solutions w# of
Fix the homotopy
z
where # is any of all but a finite number of norm one complex numbers. The solutions
of EN are the nonsingular limits as t # 0 on X of paths starting at
the w# and z
Remark 6.1. In actual practice we often have some estimate, say N - 1 of the
largest dimension of any component of the solution set of f on X. This will happen,
for example, in -7. In such a situation we need only start with EN . In this case we
can replace the homotopy 6.6 with
z
Note that the smooth nonsingular solutions of E i (f) on X are generic. Thus they
miss proper algebraic set of parameter values.
Thus for a Zariski open dense set of the homotopy parameters the homotopies with
G compute the abstract homotopies. Though E might well contain the limits of a
homotopy, the value of the limit is not influenced by G.
It is important to realize that serious numerical di#culties can arise, even when
we are dealing with a nice smooth reduced component C of the system f on X. These
occur if C is contained in a component of V (g) other than those in X. If this happens
path tracking to decompose the witness point superset containing generic points of C
will be 'singular,' and require the path tracker used in [15].
7. Diagonal Homotopies. Assume that A is an irreducible component of the
solution set of polynomial system f A of dimension a > 0, and that B
is an irreducible component of the solution set of polynomial system of a polynomial
system f B important special case of
this is when f A and f B are the same system, and A and B are distinct irreducible
components. After renaming if necessary, we assume a # b. Moreover we assume
that B is not contained in A, since we would check this at the start of the algorithm
and terminate if B was contained in A. Thus all components of A#B are of dimension
at most b - 1.
We wish to compute the irreducible decomposition of A#B. Note that the product
is irreducible of dimension a b. The theory of the preceding
sections applies with b. The intersection of A and B can be
identified, e.g., [4, Ex. 13.15], with X # where # is the diagonal of C 2k defined by
the system on X
Remark 7.1. Notice that #(u, v) plays the role of f in (5.1) in -5.
If a set D(u, v) equal to #(u, v) with a identically zero equations
adjoined. If k < a randomization D(u, v) := R(#(u, v); a once and
for all. Note that the smallest dimensional nonempty component of A # B is of
dimension at least max{0, a+b-k}. Thus by Lemma (3.1), we can find the irreducible
decomposition of A # B by finding the irreducible decomposition of D(u,
X.
Fix randomizations FA (u) := R(fA (u); k - a) and FB (v) := R(fB (v); k - b) once
and for all. We assume that we have already processed f A and f B through our
numerical irreducible decomposition. So our data for A consists of a generic system
linear equations and the deg A solutions {# 1 , . , # deg A } # C k
of the system
and the data for B consists of a generic system LB
equations and the deg B solutions {# 1 , . , # deg B } # C m of the system
Remark 7.2. We are not assuming that A and B occur with multiplicity one.
If the multiplicity is greater than one, we must use a singular path tracker [15].
Note that A-B is an irreducible component of the solution set of the system
In the following paragraphs, we write z h:k to mean the column vector of variables
z h , . , z k .
Since we know that all components of A # B are of dimension at most b - 1, the
first system of the cascade of homotopies is
z 1:b -R(1, u, v; b)
This system consists of k -a+ k - b +a+ b equations in 2k
To start the cascade, we must find the solutions of Eq. (7.5). Recall a # b.
Specializing the system from the end of -6, we have the homotopy
z 1:b -R(1, u, v; b)
z 1:b
solution paths start at the deg A- deg B nonsingular solutions
obtained by combining the witness points for A and B. At the solution paths
terminate at the desired start solutions for Eq. (7.5).
implies that
we see that when a we do not have to continue the cascade beyond level
k. We can codify this into the numerics by noting that the system E b is, with
probability one, the same as the system
R(1, u, v; b - a)
z (b-a+1):b -R(1, u, v; - a)
This system has
equations in 3k - a variables. Notice that a b. To
appreciate this, consider the case when a and b are both k - 1 and f A and f B are
each a single equation. In this case the first system of the cascade is
f A (u)
where R k-1 is a generic complex k-vector.
In the important case when a+ b # k, we want to compute the start solutions for
Eq. (7.9). Then, letting - a, the homotopy (7.6) reduces with probability one
to
R(1, u, v; b - a)
z (b-a+1):b -R(1, u, v; - a)
z (b-a+1):b
8. Computational Experiments. The diagonal homotopies are implemented
in the software package PHCpack [18], recently upgraded to deal with positive dimensional
solution components.
To compute witness points on all positive dimensional components of the inter-
section, we distinguish three stages:
1. given witness points on the two components, construct the top dimensional
system in the cascade and the start system to start the cascade;
2. use polynomial continuation to compute the solutions at the start of the
cascade; and
3. follow all paths defined by the cascade, in b stages, until all slack variables in
z 1:b are eliminated or until no more paths are left to trace. When a
we need work only with z (b-a+1):b
The complexity of this procedure thus depends on
1. the number of variables (and equations) in the top dimensional system in the
2. the number of paths it takes to compute the solutions at the start of the
cascade; and
3. the number of paths defined by the cascade.
Although we will mention timings of runs done on a 2.4 Ghz Linux machine, the
numbers describing the complexity are less transient.
8.1. An illustrative example. Consider the following example:
y, z,
xz
xw
There are two solution components of dimension two, characterized by the equations
Pretending we do not know the two components
intersect in the origin, we will set up a cascade of homotopies to compute the
intersection of the two components.
Since we start out with four variables work with two dimensional
components 2), the total number of variables at the start of the cascade
is 10. The components are characterized by one witness point each, so
there is only one path to trace. Tracing one path to start the cascade only takes 80
milliseconds CPU time, and gives a point with z 2 #= 0, z 1 #= 0. In the first stage of
the cascade, we take z 2 to zero, but z 1 remains nonzero, showing that there is not a
1-dimensional component. The second stage of the cascade takes z 1 to zero and yields
the origin as the point of intersection of the two components, as expected. The two
stages of the cascade together take just
8.2. Intersection of a cylinder with a sphere. In Figure 8.1 we see a sphere
intersected by a cylinder. The curve C defined by this intersection is
{ (x, y, z) | x
The total user CPU time of all path tracking is about a tenth of a second. First
we track two paths to find a witness set for the cylinder, which takes 20 milliseconds.
Fig. 8.1. Intersection of a sphere with a cylinder. At the right we see the curve of degree four
defined by the intersection.
Then it takes also 20 milliseconds to compute a witness set for the sphere. We have
and the diagonal homotopy requires 7 variables,
as a. Tracking the 2 - 2 paths defined by the diagonal homotopy takes
milliseconds CPU user time. At the end of the paths we find four points in the
witness set for the curve C.
We may now move the slicing plane of the witness set to find the intersection of
C with any desired plane. For example, to find the points on C of the form (x, x, z),
we move the slice in a continuous fashion to x - Tracking the four solutions in
the witness set to this special plane takes only 10 milliseconds CPU time and gives
two real and two complex-conjugate solutions.
8.3. Adding an extra leg to a moving platform. In this section we give an
application of the important case where one of the components is a hypersurface. We
consider a special case of a Stewart-Gough platform proposed by Gri#s and Du#y [6].
When further specialized to have equilateral upper and lower triangles connected by
six legs in cyclic fashion from a vertex of one triangle to a midpoint of an edge of the
other triangle, and vice versa, the platform permits motion. This property was first
identified and analyzed by Husty and Karger [7] and subsequently re-examined by the
authors of this paper in [15].
When the legs of the mechanism described above have general lengths, a formulation
of the kinematic equations using Study coordinates has one curve of degree 28
and 12 lines [15]. The lines are mechanically irrelevant, so we ignore them. Suppose
we form a tetrahedron by adding a fourth point in general position to the base triangle
and similarly for the upper triangle and then add a seventh leg of known length connecting
these two points. The condition for assembling the mechanism is equivalent
to intersecting the motion curve of degree 28 for the first six legs with a quadratic
hypersurface that equates the length of the seventh leg to the distance between its
points of connection. This hypersurface is of the same form as the main equations in
the system defining the curve. With the addition of the seventh leg, the platform will
no longer move, but will have instead a finite number of fixed postures.
The number of variables and equations in the original system is eight
We intersect a one dimensional component with a hypersurface, for hypersurface
is of dimension seven. Since a # b, we have 1. So the
cascade starts with 17 variables, as 2k 17. The hypersurface is
represented by 2 witness points and the curve we intersect has 28 witness points. To
start the cascade, we trace 2 - 28 = 56 paths in dimension 17, using 20.3 seconds
user CPU time. The cascade just has to remove one hyperplane to arrive at the 40
intersection points (16 of the 56 paths diverge), which requires 14.4 seconds user CPU
time. Interestingly, a general Stewart-Gough platform also has 40 solution points.
Finally, we point out that the CPU time spent on the diagonal homotopy is considerably
less than solving the system directly. For the direct approach the input is
a system in 9 equations and 8 variables. Before giving it to the blackbox solver of
PHCpack, we add to every equation one monomial, which is a new slack variable multiplied
with a random constant. The mixed volume of this new 9-dimensional system
is 164. The computation of the mixed volume and tracking of all 164 paths takes
seconds (1.8 minutes) CPU time. At the end we find the same 40 intersection
points, the other 124 paths diverged to infinity. Notice that in the diagonal homotopy,
only
9. Conclusions. In this paper, we extend the cascade of [12] to compute witness
points on all components of the intersection of two irreducible varieties. This is done
by computing the irreducible decomposition of the diagonal of the product of the two
irreducible varieties, and so we call the new procedure a "diagonal homotopy." The
procedure is justified as a special case of a method, also described herein, for the
irreducible decomposition of the solution set of any polynomial system restricted to
an irreducible algebraic set.
The diagonal homotopy given here always has at least twice the number of variables
as the ambient space of the varieties being intersected. In a sequel to this paper,
we will describe a modification to the diagonal homotopy that avoids the explicit doubling
of the system, which leads to more e#cient computation.



--R

Numerical Continuation Methods
Numerical Path Following.
The adjunction theory of complex projective varieties
Commutative Algebra with a View Toward Algebraic Geometry
Intersection theory


Numerical solution of multivariate polynomial systems by homotopy continuation methods.
Solving polynomial systems using continuation for engineering and scientific problems.

Algebraic Geometry I: Complex Projective Varieties
Numerical homotopies to compute generic points on positive
Numerical decomposition of the solution sets of polynomial systems into irreducible components.
Using monodromy to decompose solution sets of polynomial systems into irreducible components.
Symmetric functions applied to decomposing solution sets of polynomial systems.
A method for tracking singular paths with application to the numerical irreducible decomposition.
Numerical algebraic geometry.
Algorithm 795: PHCpack: A general-purpose solver for polynomial systems by homotopy continuation
--TR

--CTR
Andrew J. Sommese , Jan Verschelde , Charles W. Wampler, An intrinsic homotopy for intersecting algebraic varieties, Journal of Complexity, v.21 n.4, p.593-608, August 2005
Wenyuan Wu , Greg Reid, Application of numerical algebraic geometry and numerical linear algebra to PDE, Proceedings of the 2006 international symposium on Symbolic and algebraic computation, July 09-12, 2006, Genoa, Italy
Greg Reid , Jan Verschelde , Allan Wittkopf , Wenyuan Wu, Symbolic-numeric completion of differential systems by homotopy continuation, Proceedings of the 2005 international symposium on Symbolic and algebraic computation, p.269-276, July 24-27, 2005, Beijing, China
generic points;homotopy continuation;numerical algebraic geometry;irreducible components;polynomial system;components of solutions;embedding