Numerical Solution of Systems of Polynomials Arising in Engineering and Science

(Ai(0)) \ x. Proof. This is sometimes referred to as the local uniformization theorem for onedimensional analytic sets. It is the one-dimensional complex analytic version of Theorem A.4.1. A proof for it can be based on the local parameterization theorem (Gunning, 1970), which, in its simplest form for a pure one-dimensional complex analytic set X, says that given a point x C X, there exists a finite proper surjection n : U —> Ai(0) where U is an open neighborhood of x and where 0 = n(x). Since X is one-

310

Numerical Solution of Systems of Polynomials Arising in Engineering and Science

dimensional, the set of singular points of X is O-dimensional and therefore meets a neighborhood of x with compact closure in a finite set. We can therefore (by taking a smaller U if needed) assume that the only possible singular point in U is x. If a; is a smooth point there is nothing to prove. Similarly IT : U \ {x} —> Ai (0) \ 0 is an unramified covering with a well-defined sheet number d. Basic topology tells us that the restriction / : Ai(0) \ 0 —> Ai(0) \ 0 of the mapping z —• zd, factors through n : U \ {x} -> Ai(0) \ 0 as f(z) = n(g(z)) with g : Ai(0) \ 0 -> U \ {x}. Using the Riemann Extension Theorem A.2.5, we conclude we have an extension <> / of g satisfying the conclusions we are trying to show. • From Theorem A.3.2 follow results classically referred to as Puiseux's theorem, e.g., (Chapter 7 Fischer, 2001). The following corollary is a version of this result. Corollary A.3.3 Let X be a one-dimensional complex analytic subset of an open set U C C ^ . Assume that X is irreducible at a point x e X. Let V, for some open neighborhood V c X of x, be the local uniformization map of Theorem A.3.2. Given any holomorphic function g{z\,... ,zN) on U which is not constant on X, e.g., a coordinate function Zj, it follows that there exists a positive r < 1 such that a coordinate function s on A r (0) may be chosen with the property that the composition g((p(s)) equals g(x) + sc. Proof. Let w denote any coordinate on Ai(0), which is 0 at 0. The power series expansion of g((f>(w)) is given by oo

g(x)+Y^aiw\ k=c

where ac ^ 0. Since Y^k=oai+cwl 1S nonzero at 0 we may express it on A r (0) for some positive r < 1 as h(w)c, with h(w) holomorphic on A r (0). Choosing r positive, but possibly smaller, s = h(w) is the desired coordinate. •

A.4

Useful Results About Algebraic and Complex Analytic Sets

The Hironaka Desingularization Theorem, which holds for both complex algebraic sets and complex analytic spaces, is highly nontrivial, but extremely useful. Given a quasiprojective algebraic set X (respectively, a complex analytic space X), a desingularization f : X —> X of X is a quasiprojective manifold X (respectively, a complex manifold X) and a proper surjective algebraic (respectively, holomorphic) map / : X —> X such that //-i(x r e g ) : / -1 (-Xreg) —> XTeg is an isomorphism Zariski open and dense in X. Xreg (respectively, a biholomorphism) with f~l(Xreg) is always Zariski open and dense in X.

Algebraic Geometry

311

Theorem A.4.1 (Hironaka Desingularization Theorem) Let X be a quasiprojective algebraic set or a complex analytic space. Then there is a desingularization f :X -> X ofX, More refined versions of the result tell us that we may choose the desingularization map so that the inverse image of the singular set under the desingularization map is a union of smooth codimension one algebraic sets which meet transversely. See (Lipman, 1975) for a nice exposition of this result. In the case when all components of X are of dimension one, Theorem A.4.1 is simply the normalization of X, e.g., see (Fischer, 1976). The Hironaka Desingularization Theorem makes many facts that are easy for manifolds carry over immediately to general algebraic sets. Here is one simple example often referred to as the maximum principle, e.g., (Theorem III.B.16 Gunning & Rossi, 1965). Theorem A.4.2 Let X be an irreducible complex analytic space with infinitely many points. Let f be a holomorphic function of X. If \f\ has a maximum on X, then f is a constant function. Proof. Let n : X —> X be a desingularization. Let / denote the composition of / with 7T. If |/| has a maximum, then so does |/|. By Lemma A.2.7, it follows that / is constant, and hence / is constant. • Theorem A.4.20 will give another illustration of the clarity brought by using Hironaka's theorem. The proper mapping theorem of Grauert assures us that many operations with algebraic sets yield algebraic sets. Theorem A.4.3 Let f : X —> Y be a proper holomorphic mapping (respectively proper algebraic mapping) of complex analytic spaces (respectively protective, respectively affine, respectively quasiprojective algebraic) sets. Then f(X) is a closed complex analytic (respectively protective, respectively affine, respectively quasiprojective algebraic) subset ofY. Proof. The analytic statement may be found in (Fischer, 1976). This, or the simple fact that in the complex topology proper maps take closed sets to closed sets, automatically implies the algebraic statements. To see this note that if X is projective, affine, or quasiprojective algebraic, we know that ir(X) is constructible by Theorem 12.5.6. Since n(X) is closed, we have the conclusion from Lemma 12.5.4.

•

Recall that an algebraic map from a quasiprojective set to an irreducible quasiprojective set Y is dominant if the image of the map is dense in Y.

312

Numerical Solution of Systems of Polynomials Arising in Engineering and Science

Lemma A.4.4 Let f : X —•> Y be a dominant proper algebraic map from a quasiprojective algebraic set to a quasiprojective algebraic set. Then f(X) — Y. Proof. Let y be a point not in the image of X. By dominance we can find a sequence of points yj G f(X) with yj converging to y. Choose Xj G X with f(xj) = yj. By the definition of properness, there is a neighborhood U that contains y such that f~l(U) is compact. Thus there is a subsequence of the Xj that converges to a point • x G X. By continuity of / , we have the contradiction that f(x) = y. For algebraic sets there is a strong result on upper semicontinuity of dimension (Corollary 3.16 Mumford, 1995) for the algebraic case or (Theorem, page 137 Fischer, 1976) for the more difficult complex analytic version. Theorem A.4.5 Let f : X —> Y be an algebraic map (respectively a holomorphic map) between quasiprojective algebraic sets (respectively complex analytic spaces). Then for each positive integer k,

{xex\ dimxr'ifix^yk} is a quasiprojective algebraic set (respectively a complex analytic space). Remark A.4.6 Let / : X —> Y be an algebraic map between algebraic sets. As we see from Example 12.5.5, the sets

{yGY

| dim f-\y)>

k)

do not have to be algebraic sets, though by Theorem A.4.5 and by Theorem 12.5.6, they are constructible. Using Theorem A.4.5 and Theorem A.4.3 we have the following result. Corollary A.4.7 Let f : X —> Y be a proper algebraic mapping of quasiprojective algebraic sets. For each integerfc> 0, the set {y G Y\ d i m / ^ 1 ( y ) > k} is a closed quasiprojective subset ofY. Finally we have the very useful Factorization Theorem of Remmert and Stein (III Corollary 11.5 Hartshorne, 1977). Note that finite-to-one proper maps are called finite maps by algebraic geometers, e.g., (Hartshorne, 1977). Theorem A.4.8 (Stein Factorization Theorem) Let f : X —> Y be a proper algebraic mapping of quasiprojective algebraic sets. Then f factors as s or, where r : X —> Z is a proper algebraic map from X onto a quasiprojective algebraic set Z with all fibers connected, and s : Z —>Y is a finite-to-one proper map. The following general lemma, which is a special case of (III Proposition 10.6 Hartshorne, 1977), is often useful. Lemma A.4.9 Let f : X —* Y be an algebraic map from a quasiprojective algebraic set X to a quasiprojective algebraic set Y. Let Xr denote the closure of

313

Algebraic Geometry

those points from x e Xreg such that f(x) 6 f(X) dimf{Xr) < r.

and rank dfx < r. Then

The algebraic analogue of Sard's Theorem, e.g., ((3.7) Mumford, 1995), is much crisper than the usual Sard's theorem for differentiable maps. It is responsible, through the Bertini theorems of § A.9 for many of the strong probability-one statements in this book. Theorem A.4.10 (Sard's Theorem) Let n : X —> Y be a dominant algebraic map between irreducible quasiprojective algebraic sets X and Y. Then there exists a Zariski open dense subset V cY such that letting U denote the Zariski open dense set A^reg (~l TT~1(V), TTu : U —> V is surjective and of maximal rank, i.e., dnx has rank dimY at all points of x e U. In particular, for all v e V, T T " 1 ^ ) fl XTeg is smooth of dimension dim X — dim Y.

Proof. In a nutshell the proof goes as follows. By replacing Y by a Zariski open dense set Y' of Y with Y' C n(X) \ Sing(Y), and X by Xreg n TT~1(Y'), we can assume without loss of generality that X and Y are smooth and n is surjective. Let X' denote the closed algebraic subset of X consisting of points for which dirx has rank < dimY. By Lemma A.4.9, n(X') is a proper algebraic subset of Y. • Remark A.4.11 The differentiable form of Theorem A.4.10 is quite weak. For example, consider the infinitely differentiable map / : E 2 —• R defined by

/(*,„) : = f e x p ( ^ i f ^ < l . [

0

if x2 + y2 > 1

The image of this map is [0,e -1 ]. Over the dense set (Oje"1) of the image [0, e" 1 ], / is of maximal rank, but f~1(U) is far from dense in IR2. Another useful fact is that generically dimensions add. Corollary A.4.12 (Additivity of Dimensions) Let f : X -^ Y be a dominant map between irreducible quasiprojective algebraic sets. There is a dense Zariski open setUcY such that for all y GU, f"1(y) is pure dimension dimX - dimY. Proof. By Theorem A.4.5, there is a dense Zariski open set V C X such that dimx f~1(f(x)) is a constant k for all x G V, and for all x G Z := X \ V, dimx f~1(f(x)) > k. Using Theorem A.4.10, we see that k = dimX — dimY. We will be done if we show that f(Z) is not Zariski dense. Assume it was. Then we would have an irreducible component Z' of Z mapped dominantly to Y. Using Theorem A.4.10 we conclude that a dense set of points x £ Z' satisfy dimx fz^{fz'{x)) — dimZ' — dimY. But this gives the contradiction that dimX - dimY = k < dim^ f^ifz'ix))

= dimZ' - dimY < dimX - dimY. a

314

Numerical Solution of Systems of Polynomials Arising in Engineering and Science

The following result (Corollary, page 138 Fischer, 1976) is useful for analyzing not necessarily proper maps. The algebraic case with the Zariski topology follows from it by using Theorem 12.5.6. Theorem A.4.13 Let f : X —> Y be a holomorphic spaces. Assume for a point x € X that there is an O C X of x, such that for all x' € O, dinx^ f~1(f(x')) are arbitrarily small open complex neighborhoods U C such that

mapping of complex analytic open complex neighborhood is a constant k. Then there O of x and V C Y of f(x)

(1) f(U) is a complex analytic subset ofV; (2) fu'.U—t /(J7) is an open map, i.e., all open subsets of U in the complex topology are mapped to open subsets; and (3) d\mx U = k + dim /(a; ) f(U). By a covering map g : A —> B between differentiable manifolds of the same dimension is meant a differentiable map such that each point y GY has a neighborhood U such that g~1 (U) is a union of disjoint open sets each mapped isomorphically onto U by / . We have the important consequence of Theorem A.4.3 and Theorem A.4.10. Corollary A.4.14 Let f : X —> Y be a surjective proper algebraic map between quasiprojective algebraic sets. Assume that X and Y are pure dimensional with dimX = dimY. Then there is a Zariski dense open set U C Y which is smooth and such that f : f~l(U) —> U is a covering map. If Y is irreducible, the map / in Corollary A.4.14 has a well-defined degree. Corollary A.4.15 Let f : X —> Y be a proper map from a pure-dimensional quasiprojective algebraic set X to an irreducible quasiprojective algebraic set of the same dimension. Assume that f is surjective on every component of X, e.g., assume that f is finite-to-one. Then there is a Zariski dense open set U C Y such that f : f~1(U) —> U is a covering map of degree degf, which is equal to the number of points in any fiber of fj-i^uy The most important case of Corollary A.4.15 is when -K : X —» Y is finite-to-one. We say that an algebraic map from a pure-dimensional quasiprojective algebraic set X to an irreducible quasiprojective algebraic set of the same dimension is a branched covering if / is proper and finite. We define the degree of / to be the number deg / in Corollary A.4.15. The following Lemma gives an easy local condition for properness. Lemma A.4.16 (Stein) Let f : X —> Y be a holomorphic map between complex analytic spaces. Assume that y £Y and A is a connected component (not necessarily

Algebraic Geometry

315

irreducible) of f~l(y). If A is compact, then there are open complex neighborhoods U c X of A and V Vis proper. Proof. See (Lemma 1, page 56 Fischer, 1976).

•

Using this and Grauert's Proper Mapping Theorem A.4.3, we have an extremely important existence result. Theorem A.4.17 Let f : X —> Y be a holomorphic map between complex analytic spaces. Assume that Y is irreducible and that all irreducible components of X have dimension at least equal to dimY. Assume that y € Y and x is an isolated point °f f1(y)IfY is locally irreducible at y, then, there are arbitrarily small complex neighborhoods U C X of x and V C Y of y such that f\j : U —> V is a proper surjective map with finite fibers. Proof. Choose a neighborhood X' of x. By Lemma A.4.16, there are open complex neighborhoods U C X' of x and V C Y of y, such that fu : U —> V is proper. By Theorem A.4.3, f(U) is a complex analytic subspace of V. Since x is isolated, we would be done in the algebraic case by Corollary A.4.12 and the irreducibility of Y at y. In the complex analytic case, we instead use Theorem A.4.13, which implies dim/([/) = dimY. From this and the irreducibility of Y at y, we conclude that f(U) contains a complex open neighborhood V of y. The rest of the result follows by replacing V by V, and U by U n f~l{V). U Example A.4.18 The local irreducibility is needed for the above result. Let X := C and let Y := V(g) C C2 be defined by g(x,y) = y2 - x2(x + 1). Consider the algebraic map / from to X -* Y given by f(t) = (-(1 + t2),yf-i(t + t3)). The reader can check that / is surjective and one-to-one everywhere except at ±%/^T which are mapped to (0,0). A small complex neighborhood U of (0,0) on Y is biholomorphic to a small complex neighborhood of 0 on V(xy). A small neighborhood of t = yf—l does not map onto a neighborhood of (0,0) in Y, but only onto a complex neighborhood of (0,0) on one of the irreducible components of U at (0,0). The following result underpins most constructions of homotopies. It asserts that under minimal conditions, isolated solutions of a system in a family of systems are limits of isolated solutions of nearby systems. Corollary A.4.19 Let X and Y be irreducible quasiprojective algebraic sets. Let f(x;y) be a system of N := dimX algebraic functions on X xY. Letir : XxY —> Y denote the product projection. Assume that x* is an isolated solution of f(x;y*) = 0 for some point y* such that Y is locally irreducible at y*. Then each irreducible component Z ofV(f) containing (x*,y*) satisfies the following properties: (1) dim Z = dim Y; and

316

Numerical Solution of Systems of Polynomials Arising in Engineering and Science

(2) there exist arbitrarily small open neighborhoods U C Z of x* and V C Y of y* such that 7T[/ is a proper finite map of U onto V. A number of stronger versions of Corollary A.4.19 are contained in § A. 14.

A.4.1

Generic

Factorization

The next theorem tells us that if we are satisfied with generic results, as we often are in numerical work, properness is unnecessary. The proof requires some constructions involving the graph of a map. Theorem A.4.20 Let n : X —> Y be a dominant algebraic map from an irreducible quasiprojective algebraic set X to an irreducible quasiprojective algebraic set Y. There exists a smooth Zariski dense open set U C Y and a smooth Zariski dense open set W of TT~1(U) such that nw factors nw — s or, where r : W —> V is a surjective maximal rank algebraic map with connected fibers and s : V —> U is an algebraic map and a finite covering map. In particular each fiber of TTW '-W-^U has the same number of irreducible components, i.e., degs irreducible components. Proof. In the following argument, we will repeatedly replace algebraic sets by dense Zariski open sets. For the most part, we call these shrunk sets by the same names. Replacing X by Xreg, we may assume that X is smooth. By shrinking Y and replacing X by the inverse image under n of the shrunk Y, we may assume that Y is smooth. Similarly using Chevalley's Theorem 12.5.6, we may assume that ?r(X) = Y. By using the algebraic Sard's Theorem A.4.10 and shrinking X and Y further we may further assume that IT is of maximal rank. Let X denote an irreducible projective algebraic set in which X is Zariski open. Let X denote the closure of Graph(7r) C X x Y in X x Y. The induced map W : X —> Y extending n is proper. By Hironaka's Theorem A.4.1, there exists a desingularization / : X —> X. Thus following Theorem A.4.8, we can factor ?F O / as a o p where p : X —> Z is an algebraic map with connected fibers; where Z is an irreducible quasiprojective algebraic set; and a : Z —» Y is a finite-to-one proper algebraic map. By Corollary A.4.15, there is a Zariski open dense set U' C Y such that U' and cr' 1 (t/ / ) are smooth and ov-^t/') : <J~1(U') —> U' is a covering. Thus by shrinking we may assume without loss of generality that a : Z —> Y is a finite-to-one covering; Z is smooth; and that p(X) = Z. As we shrink Z we may automatically shrink Y so as not to lose the properties already obtained. To see this let V' be a Zariski open set of Z. Since the image under a of the proper algebraic subset Z \ V is a proper algebraic subset, we may replace Y by U := Y \ a{Z \ V) and Z by V := o-1 (Y \ a(Z \ V1)) to still have an algebraic finite-to-one covering map a :V —> U between manifolds.

Algebraic Geometry

317

By using the algebraic Sard Theorem A.4.10 on p we may, after shrinking, assume without loss of generality that p is of maximal rank. Since X is smooth and / is an isomorphism on the inverse image of the regular points, we may regard X as a subset of X. By using Chevalley's Theorem 12.5.6, we may assume that px '• X —> Z surjects onto Z. Since all fibers of p are smooth and connected they are irreducible. We conclude that all fibers of px are smooth and connected. Indeed, if this failed, we would have a fiber of p which is irreducible, and which after removing a proper algebraic subset is disconnected. Taking U as the final shrunk Y, V :— a~1{U) and W as the final shrunk X, we have finished the proof of the theorem. • Corollary A.4.21 Let n : X —> Y be a dominant algebraic map from an irreducible quasiprojective algebraic set X to an irreducible quasiprojective algebraic set Y. Assume that 7r(Sing(X)) is a proper algebraic subset ofY. There exists a Zariski dense open set U C Yreg such that W := ?r~1(!7) is smooth; and ITW factors nw = s o r, where r : W —> V is a surjective maximal rank algebraic map with connected fibers and s : V —> U is an algebraic map and a finite covering map. In particular each fiber of irw '• W —> U has the same number of irreducible components, i.e., degs irreducible components.

Proof. Replacing Y by Y' := Y\ (Sing(y) U7r(Sing(X))) and X by TT^1 (Y1), it may be assumed without loss of generality that X and Y are smooth. The rest of the proof follows by carefully going through the proof of Theorem A.4.20. • A.5

Rational Mappings

Besides algebraic mappings, there is a more general notion of mapping that is often very useful. On C, the assignment / : x H-> 1/X is a well-defined function on C \ {0}. Using the identification of x € C with [1, x] € P 1 ,, it is natural to think of / as extending to a function on all of C that takes 0 to the value oo equal to [0,1]. In this case, the algebraic set {(a;, [x, 1]) e C x P 1 | x G C} is the graph of the map x —> 1/x regarded as a map from C —> P 1 . This is the simplest example of a rational mapping. A rational mapping f : X —> Y between quasiprojective algebraic sets is defined to be an algebraic set F C X x Y such that there is a Zariski open dense set U c X such that F n (U x Y) is the graph of an algebraic map and V D (U x Y) = T. Every algebraic mapping is a rational mapping, but rational mappings are much general. A rational mapping often has a set of indeterminacy, where it cannot be

318

Numerical Solution of Systems of Polynomials Arising in Engineering and Science

assigned any value. Consider the rational mapping given by the assignment / : (zi, z-+ 22/21 on C 2 . The corresponding set T c C 2 x P 1 is (z1,z2;[z1,z2]) e C 2 xP 1 . F does not define an algebraic map at (0,0). Indeed, there is no way to assign a value there since 22/21 has different constant values on different lines through the origin. The origin is the set of indeterminacy of / . Rational mappings may fail to be algebraic mappings even though they are continuous maps. For example, consider the algebraic map g sending t 6 C to (21,22) := (*2,£3) e C 2 . The image of g is the affine set C denned by z\ - z\ = 0. The map g is one-to-one and onto. The inverse from C to C may be checked to be a rational mapping: it is the restriction of the rational function 22/21. However, it is not an algebraic mapping, since t as a function on C is not the restriction of a polynomial p £ C[2i, 22]. A.6

The Rank and the Projective Rank of an Algebraic System

We define an algebraic system on a pure .ZV-dimensional quasiprojective algebraic set X to be a set of n algebraic functions f{x) := { / 1 , . . . , / „ } on X. Typically we assume irreducibility in theorems about systems and leave it to the reader to make the trivial adjustments in statements for the reducible case. We define the rank of the algebraic system f(x) = 0 on an TV-dimensional irreducible quasiprojective algebraic set X to be the dimension of the closure of the image / ( I ) c C". By Corollary 12.5.7, f(X) is an irreducible algebraic set. We denote the rank of / by rank/. We define the corank of the algebraic system f(x) = 0 to be N — rank/. Neither adjoining polynomial functions of the equations of / to create a larger system nor replacing / with g • f, where g is an invertible nxn matrix, changes the rank of a system. Theorem A.6.1 Let f(x) = 0 denote a system of n algebraic functions on an irreducible quasiprojective set X. Then there is a Zariski open set U c f{X) c C" such that for y € U, V(f(x) — y) PI XIeg is smooth of dimension equal to the corank of f. Moreover, the Jacobian matrix of f is of rank equal to rank/ at all points of

V(f(x)-y)nXTeg.

Proof. By Theorem A.4.10, we know there is a Zariski open set U C f{X) such that V(f(x) — y) is smooth and such that the Jacobian matrix of / has rank equal to dim/pQ at all points of V(f(x) -y). Corollary A.4.12 gives that dim V(f(x)-y) = N-dimf(X). • Let V and / be as in Theorem A.6.1. For the dense Zariski open set U :=

Algebraic Geometry

319

/~ 1 (y)nX r e g , we have for all points £* 6 U, the rank of the Jacobian of / evaluated at x* equals rank/. This gives us a quick probability-one algorithm for the rank for a system f. Given an algebraic system f(x) of n algebraic functions on an irreducible ./V-dimensional quasiprojective set X, the rank of / equals the rank of the Jacobian at a random point of X. The following is useful. Corollary A.6.2 Let f(x) = 0 denote a system of n algebraic functions on an irreducible quasiprojective set X. If the rank of the Jacobian of f at some point x E Xreg is k, then rank/ > k. Proof. The set on X reg where the Jacobian has rank less than or equal to A; is a quasiprojective subset of X reg . If it is dense then rank/ = k. If it is not dense, then the rank of the Jacobian is greater than A; on a Zariski dense set, which would imply rank/ > k. • Theorem A.6.3 Given a system f(x) of n algebraic functions on an irreducible quasiprojective set X, all irreducible components of V(f) have dimension at least equal to the corank of f. Proof. Use the proof of Theorem 13.4.2

D

The rank of a system is a useful invariant, but from the viewpoint of the Bertini Theorems, a closely related invariant, the projective rank of a system, plays a more central role. The first time reader may safely ignore the rest of this section and any mention of the projective rank of a system. The importance of projective rank stems from Theorem A.8.6, which states that projective rank controls the nonemptiness of the zero sets in Bertini Theorems. The projective rank of a system f is the dimension of the closure of the image of the rational mapping given by sending x G X \ V(f) to [/i(a;),..., fn(x)]. We denote the projective rank of / by rankp/. A system / on CN having projective rank N is called a big system. Remark A.6.4 For an algebraic line bundle and a system of algebraic sections / i , . . . ,fn, rank does not make good sense but projective rank does. It is closely related to the notion of Kodaira dimension, e.g., (Iitaka, 1982). Lemma A.6.5 Let f be a system of n algebraic functions on an irreducible quasiprojective algebraic set X. Then rank/ — 1 < rankp/ < rank/. Proof. The rational mapping used in the definition of projective rank factors as the composition of the map in the definition of rank followed by the map Cn \ {0} —> P™"1, which sends (ZQ, ..., zn-i) —> [ZQ, ..., zn^i]. Since the fiber of the map C™ \ {0} —> P " - 1 is dimension one, we are done. •

320

Numerical Solution of Systems of Polynomials Arising in Engineering and Science

The above proof makes clear how the two ranks may fail to be equal. Before we make this precise in Lemma A.6.7, let us give a definition and an example. Let X c P™ be an irreducible projective set. X is said to be a cone with vertex x e X if for some hyperplane H of Pra not containing x, the projection •KX : P™ \ {x} —> H maps X \ {x} to a set whose closure has dimension less than dimX. An irreducible affine algebraic set X C C™ is said to be a cone with vertex x G X if, when we regard Cn as a subset of P n , the closure of X in P n is a cone with vertex x. Example A.6.6 (Cones) Let Y denote an irreducible (N — l)-dimensional smooth complete intersection in p™-1 defined by homogeneous equations / i , . . . ,fn-N in the variables zo,..., zn-\. The Af-dimensional cone X := V ( / i , . . . , / n -jv) C C n intersects a general (n - iV)-dimensional linear subspace through the origin in the origin only. To see this, regard C" as contained in ¥n with the hyperplane at infinity Hoo given by V(zn). For positive integers m satisfying (m — 1) + (N — 1) < n — 1, there is a dense Zariski open set of m-dimensional linear subspaces L c C™ with

I n I n E 0 0 = (In H^) n (x n H^) = 0. Thus X C\ L = {0}, and this point is singular if degX > 2. Lemma A.6.7 Let f be a system of n algebraic functions on an N-dimensional irreducible quasiprojective set X. Then rank/ = rankp/ except when f(X) is a cone over 0. Proof. The proof of this is immediate from the definitions and left to the reader. • To compute the projective rank is easy. Theorem A.6.8 Let f be a system of n algebraic functions / i , . . . , / „ on an irreducible quasiprojective algebraic set X with one of the functions, fi, which we relabel f\, not identically equal to the zero function. Then

rankp/ = rank j , . . . , - ^ , I /i h ) where the system of quotients is defined on X \ V(/i). Proof. The proof of this, and the independence of the choice of the not identically zero fi, follows immediately from definitions and is left to the reader. • A.7

Universal Functions and Systems

In this section we will give a detailed discussion of certain special families of polynomials, which are useful in the study of polynomial systems.

321

Algebraic Geometry

A. 7.1

One Variable Polynomials

We start with the case of the most general degree d polynomial. Fix an integer d > 1. We have the family p(z, c) := c0 + ciz + ... + cdzd = 0.

(A.7.1)

We have some related issues we must face already. (1) Should we insist that cd ^ 0? (2) Would it be better to include "solutions at infinity" by using the homogenized system

p(z,c) := cO2o + ciz^zi

+ ... + cdzf = 0

withz := [zo,zi] G P 1 ? (3) Since multiplying an equation by a nonzero complex number does not change the solution set of the polynomial, should we make the convention that c is not the point (c 0 , ...,cd) G C d + 1 , but instead [c0, ...,cd] G P d ? Doing this, of course, implicitly throws away the identically zero polynomial, that corresponds to c = 0. For simplicity, we look only at polynomials with no restrictions on the c*, i.e., we assume that (z,c) = (z,c0,... ,cd) G Cd+2 corresponding to polynomials of degree < d. The different choices raised by the issues listed above are treated in a similar way. Let's introduce some notation. We let Zd c Cd+2 denote the solution set of p(z, c) = 0. We let n : Zd —> Cd+1 denote the map induced by the projection (z, c) —> c, and we let p : Zd —> C denote the map induced by the projection 0,c) ->• z. Note that for any given c € Cd, n~1(c) consists of the points (z,c) satisfying p(z, c) = Co + c\z + . . . + cdzd = 0. It is important that the zero set Zd C Cd+2 oip(z,c) = 0 is a connected (d + l)-dimensional complex manifold. Indeed, Zd is dimension d+ 1 since it is denned by a single algebraic function on an irreducible d'oi z cl (d+ 1)-dimensional algebraic set. Moreover, since —^ ' = 1, it is a consequence OCQ

of Theorem A.2.8, that Zd is smooth. To show the connectedness of Zd, we apply the criterion that a space (in our case Zd) is connected if a continuous map (in our case p : Zd —> C) has connected image and fibers. To see this, note that the fiber p~1(zt) of p over an arbitrary point zt G C is the set of (z*,c) such that p{z*,c) = 0. Since this is the linear equation CQ + C\Z* + ... + cdzd = 0 in the variables c G C d + 1 , we see that p~1(z*) is identified with a hyperplane of Cd+l by ir. Since Zd is connected and smooth, it is irreducible. Over all points except 0 6 C d + 1 , n has finite fibers.

322

Numerical Solution of Systems of Polynomials Arising in Engineering and Science

Let us consider the points c for which p(z, c) has multiple roots, i.e., less than d distinct roots. This corresponds to points c for which the equations P(Z>C)] _n dP(z,c) — u . dz J

,A 7 9 N {A. (.A)

have a common root. The classical prescription, e.g., (Chapter 1 Walker, 1962) and (Cox et al., 1997), for how to eliminate z from these equations constructs the discriminant of p(z,c), a polynomial of degree Id — 1 in c, which is the resultant of the two polynomials in the system (A.7.2). We only discuss resultants briefly in § 6.2.1 of this book. For us it will be enough to note that (1) for some c», e.g., the c* corresponding to the polynomial zd — 1 = 0, the roots are distinct; (2) for c in a complex neighborhood of c* the roots remain distinct; and (3) the set S in Cd+1 denned by the system A.7.2 is an affine algebraic set. We know from item 3) and Chevalley's Theorem 12.5.6 that TT(<S) is a constructible set. We know that the closure T> of n(S) in the complex topology is an affine algebraic set by Lemma 12.5.3. By item 2) we conclude that V ^ C d+1 and thus that the Zariski open set C d + 1 \ T> is nonempty, and hence dense. A.7.2

Polynomials of Several Variables

The construction of § A.7.1 carries over to several variables. We summarize the construction for polynomials of degree < d on CN. Such a polynomial

P(z,c)= Yl °JzJ \j\
depends on A/" := ( j~ ) coefficients cj, where we use the multidegree notation. We regard p(z, c) as a polynomial on CN x C . By the same reasoning as in § A.7.1, we see that Z^ := V(p(z,c)) is smooth, connected, and of codimension one. Moreover by Theorem A.4.10, there is a Zariski open dense set U C O^", such that the restriction of the projection map TT : CN x C —> CN to Zd H TT~1(U) is a maximal rank map. A.7.3

A More General Case

Let fi(x),..., fn{x) be a set of algebraic functions on an irreducible quasiprojective algebraic set X. For example, these might be a set of rational functions PlQ)

Pn(x)

Qi(x)''""'' qn(x) where the Pi(x) and <&(#) are polynomials on CN and X := CN \ (\J™=1V(qi(x))).

323

Algebraic Geometry n

We define the universal function F(X: x) := V^ A;/,(z) on Cn x X. i=l

It is traditional in this context to refer to the solution set V(f) of the set of algebraic functions fi(x),..., fn{x) as the base locus of the set of functions. We will not use this language, but the reader should be aware of it. Zf : = V(F) i s a quasiprojective algebraic set with Zf (1 [Cn x (Xieg \ V(f))] smooth. Moreover there is a Zariski open dense set U C Cn, such that the restriction of the projection map -K : Cn X (Xreg \ V(/)) —> C" to Zf H TC~1 (U) is either empty or a maximal rank map. This is important enough to state as a Theorem. Theorem A.7.1 (Simple Bertini's Theorem) Let f{x) := {fi,- • • ,fn} be a system of algebraic functions on an irreducible quasiprojective algebraic set X. There is a Zariski open dense set U C C™, such that for (Ai,...,A n ) G U, it follows that g := Yli=i Ai/i has a possibly empty quasiprojective zero set Z such that Z (~i (Xreg \ V(f)) is smooth with the differential dg nowhere zero on

zn(xieg\V(f)).

Proof. First note that we can assume that X is smooth and V(f) is empty, by simply replacing X with (XTeg \ V(/)) and renaming. Note that if rank/ = 0, then each g is constant and the theorem is vacuously true. Therefore we can assume that rank/ > 0. We have the "universal function" F(\,x) :— X^ILi ^ifi(x) defined for (X,x) G n C x X. Zf := V(F) C X is smooth by the same reasoning as used in § A.7.1. Consider the maps TTI : Zf —>• Cra and 7T2 : Zf —> X induced by the projections C " x X - » C " a n d C n x I ^ I respectively. The fiber ^(x) for any x G X is an affine hyperplane of C™. It can be further checked that given any x e X, there is a neighborhood O of x in the complex topology such that 7r^"1(C7) is biholomorphic to C"" 1 x C. Thus Zj is a bundle over X and therefore irreducible of dimension dimX + 71—1. We are in the situation of Theorem A.4.10, and would be done, if we knew that 7Ti is dominant. Assume it is not. Then, there is a Zariski open dense set U C C n such that for A G U we would have that V(£)™=1 A,/*) = 0. • A. 7.4

Universal

Systems

Let / i ( x ) , . . . , fn(x) be a set of algebraic functions on an irreducible quasiprojective algebraic set X. For any positive integer s, we define the universal system "Fi(A,x)i F(A,x):=

:

_F s (A,x)J on C s x " x X.

["Ai,i ••• Ai,n"i = A • /(z) =

:

•..

:

LAS,1 ••• A s , n J

r/r •

:

[fn.

324

Numerical Solution of Systems of Polynomials Arising in Engineering and Science

Define Zf := V{F(A,x)) C Csxn x X. Let -KX : Zf -> C s x n and TT2 : Z/ -> X denote the projections induced from C sX71 x X -+ C SXri and C s x " x I -> X respectively. L e m m a A.7.2

IfV(f)

= 0 £/ien Z j is irreducible of dimension dim.X + s(n— 1).

Proof. The set 7r^"1(x) for x 6 X may be identified with the linear space of A 6 Csx™ satisfying A • / ( x ) = 0. Since f(x) ^ 0, this space has codimension s. It can be further checked that given any x G X there is a neighborhood 0 of a: in the complex topology such that T T ^ ^ O ) is biholomorphic to ^ ' " " ' ' x O . Prom this it follows that the set Zf C C s x n x X consisting of (A, x) such that F(A, x) = 0 is an irreducible • set. Lemma A.7.3

IfV(f)

is empty, then Zf D (CsX™ x Xreg)

is smooth.

Proof. Since at any point x G V(F) C Csxn x X at least one of the / , is nonzero, we can see that all the partial derivatives

dFj{A,x) From this we see that V{F) n (Csxn x X r e g ) is smooth.

D

After we develop a few results on linear projections and subspaces, we will prove Theorem A.8.7, the analogue for systems of Theorem A.7.1.

A.8

Linear Projections

"Generic" projections have been used since classical times to reduce questions about general algebraic sets to questions about hypersurfaces. Here we present the basic facts that we need. We follow the presentation in (Sommese et al., 2001c) closely. A linear projection n : CN —> C m is a surjective affine map ?r(x) = a + ^ x ,

(A.8.3)

where «i,o

o=

: .«m,oj

We work with from CN onto with T(TTI(X)) fibers through

a i , i • • • ai,N

; A=

: • . : L a m , l • ' • a m,JVJ

Xi

; and x =

:

(A.8.4)

LXN.

equivalence classes of projections, considering two projections 7Ti,7r2 C m equivalent if there is an affine linear isomorphism T : C m —• C m = 7T2(x). Thus, for us two linear projections are the same if their the origin are parallel (N - m)-dimensional linear subspaces of C ^ ,

Algebraic Geometry

325

i.e., TTJ~ (TTI(O)) is parallel to TT^" (7^(0)). So in the special case of linear projections from C^ —> C^^ 1 with N > 2, we can consider the projections to be parameterized by the lines through the origin, or equivalently the hyperplane at infinity H^ := N V(ZQ), where we regard C^ as embedded in ¥ by ( x i , . . . , XN) - » [z 0 , • • • , ZN\ = (1, Xi, . . . , I J V ) .

This observation will play an important role in § A.10.3. Though we can use the set ofmxJV matrices A g C mXiv with rank A — m to parameterize the linear projections, it helps to keep the geometrical correspondence between projections and the nullspaces of the matrices A in mind. As noted in the last paragraph, when m = N — 1, we are dealing with lines and the natural parameter space is the projective space parameterizing lines though the origin in C^. For linear subspaces of other dimensions this leads us to Grassmannians. A.8.1

Grassmannians

We denned the iV-dimensional projective space P^ in § 3.2 as the set of lines through the origin in CN+1. Replacing linesby (m+1) -dimensional linear subspaces through the origin leads to the notion of a Grassmannian. We define the Grassmannian of (m + l)-planes in (N + l)-space to be the set of all (m + l)-dimensional linear subspaces of CN+1 through the origin. Equivalently this is the space of linear P m s in FN. We denote this space Gr(m, N). The reader should be aware that there is a second convention in the literature where the focus is on CN+1, and the space we denote Gr(m, N) is denoted Gr(m + 1, N + 1). An (TO + l)-dimensional subspace of C w + 1 through the origin is determined by m + 1 elements of CN+1. In analogy with homogeneous coordinates on projective space, we may represent an element of Gr(m, N) by an (m + 1) x (N + 1) matrix A. Conversely, we would like an (m + 1) x (N + 1) matrix A to represent an element of Gr(m, N). For A to represent an (m + l)-dimensional linear subspace, A must have rank m + 1 , e.g., for projective space P^ = Gr(0,N), the (N + l)-tuples [zo,... ,ZN] £ FN are not allowed to have all entries 0. In analogy with homogeneous coordinates on PN, if G is an (m + 1) x (m + 1) invertible matrix, then the rank m + 1 matrices A and G • A represent the same linear subspace. As with FN, we can define embeddings of c( m + 1 ) x ( i V - m ) into Gr(m, N). Indeed, given an (m+1) x (N — m) matrix B, if we send it to [Im+i B], we have a one-to-one mapping. We take this as giving a neighborhood of any of the elements of the image of this map. We can construct other embeddings of c(m+i)x(W-™) whose unions cover Gr(m, N), but do not do so since we do not need this. Grassmannians are connected projective manifolds. As we saw above, the dimension of Gr(m, N) is (m + 1) x (N — m). There is a natural embedding

GrfoNO-pG+D-1

326

Numerical Solution of Systems of Polynomials Arising in Engineering and Science

called the Plucker embedding obtained by sending an (m + 1) x (AT + 1) matrix A representing a point of Gr(m, N) to the point in p U + i ) " 1 with the (^1J) determinants of (m + 1) x (m + 1) submatrices of A as homogeneous coordinates. Since using G • A in place of A multiplies all these homogeneous coordinates by det G, this mapping is well defined. There is a large literature on Grassmannians. The analogy for Grassmannians of the linear projections from FN to lower dimensional projective spaces, that we consider in § A.8.2, are similar mappings from Gr(m, N) to lower dimensional Grassmannians. The isomorphism of a vector space and its dual leads to the isomorphism between Gr(m, N) and Gr(N —m, N). A good place to read more on these useful homogeneous manifolds is (Griffths & Harris, 1994). For detailed information, (Hodge & Pedoe, 1994b) is particularly helpful. In the same vein as § A.7.4, it may be shown that there is a connected projective manifold Ti c Gr(m, N) x P N consisting of all points (L, x) where L G Gr(m, N) is an m-dimensional linear subspace of P ^ and x G PN is a point in the subspace of PN represented by L. By standard abuse of notation, this is denoted by x £ L. Let 7i"i : 7i —> Gr(m, N) and 7T2 : 7i —> PN denote the algebraic mappings induced by the projections Gr(m,N) x P N -> Gr(m,N) and G r ( m , N ) x P N - > P N respectively. The mapping TTI is of maximal rank with the fiber ir~1(L) over L G Gr(m, N) mapped isomorphically to L by 7T2- Thus

dimH = (m + 1)(N - m) + m. The mapping TT2 is of maximal rank with the fiber 7r^"1(a;) for x G PN mapped isomorphically by w\ onto the Gr(m — 1, JV — 1) of m-dimensional linear spaces of P ^ that contain x. Thus dim7r^"1(a:) = m(N — m) Regarding CN as P ^ minus a hyperplane H, there is a one-to-one correspondence of m-dimensional affine linear subspaces of CN with the dense Zariski open set U C Gr(m, N) of m-dimensional linear subspaces L of P ^ not completely contained in H. The algebraic set Gr(m, N) \U is thus identified with Gr(m, N — 1). Theorem A.8.1 Let X be an n-dimensional affine algebraic subset of CN (respectively projective algebraic subset of¥N). Ifn + m < N, there is a dense Zariski open set U C Gr(m, N) of affine linear subspaces L C C ^ (respectively of linear spaces L C PN) of dimension m not meeting X. Proof. Using the identification of affine linear spaces of C ^ with linear spaces in P ^ , we only need to show this result in the case of FN. Note that d i m T r ^ X ) = n + m(N — m). Thus 7Ti(7r^"1(X)) cannot be dense because if it was

(m+l)(N-m) = dimGr(m,N) = dimTr^Tr^^X)) < dimTr^pQ = n+m(N-m). This implies the contradiction N — m < n. Theorem A.8.2

•

Let X be an n-dimensional algebraic subset of CN (respectively

Algebraic Geometry

327

projective algebraic subset of FN). Assume n + m < N. For a given x € X, there is a dense Zariski open set U of m-dimensional affine linear spaces L C CN containing x (respectively m-dimensional linear spaces L C fN containing x) such that L D X = {x}. Moreover if x € X r e g , then U can be chosen so that in addition TL,X n Tx,x =x £ TCNIX (respectively TL,X n Tx,x =x£ T¥N^X), where TLtX! Tx,x, Tpjvj,, TCN >x are the tangent spaces of L, X, P w , C ^ respectively at x. Proof. This theorem is proved by reasoning similar to that for Theorem A.8.1. We only prove the case when X is projective algebraic (the quasiprojective case requires the projective case plus an application of Lemma 12.5.2). Fix a point x £ X C ¥N. The L € Gr(m, N) that contain x, i.e., G\ := 7T1(7r2"1(ar)) is isomorphic to Gr(m — 1,N — 1) and thus irreducible and m(N — m) dimensional. The set L containing x and a point y ^ x is isomorphic to the set G2 '•— Gr(m — 2, N — 2) and thus (m — 1)(N — m) dimensional. The set W of L that contain x and some other point y of X is thus of dimension at most (m — l)(iV —TO)+ n. Here we are using the fact that W is projective. To see this let 52 : G± —> fN denote the algebraic ir^q^iX)). mapping induced by TT2- W is the set = N-m-n>l, Since dimGi - d i m W > m(N -m) - ((m - l)(iV -m)+n) we conclude W is a proper algebraic subset of an irreducible projective algebraic set C?2- Thus there is a Zariski dense open set G2 \ W of m-dimensional projective linear spaces L containing x and no other point of X. The tangent space assertions follow by a dimension count showing that the space of L € Gi such that TL,X H TX,X ¥" x ^ TPN<X is of dimension less than dim G2- The details are left to the reader. • Theorem A.8.3 Let X be an n-dimensional affine algebraic subset of CN. Assume n + m > N. There is a dense Zariski open set U of m-dimensional linear m>N,U subspaces L C CN such that LH X is of dimension n + m — N. Ifn + may be chosen so that if L G U then L D XTeg is nonempty. Proof. Using the same sort of reasoning used in Theorem A.8.2 or a repeated use of Theorem A.7.1 gives this result. •

A.8.2

Linear Projections on FN

We need to consider the extension of projections to projective space. Such projections have traditionally been a major tool in algebraic geometry and are a perennial focus for research, e.g., (Beltrametti, Howard, Schneider, & Sommese, 2000). Let [z0,..., ZN\ denote linear coordinates on fN. As above, we regard CN C fN using the inclusion (xu ... ,xN) —> [z0,... ,zN] = [ l , x i , . . .,xN]. Thus C w = P w \ Hoo, where HOQ := V(ZQ) is the hyperplane at infinity.

328

Numerical Solution of Systems of Polynomials Arising in Engineering and Science

A projection from WN to P m is a surjective map nL : FN \ L -> P m with n(z) = Az,

(A.8.5)

where a

A=

0,0

a

'• .SO

a

l,l

'''

'•

"•

rn,l

a

0,N

ZQ

:

and

z =

: L ZN .

••• a m . w j

and where i is the linear projective space p^- 7 7 1 " 1 c P w defined by the vanishing of the linear equations Az. L is the center of the projection. Theoretically, we work with equivalence classes of projections, considering two projections TTI, TT2 from PN onto P m equivalent if they have a common center L and there is a projective linear isomorphism T : P m -> P m with T(TTI(X)) = -K2{x) on P ^ - L. Note that two projections from P ^ to P m are equivalent if and only if they have the same center L. Thus the linear projections ¥N —> P m are naturally parameterized by the Grassmannian Gr(N — m — 1,N) of (N — m— l)-dimensional linear spaces L c PN. Geometrically, the projection -KI has a simple description. Let L be the center of the projection. Choose any P m C P ^ with the property that L D P m = 0. Given a point x e WN \L and letting (a;, L) denote the linear subspace FN~m C P ^ generated by x and L, the projection from P ^ to P m with center L sends x to (i,L)nPra. The projections nL from P ^ to P m that are extensions of projections from C^ to C m are precisely the projections with centers L C H^. Indeed, let y i , . . . , ym be coordinates on C m and let the usual embedding of C m to P m be given by { y i , . . . , y m ) -> [ w o , . . . , w m ] = [ l , y i , . . . , y m ] , Since we must have a linear equation in Xi,... ,XN when we dehomogenize with respect to w0, we conclude that A is of the form " ao,o

. a m,0

0

a

•• •

0 '

m,l ' ' ' am,N .

with o0,o / 0. Using the invertible linear transformation on P m

T

-=\ \°1

329

Algebraic Geometry

ai,o

where u :=

•

, we see that an equivalent form for A is

.am,0.

where A is as in Equation A.8.4. For example, the projection (xi,... ,XN) —» (xi,... ,a;jv_i) extends to the projection [XQ, ..., XJV] —> [xo,a;i,..., rrjv-i] with center L := {[0,..., 0,1]}. To recapitulate a main point: an equivalence class of linear projections is naturally identified with the center of the projection in the projective case and with the center of the projective extension of the linear projection in the affine case. A.8.3

Further Results on System Ranks

We have a few more properties on the behavior of the rank of a system under randomization. Lemma A.8.4 Let X C C n denote an irreducible affine algebraic set. Then for any nonnegative integer s, there is a dense Zariski open set of linear projections CN —> Cs such that the dimension of the closure of the image of X is min{dimX, s}. Proof. We regard Cn as the complement in P n of a hyperplane Hoc. We first do the case of s > dim X. As we saw above, the linear projections are parameterized by the Grassmannian G :— Gr(n - s — 1, n — 1) of linear P"~'s~1s contained in H^. We have dimXnffco < d i m X - l . Since (dimX - 1) + (n - s - 1) = n — (s - dimX) — 2 < n — 1, we conclude from Theorem A.8.1 that there is a Zariski open dense set U of G corresponding to linear pn-s-i s m i s s m g X n Hoo. Given one of these, say L, and the associated linear map irL,

t h e fiber -K^(irL{x))

t h r o u g h x G X i s (x,L)

H X.

S i n c e L n (X \ X) = 0 ,

(x, L)nX is compact and hence finite by Lemma 12.4.3. Thus by Corollary A.4.12, the closure of the image of X has dimension the same as X. The case of s < dimX follows from the case s = dimX and the observation that if s < dimX, then a dense open set of linear projections from Cd™^ —> C s are onto. • Theorem A.8.5 Let f(x) — 0 denote a system of n algebraic functions on an irreducible quasiprojective set X. For any positive integer s, there is a dense Zariski open set of matrices U C Csxn such that ifAeU, then rank A • / = min{s, rank/}.

330

Numerical Solution of Systems of Polynomials Arising in Engineering and Science

Proof. Applying Lemma A.8.4 to f{X)~; there is a dense Zariski open set U of A £ C s x n such that dim(A-/)(X) = min |dim/(X), s\ . • The following useful result adds an existence component to Bertini's Theorem. Theorem A.8.6 Let f be a system of n algebraic functions / i , . . . , / n on an irreducible N-dimensional quasiprojective algebraic set X. Assume that rankp/ — K. Then there is a Zariski open dense subset ofUd CKXn of K X n matrices such that for A £ U, any subset of i distinct functions from the K functions A • / has a nonempty solution set on Xieg, which is smooth and of dimension N — i. Proof. This follows from application of Theorem A.8.2 to the closure of the image ofXinP"-1. • A.8.4

Some Genericity Properties

We have the important generalization of Theorem A.7.1. T h e o r e m A . 8 . 7 ( S i m p l e B e r t i n i T h e o r e m f o r S y s t e m s ) Let fi,--.,fn

be a

system of algebraic functions on an irreducible quasiprojective algebraic set X with solution set V(f). For each s x n matrix A £ Csxn, let F{A,x)~

'Fi(A,x): =A-/(x) .Fs(A,x)_

on C s x n x X. There is a Zariski open dense set U C Csxn of s x n matrices such that for A £ U, it follows that V(A • / ) C X is a quasiprojective set such that if Z\ '•= V(A • f) \ V(f) is nonempty, then dim^A = dimX — s, and Z\ (~l XTeg is smooth with the differentials dFj spanning the normal bundle of ZhC\Xve&. Moreover the number of components of Z/^ fl Xreg is independent of A £ U. Proof. The set U' of A with rank equal to min{s, n} is dense and Zariski open. Therefore, by replacing any dense Zariski open set U C C s x n that is constructed below with its intersection with U', we may assume that all A G U have rank equal to m'm{s,n}. By replacing X with X\V(f) we can assume that the /; have no common zeros. Denote V(F(A,x)) C C s x n x X by Zf. By Lemma A.7.2, Zf is irreducible of dimension dimX + s(n — 1). By Lemma A.7.3, Zf f) (C s x n x Xreg) is smooth. Let TTI : Zf —> CSXn denote the algebraic map induced by the product projection sx C ™ x X —> C s X n and let TT2 : Zf —> X denote the algebraic map induced by the product projection
Algebraic Geometry

331

Therefore we may assume without loss of generality that wi restricted to Zf is dominant. By Corollary A.4.12, there is a Zariski open set U C Csxn such that for y eU, all components of ^:[1{y) have dimension dimZy - dim
z& n Xies is smooth with the differentials dFj spanning the normal bundle of Z\ n Xreg. A.9

•

Bertini's Theorem and Some Consequences

In this section we present a general Bertini Theorem about the solution sets of systems. Since the intersection of any finite number of dense Zariski open sets is Zariski open and dense, we can (and typically do) apply Bertini's Theorem to conclude that a generic choice of some parameters leads to a long list of generic properties. To state such a result succinctly, let us define the constellation of algebraic sets associated to a finite number of quasiprojective subsets X\,..., Xr of a quasiprojective set X to be the collection of sets obtained by repeatedly doing in any order the operations of (1) (2) (3) (4) (5)

taking irreducible components; taking intersections; taking the singular set of a quasiprojective algebraic set; taking finite unions; and given two sets A, B taking the set A \ A D B.

Lemma A.9.1 The constellation of algebraic sets, C, associated to a finite number of quasiprojective subsets X\,-.., Xr of an algebraic set X is a finite set of quasiprojective sets. Proof. All these operations start with quasiprojective algebraic sets and produce quasiprojective algebraic sets. To prove that C is finite, it suffices to show that the set of all the irreducible components of the quasiprojective sets obtained by these operations is finite. Since an irreducible quasiprojective algebraic set A minus a proper algebraic subset remains irreducible, the last operation leads only to the finite number of quasiprojective algebraic sets A \ A f) B for the collection of quasiprojective sets J4, B generated by the first four operations. Thus it suffices to prove the finiteness of

332

Numerical Solution of Systems of Polynomials Arising in Engineering and Science

the collection of sets generated from X±,..., Xr by a repeated use of the operations 1), 2), 3), and 4). Since any intersection is a finite union of intersections of irreducible quasiprojective algebraic sets, it suffices to prove the finiteness of the collection of sets obtained by starting with X\,... ,Xr and repeatedly doing only the operations 1), 2), and 3). Note that the operations of taking intersections of irreducible sets and taking singular sets decreases dimensions if it leads to anything new. Thus, by the fact that dimension is finite, the operations 1), 2), and 3) lead to only a finite number of quasiprojective sets. D Let gi,... ,gs be a set of algebraic functions defined on a quasiprojective algebraic set X. Denote the solution set of all the functions, i.e., V(gi,... ,gg), by V(g). We say that g\,..., gs are simply generic with respect to a /c-dimensional irreducible algebraic set Z C X if given any integers 1 < i\ < ... < ir < s, it follows that (1) ifr >kthenV{gtl,...,gir)nZ (2) if r < k then either V{gtl,...,

cV(g); and gir) D (Z \ V(g)) is empty or

dimV(gil,...,gir)n(Z\V(g))

=

k-r

and V{gil,...,gir) n (Zreg \ V(g)) is smooth with the differentials dgit,..., dgir having rank r in the tangent space Tz,x any x e V(gil,..., gir) n (ZTeg \ V(
=

;

••.

•

'

. A s , l • ' • ^s,n .

the s x b submatrix A ( j i , . . . , j b ) 6 Csxb of A G C s x n associated to the list of integers 1 < j i < . . . < jb < n is defined to be Ai,ji • • •

A(ji,...,jfc) : =

:

••.

^i,jb

:

-As,ji ' • • *s,jb _

The following Bertini theorem expands on the conclusions reached in § A.7.3. T h e o r e m A . 9 . 2 ( B e r t i n i T h e o r e m f o r C o n s t e l l a t i o n s ) Let fi,...,fn

be a

set of algebraic functions on a quasiprojective set X. Given any finite number A\,... ,Am of quasiprojective subsets of X, let C denote the constellation of quasiprojective sets associated to (1) the sets A\,..., Am; (2) all irreducible components of X; and (3) all sets of the form V(fjl,... ,fjb) for the lists of integers 1 < jx < ... < j b < n.

333

Algebraic Geometry

Then there is a Zariski dense open set U C CsXra, such that for A e U and any list 1 < ji < • • • < jb < n the functions

:

:=A(ji,...,jb)-

\

.9s \

[fjb.

are simply generic with respect to every irreducible set in C. Proof. Since the intersection of dense Zariski open subsets of Csxn is dense and Zariski open, it suffices to prove the result for a single irreducible set Z e C of some dimension k. Further if we showed that for a given list l < i i < . . . < i r < s , the result is true ioi gi1,..., gir where "fill :

[/ji" := A ( j i , . . . , j b ) •

.9s J

:

[fjb.

with A in a dense Zariski open set U(ii, •.., ir;ji, • • • ,jb) C C s x n , we will be done by taking the intersection of these open sets indexed by the finite number of lists of integers 1 < i\ < ... < ir < s and 1 < j \ < ... < % < n. Therefore by renaming, it suffices to prove that there is a dense Zariski open set (/ C C s x n for any s
r/r

"si] :

:=A-

.9s\

:

,

[fn.

it follows that (1) if r > k then % , . . . , j s ) n Z c V(/); and = k - r and V(gi,... ,gB) n (2) if r < k then dimV(9l,... ,gs) n (Z\V(f)) (Zreg \ V(f)) is smooth with the differentials dgi,..., dgs having rank r in the t a n g e n t s p a c e Tz,x for a n y x e V(gil

,...,gZr)n

(Zreg \

These assertions follow immediately from Theorem A.8.7.

V(g)).

•

There are many versions of Bertini's Theorem in the literature, e.g., (Example 12.1.11 Fulton, 1998). For a further discussion of Bertini theorems, see also (§1-7 Beltrametti & Sommese, 1995).

334

A.10

Numerical Solution of Systems of Polynomials Arising in Engineering and Science

Some Useful Embeddings

There are some natural embeddings of algebraic sets that are useful. For simplicity, we give versions for projective algebraic sets, though similar constructions are equally useful for affine algebraic sets.

A.10.1

Veronese Embeddings

Let N and d be positive integers. The Veronese embedding is the natural embedding

to the point with homogeneous coorobtained by sending the point [ZO,...,ZN] J dinates made out of all the monomials {z \ \J\ = d} where we use multidegree notation. The restrictions of the linear equations ¥^ N >~ to the image of the Veronese embedding give all the degree d equations of VN.

A.10.2

The Segre Embedding

Let Ni,...,

Nr be r positive integers. The Segre embedding is the natural embedding P^ 1 x . . . x FNr -> p n L i W + i J - i

given by sending the point [zito,..., Z±>N1 ; . . . ; zr,o, • • •, Zr,Nr] to the point with homogeneous coordinates made out of all the monomials z\^ • • • zr^T. Remark A.10.1 The degree of the image of the Segre embedding of the multiprojective space FNl x . . . x PNr in p n r=i( Ar ;+ 1 )- 1 i s the multihomogeneous Bezout number for the system with X)[=i Ni equations all of type ( 1 , . . . , 1). This may be checked, e.g., using Equation 8.4.15, to be / V

N- \

\N1,---,NrJ-

CV"

7V-V

N1\---Nr\-

On a theoretical level, the Segre embedding shows that subsets of multiprojective spaces defined by multihomogeneous equations may be regarded as projective algebraic sets. One case is of special interest. Example A.10.2 (The Quadric Surface) Let S := P 1 x P 1 with bihomogeneous coordinates [zi,o, zi,i; Z2,o, ^2,i]- Let [wo, wi, ^2,^3] denote the homogeneous coordinates on P 3 . The Segre embedding of P ' x P U P 3 given by [wO,Wi,W2,W3]

: = [zi,0Z2,O,Zl,1*2,0, Zl,0Z2,l>zl,1^2,1]

has as image the smooth quadric V(u>oW3 — Wiit^)-

Algebraic Geometry

335

The Segre embedding is useful because it gives a consistent way of measuring the degrees of pure-dimensional algebraic sets on P^ 1 x ... x WNr. Remark A.10.3 (Measuring Degrees) Measuring degree by using the Segre embedding gives the smallest possible values of all the consistent ways of measuring the degrees of pure-dimensional algebraic sets. Other consistent ways may be obtained by using the Veronese embedding on the different projective spaces followed by a Segre embedding. In the language of line bundles mentioned briefly in § A. 13, such a choice is equivalent to choosing an ample line bundle L on M := P^ 1 x ... x ¥Nr and then denning the L-degree degL(X) of a pure fc-dimensional X C M to be c\{L)k • X, where ci(L) is the first Chern class of L. A.10.3

The Secant Variety

To derive properties of generic projections, we need to define the secant variety of an affine algebraic set X. Let X be an irreducible affine algebraic subset of C^. Given two distinct points x, y e X, we have a unique line between them, parameterized by u € C as (1 — u)x + uy. Let A denote the diagonal A := {{z, w) € X x X \ z = w} . Then the image of the map / : ( I x I \ A ) x C - > C A r , defined by f(x, y, u) = (1 u)x + uy is a constructible set by Theorem 12.5.6. The secant variety of X, denoted Sec(X), is the closure in CN of the image of this map. By Corollary 12.5.7, Sec(X) is an irreducible affine algebraic set. By Lemma 12.5.2, dimSec(X) < 2dimX + 1. L e m m a A.10.4 Let X be an irreducible affine algebraic subset of CN. If N > 2d\mX + 1, then a generic linear projection TT : C ^ " 1 applied to X is one-to-one. Proof. Embed CN into PN by the map (zi,...,

ZN) —> [XQ, . . . , XN] = [1, Z\,..., ZJV].

Let HQ := V(XQ) denote the hyperplane at infinity. Then Sec(X), the closure of Sec(X) in ¥N, meets Ho in a proper algebraic set of Sec(X). Thus dim iJonSec(X) < dim Sec (X). So we conclude that dim# 0 n Sec(X) < dimSec(X) - 1 < 2dimX < N - 1 = dimH0. Thus Ho
336

Numerical Solution of Systems of Polynomials Arising in Engineering and Science

A.10.4

Some Genericity

Results

Let X C C ^ be an irreducible affine algebraic set. Let n : CN —> C m be a linear projection. The restriction nx, of n to X, does not have to be proper. For example, the map from the hyperbola V(xi^ — 1) to the x\ axis has as image the complement of the origin and is therefore not proper. It is a part of the Noether Normalization Theorem 12.1.5, that if 7r is general, then the restriction wx, of n to X, is proper. We now go over the geometric proof behind a form of Theorem 12.1.5, which includes some degree information.

Theorem A.10.5 (Noether Normalization Theorem) Let X C CN denote an affine algebraic set. Let TV : CN —> Ck denote a generic linear projection. Then if dim X < k, the map TTX is a proper algebraic map with all fibers nxl{y) finite for ally GY :=TT(X). If dim X < k, then there is a Zariski dense subset U C X such that iru : U —> TT(U) is an isomorphism. If X is of pure dimension k, then nx is a branched covering of degree degX. Proof. Let X denote the closure of X in P ^ . Here we embed C ^ by sending (xi,...,xN)

G CN t o [zQ,...,zN]

= [l,xi,...

,xN] 1

G FN. A s a b o v e , w e l e t # o o N Q 1P ; equal to V(ZQ). Linear

denote the hyperplane at infinity, i.e., the p ^ projections CN —> Ck correspond to (N — k — l)-dimensional linear subspaces Z/Ar_fc_i c Hoo. Fixing a general fc-dimensional linear subspace Sk C P ^ , the to map 7T£ : ¥N —> ¥k associated to £, an L w _ fc _i c i?oo, sends x ePN \ LN-k-i T^cix) = Sk n (x,Ljv-fc-i). If C does not meet the projective algebraic set X \X, then TT£ is proper when restricted to X. Since d i m X \ X < dimX < k, we conclude that the set of C C H^ that meet X \ X is a proper algebraic subset A of the Grassmannian Gr(N - k, N) of linear PJV~fcs in P ^ " 1 . This implies properness of the restrictions to X of projections 7f£ with C in the complement of A. If a fiber of -KC on X was not finite, then since the restriction of TT£ is proper, we would have a compact projective subset of X which is not finite. This is absurd by Lemma 12.4.3. If dimX < k, then it is sufficient to show that given a general point x of an irreducible component of X, a general £ = fN~k containing x meets X in no other points and the map associated to H^ n C has maximal rank at x. This makes sense since the general point of an irreducible quasiprojective algebraic set is smooth. This follows from Theorem A.8.2. If X is of pure dimension k, then a general £ = fN~k meets X in deg X points. The general map associated to C = £ fl iJoo has degree degX. • N + 1 different projections may be used to separate points. Lemma A.10.6 Let X be an affine algebraic subset ofCN, all of whose irreducible components are of dimension < k. Fix a finite set S C CN. For a general linear

Algebraic Geometry

337

projection IT : CN -> C m with m> k + 1, K(X) = ir(y) for x e S and y e X U 5 implies that x — y. Proof. Since the lemma is vacuous if m — N, we can assume that m < JV — 1 and thus that k < N — 2. We can reduce by induction to the case when m = N - 1. Let Hoc := f1^-1 denote the hyperplane at infinity in FN. Let y be a point of S. If y ^ X, consider the map y{x) equal to the intersection of H^ with the line spanned by x and y. If y £ X (~) S, let (f>y : X \ {y} —> i ^ be the analogous map. The union T of the closures of the images of these maps as y runs over the set S is at most dimX. Since dimX = k < N — 2 < dimiJoo, we conclude that the projection corresponding to a general point of -ffoo \ T has the desired • properties. The following result is classical (p. 7 Mumford, 1995). A proof follows, e.g., from the construction given in § 15.5.4. Theorem A.10.7 Given a pure (N — 1)-dimensional affine set A C C ^ (respectively, protective set A C ¥N), there is a polynomial p(z) on CN (respectively, a homogeneous polynomial p(z) on VN) of degree deg A with V(p) — A. A is irreducible if and only if p(z) is irreducible in the sense that p(z) does not factor as a product of two polynomials both of strictly lower degree. Given a reduced affine algebraic set X, the following classical lemma lets us construct polynomials whose set of common zeros is the underlying set of X. Lemma A.10.8 Let X be an affine subset of CN, all of whose irreducible components are of dimension k < N. Given N + 1 generic projections i\i : CN —> Ck+1 with Qi the defining degX polynomial of TTJ(X) for i = 0 , . . . , iV; the set of common zeros of the polynomials qo(iTQ(x)),..., qN(nN{x)) is X. Proof. Choose a generic projection TTJV : C ^ —> C fc+1 and let qpj be the defining degX polynomial of n^(X). Then gjv(7Tjv(aO) vanishes on an (N — l)-dimensional set XJV containing X. Let S be a finite set consisting of one point from each irreducible component of X^ \X. Choose a generic projection TT/V-I : C ^ —> Ck+1. By Lemma A.10.6, TTJV-I(S) fl TTJV-I(X) = 0, and thus the set of common zeros minus X is of dimension at most N — 2. This Xjv-i of qN(^N{x)),qN^i(nN^i(x)) • step can be repeated, in an induction, to give the conclusion of the lemma.

A. 11

The Dual Variety

In classical projective geometry there is a simple but basic duality between points and hyperplanes. To make this precise, let P ^ denote the A^-dimensional projective

338

Numerical Solution of Systems of Polynomials Arising in Engineering and Science

space. A point is represented in homogeneous coordinates by an (TV + l)-tuple [zo,..., ZN\- A hyperplane is represented by a linear equation a^zo + • • • + OJVZJV = 0 with not all coefficients zero. Since multiplication of a linear defining equation of a hyperplane does not change the hyperplane, we see that there is a one-to-one correspondence of hyperplanes with points in a projective space represented in the homogeneous coordinates \ao,..., a/v]- This second projective space is referred to as the dual projective space FN*. Note the relationship is completely symmetric, i.e., P^**, the dual of the dual of FN, is just FN. The family of hyperplanes containing a P N ~ 2 C ¥N corresponds to a line in P^*. With such a duality, it is natural to try to extend it to subsets of projective space besides points and linear spaces. To see how this might be done, let C be an irreducible curve in P 2 . If C was smooth we could send x £ C to the point in P2* representing the line in P2 tangent to C at x. This curve C" is called the dual curve of C despite the fact that if C is a line then C is a point. If C is a singular curve we could define C as the closure of the image of the smooth points. For such a singular curve, the map C —• C is a rational mapping but not necessarily a function. This duality makes sense in general. Given an irreducible projective algebraic set I c P " , define the dual variety X' as the closure in PN* of the set consisting of hyperplanes which contain at least one tangent space of some smooth point of X. We can similarly define the dual of an algebraic set. There is a strong result about dual algebraic sets in complex projective space. Theorem A . l l . l

Let X be an irreducible subset of¥N. Then (XJ = X.

Proof. (Kleiman, 1986) is a good reference for this result and related material.

•

Note this result says that in the case when X is a curve in P 2 and not a line, the rational map X —> X' gives an isomorphism from a Zariski open set of X to a Zariski open set of X'. To see this note that the image of X is either a point or a curve. If it is a point then X" = X is a line. So we have that if X is not a line it has image a curve. The rational mapping X' —> X is a well-defined map on the smooth points of X'. Prom this we conclude that X - t l ' could not be r to one for an r > 1. We need a special consequence of this result. Corollary A.11.2 Let C be a pure dimension-one, not necessarily irreducible, algebraic subset o/P 2 . Assume that C has no irreducible components of degree one. Then C" = C. Further let x be a general point of any one of the components C of C with the tangent line £ to C at x. Then the defining equation of C given by Theorem A. 10.7 restricted to £ has x as a zero of multiplicity two with all other zeros of multiplicity one. Proof. Since C" = C for an irreducible curve and the degrees of the components of C are all of degree greater than one, we have from Theorem A.ll.l that the images of the components of C are distinct irreducible curves. Choosing a general point x

Algebraic Geometry

339

of a component D we get a general point of a component D' of C. This implies that any line £ tangent to a general point of a component D of C corresponds to a point of P2* not on any component of C other than D'. In particular £ must be transverse to C away from x. The condition that a neighborhood of x on C" goes isomorphically to a neighborhood of x on C is equivalent to the fact that x is a multiplicity-two zero of the restriction to £ of the defining equation of C. • A.12

A Monodromy Result

Let X be a pure fc-dimensional affine algebraic subset of CN and let Gr(m, N) denote the Grassmannian of P m s in FN. We close X up to get a pure fc-dimensional projective algebraic set X C PN. We consider the family of intersections £;v-fc H i for A;-dimensional linear spaces Lpi^k C fN. The set of pairs F := {(LN_k,x)

GGr(N-k,N) x X |x
is a projective algebraic set. This is completely analogous to the simpler construction in § A.7. We have the maps p : T —> Gr(N — k, N) and q : T —> X induced by the product projections on Gr(N — k, N) x X. Since a generic L^-k meets X transversely in a set of degX distinct points of X reg , we conclude from Corollary A.4.14 that there is a Zariski open set U c Gr(N - k, N) such that pp-i(u) '• P'1^) —> U is a finite covering. Fix a general point y € U, we have the monodromy action of the fundamental group ni(U,y) on the set p~l(y)- Statements for monodromy using slices of X follow immediately from the statements for monodromy using slices of X. Indeed, by shrinking U further it may be assumed that q(p~1(U)) C X, and so the lemmas and theorems we state hold equally for X and its closure X. Reflecting the bias in this book to regard polynomial systems as being defined on Euclidean space rather than projective space, we state the results for affine algebraic sets X in the rest of this subsection. Lemma A.12.1 If Xi is an irreducible component of X, then the above monodromy action acts transitively on the set Xi np~1(y). Proof. Note that q : J- —> X is a fiber bundle with the fibers isomorphic to the Grassmannian Gr(N — k, N). Thus the set q"1{Xi) is irreducible, and therefore the Zariski dense open subset p~l(U) D q^1(Xi) C q~l(Xi) is also irreducible. Since y is general, p~l{y) consists of smooth points of the irreducible and hence pathconnected manifold (p^1(f7) n q~1(Xi))reg. The monodromy action under a path connecting two distinct points of p~1(y) gives the transitivity. • We need a much stronger result. Choose a general affine linear subspace B :=

340

Numerical Solution of Systems of Polynomials Arising in Engineering and Science

£N-k+i c £N containing the (N -fc)-dimensionalaffine linear space corresponding to the basepoint y € Y. Let BQ denote the (N —fc)-dimensionallinear subspace of C* parallel to B. Though in practice it does not matter, we should theoretically choose the general B first and the general space corresponding to y afterwards. We let 7r : CN~k+1 ->C:= CN~k+1/B0 be the induced linear map. Let Ls := TT" 1 ^). Let V C U be the linear curve through y corresponding to the Ls. We have the following result from (§3 Sommese et al., 2002b). Theorem A.12.2 Let X = U^1Xi denote the decomposition of a pure kdimensional affine algebraic set X c C^ into irreducible components. We assume that k > 1. Let ir~l(y) = VJTi=1Fi, where Ft = ir~l(y) n Xt with n, y, and V as above. The image ofit\ (V, y) into the automorphism group of the set n'1(y) induced by the monodromy action of slices of X by the (N —fc)-dimensionallinear subspaces Ls c CN is r

0Sym(Fi), where Sym(F;) is the symmetric group of F^. Proof. First we may discard all degree one components since they do not effect the veracity of the theorem. Next we reduce to the case when k = 1. Since B is general, we know from part 3) of Theorem 13.2.1 that each X, is irreducible. The map -K may now be regarded as the linear map from CN to C with Ls of the form LQ + sv for a fixed vector v G CN with v £ LQ. By renaming if necessary, we may assume that X is one-dimensional. Next we take a general projection TT' : C^ —* C. The generic linear map II := (7r,7r') : CN —> C2 maps X generically one-to-one to its image by Theorem A.10.5. Let TTi denote the projection of C2 onto its ith factor. There is a Zariski open dense set V of C such that ?rf 1{V) nll(X) is smooth and m : Tr^l(V')r\Tl(X) -> V is a d := degX sheeted covering map. Since n = TT\ O LT, we may regard V as an open subset of V. Since every immersion g : S1 —> V' gives an immersion g : S1 —> V, it suffices to prove the result for V'. This reduces us to the case of a curve in C2 with V a family of lines parameterized by an open Zariski dense set of a line in the dual P2 to the P 2 containing C2. This case follows in two steps. First we prove the statement for the family U of all affine lines in C2. This follows using Corollary A. 11.2 and a modification of the proof of the classical statement when X is an irreducible curve, e.g., (page 111 Arbarello, Cornalba, Griffiths, & Harris, 1985). The proof foiVcU follows from a theorem (Theorem, §5.2. Part II Goresky & MacPherson, 1988) of Lefschetz type asserting that the homomorphism TT\(V, y) —> 7Ti(U,y) induced by the inclusion V C U is a surjection. • We refer the reader to (Sommese et al., 2002b) for a more detailed proof.

341

Algebraic Geometry

A. 13

Line Bundles and Vector Bundles

We have mentioned earlier that homogeneous functions are not functions on projective space, though they are functions on a related Euclidean space. One difficulty posed by this is that the usual statements for algebraic functions on affine algebraic sets are not literally true for homogeneous functions on projective space. If homogeneous functions on projective space were the only issue, we could state the results for polynomials with slight rewording for homogeneous functions. But, faced with a number of very useful generalizations of homogeneous functions, e.g., bihomogeneous and more generally multihomogeneous functions, this is not a viable approach. In this section we first introduce bihomogeneous and multihomogeneous polynomials, and then define line bundles and their sections. A.13.1

Bihomogeneity and

Multihomogeneity

Let X denote the product of two projective spaces, P m x P n . We can denote a point in this space by a (a + b + 2)-tuple [ZQ, ..., zm; Wo,..., wn] of points with neither Zi = 0 for all i nor Wj = 0 for all j , and with the equivalence relation [zQ>...,zm;wo,...,wn]

~ [Xz'o,...,

Xz'm; fiw0,...,

p,w'n}

for all 0 j^ A e C and 0 ^ /x € C A polynomial p(z, w) in the variables ZQ,.. . ,zm,Wo,... ,wn is said to be bihomogeneous of degree (a,b) if it is of the form Yl\i\=a \j\=bcuzIwJ• Note that since p(Xz, /j,w) = Xanbp(z,w), it follows that the set where p(z,w) = 0 is a well-defined subset of Fm x P™. Similarly, we can define multihomogeneous polynomials on P™1 x • • • x Pnfc. A. 13.2

Line Bundles and Their Sections

First, let's consider the case of C^. If we have a polynomial p(z) on CN, we can think of p(z) in terms of its graph ap :— {(z, A) e C^ x C j A = p(z)} . We say that CN x C is the trivial line bundle on CN and av is a section. In loose terms, a line bundle over X is a quasiprojective algebraic set which maps onto X with fibers identified with C in such a way that the vector space structure on C is preserved. Precisely, we can define line bundles on any quasiprojective algebraic set X. A line bundle L on X consists of the data (1) UQ, .. •, Ue, a covering of X by affine Zariski open sets Ui dense in X; (2) for each 0 < i < £, 0 < j < £, an algebraic function ptj defined and nowhere zero on Uij := Ui f] Uj with pijPji = 1 on Uitj and pa = 1 on Ui\ and (3) PijPjk = Pik on Ui n Uj n Uk for all 0 < i < I, 0 < j < I, 0 < k < £. Associated to a line bundle is a space generalizing the trivial bundle. The space, also called L by abuse of notation, is covered by open sets UiXC where for x € Uij we identify {x,At) G £7, x C with (x,Aj) 6 Uj x C if Aj = pij{x)Al. The cocycle

342

Numerical Solution of Systems of Polynomials Arising in Engineering and Science

condition pijPjk — Pik guarantees the identifications are well defined. There is a further natural, but involved, definition of when different covers and choices of pij lead to the "same" line bundle. Sections, which are basically like graphs of functions, are defined as a choice of algebraic functions at : Ui —> C with the property that

aj{x) = ai{x)pij{x) for x e Uld and all 0 < i < I, 0 < j < L An algebraic line bundle L on a quasiprojective algebraic set X is spanned by a vector space V of global sections of L if for each point x 6 X, there is at least one section s & V such that s(x) ^ 0. For example, letting [zo,zi] denote homogeneous coordinates on P 1 , we may cover P 1 with Uo :— P 1 \ V(zx) and Ux := P 1 \ V(z0). We have the coordinate z :— ZQ/ZI on UQ and w := 1/'z = Z\/ZQ on U\. We may form the line bundle Opi (d) by taking the data consisting of the function poi = l/zd on Uo fl U\. We may regard a homogeneous polynomial p(zo,z\) of degree d > 0 a s a section of Opi(d) by assigning ao(z) := p(z, 1) to Uo and
= p(l, 1/z) = z" d p(-s ; 1) = Po,io-o(^)-

Note that Opi (0) is the trivial bundle, and for d > 0 the bundles 0pi (rf) are spanned. There are no other sections of (Dpi (d) besides the ones just constructed using the homogeneous polynomials. On P ^ , the line bundles are not much more complicated than the ones just constructed for P 1 . They are in one-to-one correspondence with the integers d, with the line bundle corresponding to d being denoted Cpw(d). For d < 0 the only algebraic section of OFw(rf) is the 0-section, i.e., the choice of a cover [7; of FN and (Ti — 0 for all i. For d = 0 we have the trivial bundle, whose only sections are the constant functions, and for d > 0 the algebraic sections are again in one-to-one correspondence with the homogeneous polynomials of degree d. It turns out that up to equivalence that the only algebraic line bundle on CN is the trivial line bundle. Any algebraic line bundle L on an irreducible projective algebraic set X gives rise to a well-defined element C\{L) in the second integral cohomology group H2(X, Z) of X. This element c\(L) is called the first Chern class of L. If L has a not identically zero section s, then ci(L) is Poincare dual to the zero set Z of s. Let us assume we have line bundles L\,... ,LN on an irreducible projective algebraic set X of dimension N. If the line bundles are spanned by global sections, then given general sections Si of Li for i = 1 , . . . , N, it follows that the system siO) = 0 :

(A.13.6)

sN(z) = 0 has exactly (c\{L\) • •

-CI(LJV))

[X] isolated solutions and they are all nonsingular.

343

Algebraic Geometry

For example, if X = FN and Li = OpN(di), then the Sj are homogeneous polynomials of degree di, and we have the classical Bezout Theorem.

A. 13.3

Some Remarks on Vector Bundles

Replacing C in the definition of line bundles by C , and letting p^ be invertible r x r matrix-valued holomorphic functions we end up with the definition of a vector bundle of rank r. In terms of this definition, given line bundles L\,..., L^ on an irreducible projective algebraic set X of dimension N, and sections Sj of L, for i = 1,..., N it follows that the system given by Equation A.13.6 is equivalent to s = 0, where s = s1 © • • • © s^ is the section of the rank N vector bundle E := L\ © • • • © LN obtained by taking the direct sum of the N line bundles L^ The cohomology class c\{L) •••cN(L) e H2N{X,Z) is just the iVth Chern class Cff(E) of E, and the Bezout number for the system is just c^/(E)[X]. Such numbers are very often easy to compute. As a concrete example, we give the simplest nontrivial system on CN arising as a section of a rank N bundle on P w restricted to C^. For the bundle we take the tangent bundle Tpw of FN. The Bezout number for the system associated to a general section s of TpN is AT + 1. Written in terms of coordinates x i , . . . , x^ on CN the system becomes ' £i(x) -

Xleo(x)

'

:

=0

JN{X) -xNe0(x)_ where li{x) = a^o + auxi + • • • + dixx^ for generic choices of all the a^. By the theory of vector bundles it may be checked that this system has exactly N + 1 nonsingular isolated solutions.

A.13.4

Detecting Positive-Dimensional Components

The algebraic geometric structure that best captures what is meant by a polynomial system is that consisting of a vector bundle and one of its sections. For the sake of simplicity we have avoided line bundles and vector bundles in this book, but they are in the background and they lead to useful results, e.g., (Morgan et al., 1995) and (Morgan & Sommese, 1989). Here is one (Theorem 7 Morgan & Sommese, 1989). Theorem A. 13.1 (Morgan and Sommese) Let £ be a spanned rank N holomorphic vector bundle on an N-dimensional irreducible compact complex analytic space X. Assume that CN{£)[X\ ^ 0. Let a0 and o\ be two holomorphic sections of £. Then letting \ZQ,ZI] be homogeneous coordinates on P 1 , the solution set of 1 ZQCTQ + z\cj\ on P x X is connected.

344

Numerical Solution of Systems of Polynomials Arising in Engineering and Science

Before we start the proof of this theorem we would like to show what it says about down-to-earth polynomial systems. Let X := P^ 1 x • • • x ¥Nr be a product of projective spaces. Consider "systems of polynomials" a consisting of N := YH=i Ni equations where the ith equation has the nonnegative multidegrees d^i,... ,dktT with respect to the multihomogeneous structure. Letting TTJ be the product projection of X onto the jth factor P ^ , a is a section of the bundle

£:=0(0*;
(A13-7)

When the solutions of a system a are isolated and nonsingular, then the Nth Chern class of £ evaluated on X, i.e., CN{£)[X], equals the number of points in V(a). In the case of the £ of Equation A.13.7, c^(£)[X] equals the coefficient of tr 1 • • • t^r inIT^=1(M»,i + \-Uditr)Next let ai be a section of the £ in Equation A. 13.7 with isolated nonsingular solutions. Assume that we know the solutions of <j\. Now consider the "homotopy" CTJ := (1 — £)<7o + itai where ao is a second section, whose solution set we are computing. We know that for all but a finite number of 7 £ 5 1 , the solution set of <7t — 0 is isolated and nonsingular for t G (0,1]. By Theorem A.13.1, we know that the limits of V(at) as t —> 0 include points from every connected component of V(a0). Proof, (sketch of the proof of Theorem A.13.1) Letting X be a desingularization of X by Theorem A.4.1 and noting that sections from a Zariski open dense space of sections of £ are nowhere zero on a proper analytic subset of X, we conclude that we can assume that X is smooth without any loss of generality. Analogously to the arguments in § A.7, the universal space of solutions of sections of £ is a smooth connected projective bundle over X. Using the proof of item (3) • of Theorem 13.2.1, we have the connectedness. A. 14

Generic Behavior of Solutions of Polynomial Systems

Systems of polynomials that arise in engineering and science often depend on parameters. In this section, we take a general approach to polynomial systems with parameters, and discuss what we can say about the dependence of solution sets on the parameters. There are two questions we are interested in: (1) what properties hold for general values of the parameters, e.g., a well-defined number of isolated solutions; and (2) given some property for a system with a special value of the parameter, e.g., having an isolated solution, what can we conclude for general values of the parameters.

345

Algebraic Geometry

Since the proofs require material beyond the scope of this book, we refer to references for essential points. Our approach is the same as (Morgan & Sommese, 1989), though the focus there was mainly on isolated solutions of systems. Let / i ( z i , . . .,xN;qi,..

.,qM)

:

f(x;q):= _fn{xi,

• • • ,XN',Ql,

(A.14.8) • • • ,QM) .

be a system of polynomials of (x;q) G CN x C M . We regard this as a family of polynomial systems in the x variables with the g-variables as parameters. Though the algebraic system given in Equation A.14.8 is quite general, it is not general enough. We need to allow also the possibility that systems in the family are defined on any algebraic subset of
(A.14.9)

be the restriction to X x Y of an algebraic section of an algebraic rank n vector bundle £ on X x Y, where X is a Zariski open and dense subset of an iV-dimensional connected projective manifold X, and Y is an irreducible smooth quasiprojective algebraic set of dimension M. A special case of this would be the situation that X x Y is a smooth Zariski open set of an irreducible projective algebraic subset of some projective space and f(x; q) consists of the restriction of n homogeneous polynomials fi(x; q) to X x Y. Though we briefly discussed vector bundles in § A.13, we suggest strongly, the first-time reader proceed with X := CN, Y := C M , and f(x;q) = 0 in Equation A.14.8 satisfying the extra property that it is a set of n polynomials on CN+M. Let X denote the nonreduced solution set of f(x; q) = 0, and let Z := V(f(x; q)) denote the reduction of X. Let n : X —> Y be the map induced from the product projection X x Y —> Y {CN x C M —> C M if you are following in the simpler setup). Let Xo denote the union of irreducible components Z of Z such that TTZ is dominant and such that dim Z = M. T h e o r e m A.14.1 If n = N and if there is an isolated solution (x*;q*) of f(x;q*) = 0, then (x*;q*) £ XQ. Moreover there are arbitrarily small complex open sets U C X x Y that contain (x*; q*) and such that (1) (x*;q*) is the only solution of f(x; q*) = 0 in U D (X x {<7*})/ (2) f(x;ql) = 0 has only isolated solutions for q' G TT(W) and x G U fl (X x {q1}); and

346

Numerical Solution of Systems of Polynomials Arising in Engineering and Science

(3) the multiplicity of (x*;q*) as a solution of f(x;q*) = 0 equals the sum of the multiplicities of the isolated solutions of f(x; q1) = 0 for q' € ir(U) and x € Un(Xx{q'}). Proof. The first two statements are proven in Theorem A.4.17. Since the codimension of XQ is N and XQ is defined near (x*;q*) by N functions, we know that Xo is a local complete intersection near (x*;q*). Thus Xo has at worst Cohen-Macaulay singularities. Since Y is smooth, this implies that -Kx0 '• X$ —> C M is flat in a neighborhood of (x*;q*). Here we are using the nonreduced structure of XQ in the neighborhood of (x*;q*). Flatness yields this result, e.g., (Prop. 3.13 Fischer, 1976) and the corollary following that proposition. • Corollary A.14.2 Let f(x;q) be as in Equation A.14-9. Then there is a Zariski open set U
tions counting multiplicity is d := yjidj, where the sum is always finite and i=l

bounded by the product of the JV largest degrees (with respect to the x variables) of the equations making up f(x; q) = 0. We call d, the generic Bezout number or the generic root count of the system f(x; q) = 0. Theorem A. 14.1 is one large reason why we use square systems. The following example is typical of the case n > N. Example A.14.4

For a system of polynomials in (x; qit q2) € C x C2, take

For q\ — q§, the system has isolated solutions, but for q\ ^ q2., there are no solutions. Theorem A.14.5 Assume that M + JV > n and that there is an isolated solution (x*;q*) of f(x;q*) = 0 where f(x;q) is as in Equation A.14.9. There is a germ of an irreducible complex analytic set Q containing q* with dim Q > M — {n — N) such that for all points q' in arbitrarily small open sets U
Algebraic Geometry

347

obtain a system equivalent to f(x;q) = 0. Using Theorem 12.2.2 successively, we cut X'Q down to an affuie algebraic set with dimension > M - (n — N). Take a component Z of this set at (x*;q*). By Lemma A.4.16, there are arbitrarily small open sets V of q* on this component (in the complex topology) on which the restriction 7rgn7r-i(y) : ZPi-K~l(V) —> V is proper (in addition to being finite by construction), e.g., see (§3, Theorem 8(b) Gunning, 1970) for a discussion. By Theorem A.4.3 applied to map irzr\-ir-1{y)i w e a r e done. • Remark A.14.6 A similar statement to Theorem A.14.1 can be proved, when we are talking about k dimensional components in place of an isolated x*. In this case when M + N > n + k, we get a Q of dimension at least M + N — n — k. A.14.1

Generic Behavior of Solutions

As at the start of the section, let f(x;q) be as in Equation A.14.9 (or simply as in Equation A. 14.8). We let X denote the solution set of f(x;q) = 0 with the induced nonreduced structure, and TT : X —> Y the induced morphism. The easiest route to generic statements is to exploit the fact that the morphism IT : X —> Y is "generically flat." Before we do this, let us show some generic properties, just to give the flavor of how the arguments go. We will continually choose smaller Zariski open dense sets U CY, and by abuse of notation call them U. Lemma A.14.7 There is a Zariski open dense set U cY such that either TT"1 ([/) is empty or n^-i^ : 7r^1(t/) —> U maps every irreducible component of X surjectively onto Y. Proof. To see this note that there are finitely many irreducible components Z of X. The set TT(Z) is constructible by Theorem 12.5.6, and so either n(Z) is Y or a proper algebraic subset of Y. Setting U equal to the complement of the union of the proper algebraic sets arising in this way, we can assume TT(Z) is dense in U for every component of Xu, the solution set of f(x;q) over U. We know, by Lemma 12.5.8, that for such a Z there is a Zariski open dense set of Y contained in ir(Z). By taking the intersection of these sets, we get a Zariski open dense set U with the desired property. • Lemma A.14.8 There is a Zariski open dense set U C Y such that given any irreducible component Z of n~1(U), TT^-I^) : TT~1([7) —> U maps Z surjectively onto Y with every fiber of nz having dimension exactly dim Z — M. Proof The argument follows from Corollary A.4.7 combined with the same reasoning as Lemma A.14.7. • The same sort of arguments yield the following result.

348

Numerical Solution of Systems of Polynomials Arising in Engineering and Science

Lemma A. 14.9 There is a Zariski open dense set U C Y such that given any distinct irreducible components Z\ and Z2 ofn'1^), either Z\V\Zi — 0 or 7rff-i((/) : TT~1(U) —> U maps every irreducible component W of Z\ D Z 2 surjectively onto Y with every fiber W of irw having dimension exactly dim W — M Many results such as this are immediate consequences of the generic flatness theorem. The generic flatness theorem is a useful algebraic result of Grothendieck, e.g., (pg. 57 Mumford, 1966), which Frisch (Frisch, 1967) showed holds for holomorphic maps between complex analytic spaces. We are not going to define flatness, but it geometrically says "fibers change without discontinuity." Good places to read about flatness (and some of the results that justify such a statement) are (pg. 146-161 Fischer, 1976) and (Chapter III. 10 Mumford, 1999). The generic flatness theorem mentioned above says that there is a Zariski open set U C Y such that either 7r~1(C/) is empty or T I V - I ^ ) : TT~1(C/) —> U is a flat surjection. From here on we will assume that U is not empty, since the statements we show are all trivially true in that case.

The generic irreducible decomposition Is there a "generic irreducible decomposition?" The answer is a strong yes, but first we must understand what we mean by this. For a point y € Y, let Xy denote the solution set of f(x; y) = 0. Forgetting about multiplicity information, we have the irreducible decomposition dimZy /

\

(J M J Zy,it3.

Zy:=V(f(x;y))=

(A.14.10)

We would like there to be a Zariski open dense set U
n-\U), i.e., dim Zy /

Zv=

\

U (\J Zv,itk i=l

\keJi

.

(A.14.11)

/

Note we are using Lemma A. 14.8, which tells us that given any irreducible component ZUthk of ZJJ, dimZ[/,j;fc = M + d\mZUylyk,y = M + i, where ZUtitk,y = Zu,i,k n (X x {y}).

349

Algebraic Geometry

Theorem A.14.10 Let f(x;q) be as in Equation A.14-9. Then there is a Zariski open dense set U C Y such that for any y £ U and each Zu,i,k occurring in Equation A.14-11, it follows that Zy^fcClTr—1(y) is a union of the irreducible components Zy,i,j °f Zy occurring in Equation A. 14-10. Moreover, for each of the i,k, all fibers of Zjj,i^k under n have the same number of components. Proof. Assume that it is not true, for the U selected in Lemmas A. 14.7, A. 14.8, and A.14.9, that Zu,i,k H Tr~1(y) is a union of the irreducible components 2y,i,j of Zy. Then one of the components Zy^j of Zy must contain one of the components of Zu^^k H ir~l{y). Moreover one of the components Zuytk' of Z\j must contain Zyjj. Thus we get that Z[/,i',fc' H •Zf/.i.fc contains a component W with fiber under 7T of dimension i. But this means W is dense in Zu,i,k, which gives the absurdity that Zutifk C Zuyk'By Theorem A.4.20, we may shrink U to a smaller dense Zariski open set U, so that each Zu,%,k contains a smooth Zariski open set W such that for all y e U, W Pi 7r~1(y) is dense in 7r^1(y); and IT : W —» U is of maximal rank with all fibers • having the same number of irreducible components. A.14.2

Analytic Parameter Spaces

It is a natural question to ask whether the results in this section are true when the parameters do not vary algebraically but only vary holomorphically. The short answer is "yes, with certain minor modifications." Because it is useful to allow complex analytic parameters, we explain what we mean by this and moreover state the generalization of the above results with the changes needed to prove them. In this one subsection, Zariski topology refers to the Zariski topology using zero sets of sets of homomorphic functions. The simplest case is a system '

fi(xi,...,xN;qi,...,qM)~

f(x;q):=

(A.14.12)

: Jn(xi,-

•• ,xN;qi,.

..,qM).

of holomorphic functions of (x; q) £ CN x C M , that are polynomial in the x variables. We regard this as a family of polynomial systems with the q-variables as parameters, there is a positive integer di such that i.e., for each i — l,...,n,

fi(x;q)= ] T aI(q)xI, \i\
where each ai(q) is holomorphic on all of C M . The situation analogous to Equation A. 14.9 is a system f(x;q),

(A.14.13)

350

Numerical Solution of Systems of Polynomials Arising in Engineering and Science

which is the restriction to X x Y of a holomorphic section of a holomorphic rank n vector bundle £ on X x Y, where X is a smooth and dense Zariski open subset of an irreducible projective algebraic set X of dimension N, and Y is a connected complex manifold of dimension M. We allow the possibility that X — X. In the case of Equation A.14.12, X = P^, and £ = FN and £ = OPN(di)

® • • •®

O¥N(dn),

and f(x;q) = fi(x;q)(B- • -®fn(x;q). As before, the first-time reader should assume that X := CN, Y := C M , and f(x; q) = 0 is as in Equation A.14.12. As above we let n : V(f) —> Y denote the holomorphic mapping induced by the product projection X x Y —» Y. We let n : V(f) —> Y denote the holomorphic mapping induced by the product projection X x Y —> Y. If Z is an irreducible component of V(/), then by Theorem A.4.3, W (Z) is a complex analytic subspace of Y. Since n {Z\Z) is a proper complex analytic subspace of n (Z), we conclude that U :— 7f (Z) \ W [Z \ Z) c n(Z) is a Zariski open dense subset of TT(Z). This plays the role of Lemma 12.5.8. We will continue to replace U by Zariski open dense subsets of U as needed, and call them by the name U. This implies that each irreducible component of 7T~1(C/) maps surjectively on U. We state only the analogues of Theorem A.14.1 and Corollary A.14.2. Theorem A.14.11 If n = N and if there is an isolated solution (x*;q*) of f(x;q*) = 0, then (x*;q*) € XQ. Moreover there are arbitrarily small open sets U C X xY that contain (x*; q*) and such that (1) (x*;q*) is the only solution of f(x;q*) = 0 in U n (X x {q*}); (2) f(x; q') = 0 has only isolated solutions for q' € TT(U) and x 6 U ("1 (X x {9'}); and (3) the multiplicity of (x*;q*) as a solution of f(x;q*) = 0 equals the sum of the multiplicities of the isolated solutions of f(x; q') — 0 for q' e TT(W) and x G Un(Xx{q'}). Proof. The argument is the same as that for Theorem A.14.1.

O

When working with complex analytic spaces it is useful to define an analytic Zariski open set to be a subset U C X of an irreducible complex analytic space of the form X \Y where Y is a complex analytic subspace of X. All the usual notions, e.g., probability-one and generic point, carry over with no change. We would call the Zariski open sets we have dealt with up to now, algebraic Zariski open sets, if we needed to deal in any significant way with both sorts of Zariski open sets. Corollary A.14.12 Let f(x;q) be as in Equation A. 14-13. Then there is an analytic Zariski open set U C C M such that for q € U the system f(x; q) = 0 has di

351

Algebraic Geometry

isolated solutions (not counting multiplicity) of multiplicity i where di is an integer independent of q &U. Remark A.14.13

Thus, as in the purely algebraic case, the generic number of oo

isolated solutions counting multiplicity is d := ~S^idi, where the sum is always i=\

finite and bounded by the product of the N largest degrees (with respect to the x variables) of the equations making up f(x; q) — 0. We, as in the purely algebraic case, call d, the generic Bezout number or the generic root count of the system f{x;q) = 0. Corollary A. 14.12 holds with X singular.

Appendix B

Software for Polynomial Continuation

There is much to be said for the motto "learn by doing," and in our case, this means solving polynomial systems with numerical continuation. Even though this book offers substantially all the information one would need to write a solver from scratch, that is rather far beyond the level of commitment most readers will muster. To provide an easy entry to the area, we provide a suite of m-file routines called HOMLAB for performing polynomial continuation in the Matlab environment. After gaining experience with HOMLAB, one may wish to download one of several freely available software packages for polynomial continuation. These may offer speed advantages and advanced options, such as polytope methods, not available in HOMLAB. Some of these have been adapted to run on multi-processor machines for large computations. A partial listing of packages available as of the writing of this book is as follows. • HOMLAB runs in the Matlab environment and implements general linear product homotopy and parameter homotopy. See Appendix C. • HOMPACK, H0MPACK90, POLSYS_PLP are a sequence of increasingly sophisticated continuation algorithms, written in Fortran. The "PLP" in POLSYS_PLP stands for Partitioned Linear Products, a special case of the general linear products discussed in § 8.4.3. This code finds only isolated solutions for square systems (same number of equations as variables). • PHoM is a C++ code that implements polyhedral homotopies (see § 8.5). This package finds isolated solutions for square systems. • PHCpack implements a variety of homotopies in a menu-driven interface that includes all the structures discussed in Chapter 8, except polynomial products. In addition to isolated roots, the algorithms from Part III of this book for handling positive dimensional solutions, nonsquare systems, etc., are implemented. This package is written by our collaborator, J. Verschelde, and it has been the experimental platform for validation of these algorithms. Both executables and Ada source code are available. • Algorithms for mixed volume computations can be found on T.Y. Li's webpage. This is the most difficult phase of a polyhedral homotopy, (§ 8.5). 353

Appendix C

HomLab User's Guide

a suite of scripts and functions for the Matlab environment, is designed as an easy entry into the use of polynomial continuation and, for the experienced user, as a platform for experimental development of new methods. Many of the exercises of this book assume the availability of HOMLAB and special routines using HOMLAB functions are provided for some exercises. The use of a routine for a particular exercise is described in the exercise statement itself, while the general structure and use of HOMLAB is documented below. The best way to learn HOMLAB is simply to work the exercises in the order they appear in this book. These progress from the simple application of the core path-tracking routine to successively more sophisticated homotopies that use it. Help describing the usage of individual routines, say, endgamer. m, is available by typing "help endgamer" at the Matlab prompt. The main text of this book is the reference for the methodologies used and the help facility just mentioned is the reference for individual routines. However, to help the user in getting started quickly, we provide this user's guide. We assume the user has at least a minimal acquaintance with Matlab; in particular, the user must know how to write and execute simple scripts and functions. A script is a sequence of Matlab commands recorded in a file, say "myscript.m," which are executed by typing » myscript at the Matlab prompt, here indicated as " » . " (Scripts can also be called within other scripts or functions.) A function is a file, say "myfunc.m," which starts with a declaration line something like HOMLAB,

function

[out1,out2]=myfunc(inl,in2,in3)

followed by lines of Matlab code that compute the two outputs, outl,out2 from the three inputs inl,in2,in3. This function might be called as [a,b]=myfunc(0.1,[1 3] ,x) where x is an existing variable in the workspace. For more on using Matlab, please see the Matlab documentation. 355

354

Numerical Solution of Systems of Polynomials Arising in Engineering and Science

• BERTINI is a C code soon to be available on A. Sommese's webpage. An effort of D. Bates, C. Monico, A. Sommese, and C. Wampler, led by A. Sommese, BERTINI features a high-level interface for parameter homotopies (including automatic differentiation) and multiple-precision routines that can adjust precision on the fly. As URL's are often subject to change, we suggest that the packages be located by use of a search engine.

356

C.I C.I.I

Numerical Solution of Systems of Polynomials Arising in Engineering and Science

Preliminaries "As is" Clause

HOMLAB is distributed free of charge on an "as is" basis. Its intended usage is educational, so that the user may gain a greater understanding of the use of numerical homotopy continuation for solving systems of polynomial equations. Any other use is strictly the user's responsibility.

C.I.2

License Fee

There is no license fee for HOMLAB. In lieu of this, we hereby request each user to buy a copy of this book. C.I.3

Citation and

Attribution

The use of HOMLAB for research purposes, either in its original form or as modified by the user, is highly encouraged, subject only to professional ethical conduct, as follows. In publications based on results obtained using HOMLAB or its successors, the use of HOMLAB should be acknowledged and this book should be cited. The author of the code is Charles Wampler. Any redistribution of HOMLAB in unaltered form must retain the same name and acknowledge the author. Any distribution of derived codes that extend or modify HOMLAB should acknowledge the original source and authorship. In addition, the differences from the original should be clearly documented and attributed to the new author. These conditions extend to users of the derived codes. C.I.4

Compatibility and Modifications

HOMLAB is a suite of Matlab routines. Version HOMLABI.O has been restricted to the conventions of Matlab v.4.0 to provide compatibility with both old and new Matlab installations. (Even the file names have been restricted to eight characters for compatibility with old operating systems.) The exception to this rule is that routines based on Part III of this book for generating witness point supersets use cell arrays to store sets for different dimensions. Users who advance to that level will need a more recent version of Matlab, or else they must modify the code. All routines have all been verified to run under Matlab v.6.5. By avoiding advanced features of newer versions of Matlab (except as just noted), we hope the package will be easier to translate to run in other environments, in case some readers lack access to Matlab. In particular, Octave and SciLab are both freely available packages that implement a large subset of Matlab functions, so they are good candidates for substitute environments. Anyone who successfully

HomLab User's Guide

357

ports HOMLAB to one of these, or similar, environments is requested to notify the authors and to make the ported version freely available. Citation of HOMLAB and this book are required, and any differences in functionality must be documented. The authors are not bound to fix bugs in the current version or to upgrade HOMLAB for compatibility of any future release of the Matlab product. However, user comments and bug reports are welcome, so that, at our discretion, we can maintain and possibly improve the educational value of the package. Please see the HOMLAB webpage for instructions on how to submit a comment or bug report. The exercises for this book have been written under Matlab v.6.5. Some of these use features not available in previous releases, namely function pointers and function files that include subfunctions in the same file. This should be more convenient for those with an up-to-date release of Matlab; those with old versions will, we hope, have little trouble revising the source code to run in their environment. C.I.5

Installation

As a suite of m-files, HOMLAB becomes functional by simply adding the folder containing the routines to Matlab's search path. The folder for the current release, HOMLABI.O, is HomLablO. Let's say that you have copied this folder onto your machine with the full path name of c:\mypath\HomLablO, where "mypath" could be any path in the file structure of your machine. There are three basic options for adding HOMLAB to the Matlab path: • In Matlab (v.6.5 and above), use "File -> Set Path" on the Matlab menu bar to launch a dialog box for setting the path and use it to add c: \mypath\HomLablO and its subfolders to the top of the search path. The change becomes effective immediately in the current session, while the "Save" button in the dialog box records it for future sessions. • At the Matlab prompt, use the command » addpath c:\mypath\HomLablO HOMLAB will then be available for the current session only. Similarly, add the subfolders of HomLablO to the path. • Create a file called startup.m in a directory already on Matlab's search path and put the appropriate addpath commands there. HOMLAB will then be available for all future sessions.

Any one of these three options is sufficient. See the Matlab help facility to obtain more detailed instructions on modifying the search path. To test if the installation is successful, type » simpltst at the Matlab prompt. If all is well, the session should look something like:

358

Numerical Solution of Systems of Polynomials Arising in Engineering and Science » simpltst Number of s t a r t points = 2 elapsecLtime = 0 Path 1 elapsed_time = 1.4100e-001 Path 2 elapsed_time = 3.1300e-001 The solutions are: 1.0000e+000 -2.2204e-016i -1.0000e+000 -1.1102e-016i 1.0000e+000 -1.6653e-016i -1.0000e+000 -1.6653e-016i 1.0000e+000 1.0000e+000 +5.5511e-017i »

The times will vary according to your machine and the tiny values of the imaginary parts of the answers will typically change with each run. This test solves the simple system x2 - 1 = 0,

xy-l

= 0,

in the homogenized form x2 - w2 = 0,

xy — w2 = 0,

using a two-path homotopy based on the linear-product formulation /i G (x,l) , / 2 6 (x,l) x (y, 1). Accordingly, the answers should be (x,y,w) = (1,1,1) and (—1, —1,1), as above. More information on interpreting the results is given below. C.I.6

About Scripts

In HOMLAB, the high-level functions are written not as true functions, which hide their internal variables from the workspace, but as scripts, which are a sequence of commands that run directly in the top level workspace. One advantage of this is that a Matlab save command can save all of the data necessary to execute an exact re-run, including all random constants used in denning a start system, and so on. A negative consequence is that all such data is in the workspace until the user clears it. If one wishes to avoid this, one can write a function to call the HOMLAB script and pass out only the desired results. C.2

Overview of HOMLAB

HOMLAB is a collection of compatible routines for defining and executing homotopy algorithms. The workhorse routine is endgamer.m which tracks solution paths for a homotopy h(x, t) = 0 from a list of startpoint solutions of h(x, 1) = 0 to their

HomLab User's Guide

359

endpoints satisfying h(x, 0) = 0. Specifically, endgamer has the usage [xsoln,stats,xendgame]=endgamer(startpoint,hfun) which is more completely documented in § C.7 below. Briefly, the inputs are startpoint, a matrix with one startpoint solution of the homotopy in each column, and hf un, a string name of the homotopy function. The matrix xsoln lists the endpoints of the solution paths in columnwise fashion. As its name suggests, endgamer applies an endgame to get better estimates of the endpoints for paths which approach singularities as t —> 0. Specifically, it uses the power-series endgame described in § 10.3.3. Usage of HOMLAB mainly comes down to specifying a homotopy and finding its start points. This can be done by writing one's own m-files or by making use of utilities and drivers in HOMLAB. The main alternatives are as follows. Linear Products This option includes total degree homotopies (§ 8.4.1), multihomogeneous homotopies (§ 8.4.2), and general linear-product homotopies (§ 8.4.3). The user must specify a target function f(x), its derivative fx{x), and the linear product structure. Automatic differentiation is available if the function is specified in fully-expanded form (see § C.3.1). Driver routine lpdsolve does everything else to construct and solve a homotopy of the form h(x,t) = ytg(x) + (l-t)f(x) = 0. That is, lpdsolve constructs a compatible start system g(x), solves it, and calls endgamer to get the final answers. See § C.4 for details. Parameter Homotopy This option handles general homotopies of the type described in Chapter 7. The user gives a parameterized function f{x,q), its derivatives fx{x,q) and fq(x,q), starting and ending parameter values q\ and go, and startpoint solutions for f(x,qi) = 0. (Usually, the start points are found with a single linear-product run, then parameter homotopy is used for all subsequent runs for various target values of go-) A means is provided for selecting a linear path from q\ to qo; otherwise, the user must write an m-file to implement a nonlinear path. When the linear path is selected, the homotopy is of the form h(x,t)=f{x)tq1 + (l-t)qo)=O. Secant Homotopy This option solves homotopies of the form h(x, t) = -ytf(x, qi) + (1 - t)f(x, q0) = 0. The user supplies the function f(x,q), the derivative fx(x,q), and startpoint solutions to f(x,qi) = 0. (Again, as in the parameter continuation case, one usually solves f(x,q±) = 0 with a single linear-product homotopy, reusing the same q\ for subsequent homotopies to various target values of qo.) It is the

360

Numerical Solution of Systems of Polynomials Arising in Engineering and Science

user's responsibility to verify that the homotopy is valid in the sense that the linear combination of two functions from the family is still in the same family. This is the least used option, but as shown in Exercise 7.6, it is sometimes handy. The usual process involves creating two m-files: • a function defining the system to be solved • a script that sets up the required data structures before calling endgamer to get the solutions. The exception is if one chooses to specify the function in "tableau" form (§ C.3.1), in which case the function evaluation routine is already provided. Facilities are available to make the whole process easy in the most common formulations, while the more advanced user can directly access the basic routines to implement specialized homotopies. In the next few sections, we illustrate each of the main options by examining example scripts and functions. C.3

Defining the System to Solve

HOMLAB allows a target system to be denned in one of two ways: as a fully expanded sum of terms or as a black box function. The fully expanded form is convenient for simple, sparse polynomials, while user-written functions are more flexible and often more efficient. Parameterized families of systems must always be written as a userdefined function, but the underlying functions that HOMLAB uses for evaluating fully expanded functions can be employed in a user-defined function as well.

C.3.1

Fully-Expanded

Polynomials

The simplest option for specifying a target polynomial is to list out its monomials and coefficients. As discussed in § 1.2, this is not generally an efficient formulation: for complicated problems, straight-line programs can require much less computation. However, for simple systems, the fully expanded form is quite reasonable. HOMLAB supports a "tableau" style definition for systems, wherein the entire polynomial system is laid out in a single numerical matrix with n + 1 columns for an n-variable problem. The convention is that each row is a term of a polynomial, with the coefficient in the first column and the exponents d\,..., dn for monomial xf1 • • • xff in the remaining columns. The end of a polynomial is marked by a row with a negative exponent for x\. A complete script for solving the system x2 - x - 2 = 0,

xy - 1 = 0,

using a tableau definition of the system and a total-degree homotopy is as follows.

HomLab User's Guide

361

% Define the target system in tableau form eop = [0 -1 0 ] ; % marker for end of polynomial tableau = [ 12 0 -110 -2 0 0 eop 111 -10 0 eop ]; '/, decode tableau and solve with total-degree homotopy totdtab 7, display the dehomogenized solutions dispOThe solutions a r e : ' ) ; disp(dehomog(xsoln, le-8)) The total degree is 2 • 2 = 4, and there are two finite solutions [x, y, w] = [2,0.5,1], and [—1,-1,1] and a double root at infinity of [0,1,0]. More information on the solution script totdtab is given in § C.4. A related script, lpdtab, can be used to solve tableau-style systems using multihomogeneous or general linear-product homotopies. Using this capability, a two-path version of the above would be as follows. °/0 Define the target system in tableau form eop = [ 0 - 1 0 ] ; '/, marker for end of polynomial tableau = [ 12 0 -110 -2 0 0 eop 111 -10 0 eop ]; % define a linear-product decomposition xw=[l 0 1]; yw=[0 1 1] ; LPDstruct=[ xw; xw; xw; yw; ] ; HomStruct= [] ; V, default t o 1-homogeneous % decode tableau and solve with linear-product homotopy lpdtab '/, display the dehomogenized solutions disp('The solutions are:'); disp(dehomog(xsoln,le-8))

362

Numerical Solution of Systems of Polynomials Arising in Engineering and Science

See § C.4 for details on specifying linear-product structures and see the help for lpdtab for details on how this script automatically homogenizes the tableau-style polynomial using the information in HomStruct. These scripts parse the tableau matrix into a more basic form and pass the results to a built-in function, ftabcall, which in turn calls function ftabsys. The latter can be used directly if one wishes to write a straight-line function (see next section) while specifying some subset of the polynomials in tableau form. For details, see use the help facility or look at the source code for ftabsys.

C.3.2

Straight-Line

Functions

For more complicated functions, it is usually more efficient to express them in straight-line form. There are two contexts in HOMLAB where a user might define such a function: • to define a target polynomial for solution in a linear-product homotopy, or • to define a parameterized family of functions for a coefficient-parameter homotopy. In the first case, the function must have the form

function

[f,fx]=function_name(x)

where x is the input variable list, f is the output function value, and f x is the output Jacobian matrix of partial derivatives df/dx. The function must be homogeneous, possibly multihomogeneous. The careful reader might raise an objection that a homogeneous polynomial on P n is not truly a function (see § 12.3), but for our purposes we consider it as a function on C" +1 , which it certainly is. The script which defines the linear-product homotopy appends random linear equations to effect the projective transformation of § 3.7, one such equation for each projective subspace when working multihomogeneously. To repeat the example above of the system

x2 - x - 2 = 0,

xy-1-0,

in straight-line form, one could define the function

HomLab User's Guide

363

function [f,fz]=simplefcn(z) % Straight-line function for "/. x"2-x-2=0, xy-l=0 x=z(l); y=z(2); w=z(3); f = [ x~2-x*w-2*w~2 x*y-w*2 ]; fz = [ 2*x-w, 0, -x-4*w y, x, -2*w ]; This is not really useful for such a simple example, but it can be significant for more complicated systems. Notice the use of the homogeneous coordinate w. Similarly, parameterized functions must also be homogeneous in the unknowns, but not necessarily in the parameters. The Matlab format for a parameterized family of systems is simply function

[f,fx,fp]=function_name(x,p)

where the third output, f p, is the matrix of derivatives df /dp. Here is a complete specification for the intersection of two circles, where a subfunction for a single circle is used twice. function

[f,fx,fp]=twocircle(x,p)

% Straight-line function for intersection of two circles f=zeros(2,l); fx=zeros(2,3); fp=zeros(2,6); [f(l),fx(l,:),fp(l,l:3)]=onecircle(x,p(l:3)); [f(2),fx(2):),fp(2)4:6)]=onecircle(x,p(4:6)); % function [f,fx,fp]=onecircle(z,p)

% straight-line function for one circle °/, parameters are [cx;cy;r~2] where (cx,cy)=center, r=radius x=z(l); y=z(2); w=z(3); cx=p(l); cy=p(2); rsq=p(3); a=x-cx*w; b=y-cy*w; f = 0.5*( a~2 + b~2 - rsq*w~2); fx = [ a , b, -cx*a-cy*b-rsq*w]; fp = [ -w*a, -w*b, -0.5*w~2 ] ; The most error-prone part of writing a straight-line program is in generating the derivatives. To aid in debugging, utilities are provided to numerically check the coding of the function. See § C.3.4.

364

C.3.3

Numerical Solution of Systems of Polynomials Arising in Engineering and Science

Homogenization

It is highly recommended that all systems presented to HOMLAB be denned in homogeneous form. This is the user's responsibility, with the exception that tableaustyle systems will be homogenized automatically. Homogenization is recommended because path endpoints approaching infinity are very common, and the projective transformation available after homogenization keeps both the magnitudes of the coordinates and the arclengths of the homotopy paths finite. If one wishes to compute homotopy paths without homogenization, the path-tracker routines endgame and tracker will still work, but they do not include any special stopping conditions for diverging solutions, which may therefore take up inordinate computation time. (Such paths can never make it to t — 0, so eventually they must fail on a too small step size condition or on the limit on the number of steps.) The choices of a linear product structure and a multihomogenization are independent. For example, if a system is bilinear, one can reflect this in the linearproduct structure while one-homogenizing the system. The one-homogeneous start system will have solutions at infinity, but HOMLAB will ignore these. If the system is two-homogenized instead, respecting the bilinear structure, the linear-product start system has no solutions at infinity. This is a bit cleaner mathematically, but in practical terms, both formulations have the same number of solution paths to follow. To be clear, consider again the example x2 ~ x - 2 = 0,

xy - 1 = 0.

In a one-homogeneous treatment using coordinates [x, y, w] £ P 2 , we have the equations x2 - xw - 2w2 = 0 ,

xy -w2 = 0,

and we must specify a compatible homogeneous structure: HomStruct=[l 1 1]; which directs HOMLAB to append a inhomogeneous linear equation ax + by+cw = 1 for some random, complex {o, b, c}, thereby choosing a random patch on P 2 . (For a discussion of projective spaces, see Chapter 3.) To get a two-path homotopy, we specify the linear-product structure LPDstruct=[l 0 1 ; 1 0 1 ;

1 0 1; O i l ] ;

that is, /i e (x,w) x (x,w) and / 2 G (x,w) (y,w). This start system has a double root at infinity of [x,y,w] = [0,1,0], but HOMLAB will ignore it. The two-homogeneous treatment of the same system using coordinates {[x, u], [y,v]} e P 1 x P 1 is x2 — xu — u2 = 0,

xy — uv = 0.

365

HomLab User's Guide

The compatible HomStruct is, assuming the coordinates are ordered as HomStruct=[l 0 1 0 ; which directs

HOMLAB

(x,y,u,v),

0 1 0 1];

to append two linear equations

ax + Qy + bu + Ov = 1,

Ox + cy + Ou + dv = 1,

for random, complex values of {a, b, c, d}. This picks a random patch on each of the two P 1 subspaces. Now, the two-path linear-product decomposition is LPDstruct=[1 0 1 0 ; 1 0 1 0 ;

1010;

010

1];

See § C.8 for a description of the dehomog function to dehomogenize a solution point.

C.3.4

Function Utilities and Checking

With a few sample scripts in hand, it is easy to set up and run any of the various kinds of homotopies once the function and its derivatives are available. To make the definition of these easier, some utilities are available. • Function f tableau accepts a list of coefficients and a matrix of exponents to define the terms of a polynomial. It then provides both the function and derivative evaluations. It works only for a single function / : C n —> C, so a wrapper function ftabsys is provided to call ftableau multiple times for a system of such functions. • Utility scalepol is available for scaling a system for f tabsys, as is sometimes necessary. For example, see the chemical system of § 9.2. Since Matlab is a numerical package, there has been no attempt to automate differentiation and homogenization except for the simple case of fully expanded polynomials via the ftableau function. Otherwise, this onerous task falls to the user. Symbolic packages can be employed to preprocess functions in this way and then copy the results into an m-file function. The most error-prone step in defining a straight-line program for a function is in giving formulae for the partial derivatives. A helpful way of checking these is to compare the computed derivatives with a computation based on numerical differentiation. The function must also be homogenized, which can also be checked numerically. The following checking utilities are provided for these purposes.

366

Numerical Solution of Systems of Polynomials Arising in Engineering and Science

function [fxerr]=chekffun(fname,nx,epsO) —> checks derivatives of target functions [f,fx]=myfunc(x) function [fxerr,fperr]=chekpfun(fname,nx,np,epsO) —> checks derivatives for parameterized functions [f,fx,fp]=myfunc(x,p) function [homerr]=chekhmog(fname,HomStruct,mdeg) —> Checks multihomogenization of function [f]=myfunc(x) User provides homogeneous structure and multidegree matrix function [homerr]=chekhmog(fname,HomStruct,deg,lpd) —> Checks multihomogenization of function [f]=myfunc(x) User provides homogeneous structure, t o t a l degrees, and linear product structure. Code computes multidegree matrix from these. In each case, the checking is done at a random point x £ Cnx. The functions provide a numerical comparison and also use the Matlab spy function to graphically show which elements are suspicious, having an error greater than espO. If epsO is omitted from the call, it defaults to 10~6. Note that high-level scripts define a global FFUN, which can be used for fname.

C.4

Linear Product Homotopies

One of the two main options in HOMLAB is the linear-product homotopy, implemented in the script lpdsolve. With appropriate settings, this script performs the equivalent of a total-degree homotopy, a multihomogeneous homotopy, or a general linear-product homotopy. For total-degree and multihomogeneous homotopies and a tableau-style function definition, the higher-level scripts totdtab and mhomtab automatically perform some preliminary processing steps for you before initiating lpdsolve. Let's first see all the set-up information required by lpdsolve by studying a script to solve a simple system specified in straight-line form. Such a function is treated as a "black box," so the user must supply all the structural information necessary to specify the linear-product formulation. To this end, consider the straight-line function called simplf en in § C.3 above, that implements the system x2 - x - 2 = 0,

xy - 1 = 0.

It has two variables (before homogenization), and each equation is quadratic. A complete script to solve this with a total-degree homotopy, with four paths, is as follows.

HomLab User's Guide

367

% script to solve "simplfcn" by t o t a l degree using lpdsolve global nvar degrees FFUN nvar=2; degrees=[2 2 ] ; FFUN='simplfcn'; LPDstruct=ones(sum(degrees),nvar+l); % t o t a l degree structure lpdsolve dispOThe solutions a r e : ' ) ; disp(dehomog(xsoln, ie-8)) The meaning of the global variables is self-explanatory. The degrees of the polynomials as listed in degrees must be in the same order as they appear in the evaluation function, although in this example they are the same. The item that needs explanation is LPDstruct, which defines the linear-product structure to be used. Each row in LPDstruct represents one linear factor, and there must be degrees (i) factors for the ith equation, for a total of sum (degrees) rows in all. The columns of LPDstruct correspond to the variables in x as it is passed into simplfcn(x). Typically, the final column is the homogeneous coordinate, but this is at the discretion of the user when writing the function. A nonzero entry in element (i,j) of LPDstruct indicates that variable j appears in the ith linear factor, and factors are assigned to equations in accordance with the entries in degrees. For a total-degree homotopy, LPDstruct is just a full matrix of ones. We can run the same problem using only two paths just by changing LPDstruct. In this case, a two-path homotopy is obtained with the following script. '/„ script to solve "simplfcn" with two paths using lpdsolve global nvar degrees FFUN nvar=2; degrees=[2 2]; FFUN='simplfcn'; xw= [ 1 0 1]; yw=[0 1 l ] ; LPDstruct=[ xw; xw; xw; yw; ];

HomStruct=[]; % default to 1-homogeneous lpdsolve disp('The solutions a r e : ' ) ; disp(dehomog(xsoln,le-8)) This is exactly the script simpltst that is suggested as an installation check in § C.1.5. The script above uses only two paths even though simplfcn is only onehomogenized. That is, the homotopy runs in the projective space P 2 . The choice of linear product structure guarantees that the start system, the target system, and consequently the whole homotopy, have a double root at infinity that we choose not to track. If we two-homogenize the equations instead, then this double root

368

Numerical Solution of Systems of Polynomials Arising in Engineering and Science

does not exist at all. It makes no difference in this case, but in cases where some endpoints arrive at infinity only at the target (as t —• 0), multihomogenization can change their representation, and sometimes this can make them numerically more tame. For instance, a singular double root at infinity might break into two distinct nonsingular roots at infinity. To show how HomStruct is used to set up a homotopy in a cross product of projective spaces, let's rework the running example. First, we need a two-homogenized version of the equations. function [f,fz]=simplefcn2(z) % Straight-line function for '/. x~2-x-2=0, xy-l=0 % Two-homogeneous version on [x,u] \times [y,v] x=z(l); y=z(2); u=z(3); v=z(4); f = [ x~2-x*u-2*u~2 x*y-u*v ]; fz = [ 2*x-u, 0, -x-4*u, 0 y. x, -v, -u ];

The script to solve this as a two-homogeneous system follows. 5i script to solve "simplfcn2" two-homogeneously global nvar degrees FFUN nvar=2; degrees=[2 2]; FFUN='simplfcn'; xu=[l 0 1 0 ] ; yv=[0 1 0 1 ] ; LPDstruct=[ xu; xu; xu; yv; ]; HomStruct=[ xu ];

lpdsolve dispOThe solutions a r e : ' ) ; disp(dehomog(xsoln,le-8)) In general, the groupings in the linear factors specified in LPDstruct do not have to be copies of those in HomStruct, as indeed, they are different in the two-path,

369

HomLab User's Guide

one-homogeneous example above. The given LPDstruct and HomStruct must be compatible with the target function. In tableau style functions, the automated scripts will ensure compatibility, but straight-line functions are treated as black boxes, so HOMLAB has no way of checking compatibility. It is the user's responsibility to ensure compatibility. In the case of errors, the resulting behavior will be erratic, sometimes signalled by path-tracking failures, but not necessarily. The solution script, lpdsolve, does the following: • generates a start system g(x) according to the linear-product structure of LPDstruct, • appends random hyperplane slices to implement the projective transformation compatible with HomStruct, • solves g(x) = 0 to get all the start points, • forms the homotopy h(x,t) = 1tg(x) +

{l-t)f(x),

• calls endgamer to track the solution paths, invoking a power-series endgame. The results are in matrices xsoln, stats, and xendgame, as described in § C.7.3. C.5

Parameter Homotopies

Suppose we have written a coefficient-parameter target function, f(x;p), implemented as an m-file function, say myf unc, having the calling sequence [f,fx,fp]=myfunc(x,p) as described in § C.3. An example is function twocircle above. How can we form a parameter homotopy function to solve it for some target value of pO? Let's assume we have a solution list for random, complex parameter values pi. (We will see in a moment how to get this using lpdsolve.) What we need is a homotopy function h(x,t;pl,pO) = f(x,p(t;pl,pQ)) where p : C x Q x Q —> Q with Q the parameter space, and p(l;pi,p0) = pi, p(O;pi,j>o) — Po- The path function p must give a continuous path, with continuous first derivative, starting at pi, ending at po, and always staying in the parameter space. HOMLAB does not offer a general solution for arbitrary parameter spaces, but in the special case that Q = C m , a Euclidean space, a linear path suffices: p(t\pi,p0) = tpi + ( l - i ) p 0 Our path tracker and endgame function, endgamer, expects a homotopy function with the calling sequence [h,hx,ht]=h(x,t). Therefore, the parameters and the

370

Numerical Solution of Systems of Polynomials Arising in Engineering and Science

path function must be passed from the top level script to the homotopy evaluation function via global variables. Moreover, we write myfunc in homogeneous form, so projective transformation equations must be appended. The script parsolve takes care of all the formatting once the minimal set of information has been established. Let's assume that pi and pO are in memory along with the start points, as matrix startpoint, listed columnwise and satisfying f(x,pi) = 0. Then, a script for solving the system f(x,p0) = 0 is as follows, assuming myfunc implements f(x,p). global FFUN PATHFUN FFUN = 'myfunc'; PATHFUN = ' l i n . p a t h ' ; global ParStart ParGoal ParStart = p i ; ParGoal = pO; HomStruct= [] ; °/« defaulting to 1-homogeneous parsolve disp('The solutions a r e : ' ) ; disp(dehomog(xsoln,le-8)) Here, lin_path is a pre-defined function for a linear path. Clearly, HomStruct must be set to agree with the homogenization that has been applied to the user-defined myfunc. C.5.1

Initializing Parameter Homotopies

For parameter homotopy to be useful, we must have some way to solve the first example, f(x,pi) — 0. This can be done with a linear-product homotopy. Once the parameterized family of systems has been defined, in the form f(x;p) = 0, HOMLAB can treat it like any other black box target system. This requires, as described in § C.4, one to provide the linear product structure to be used in the homotopy. One additional wrinkle is that the initial set of parameters p\ must be chosen at random, and then passed behind the scenes through a global variable. Script Ipd2par takes care of all of this. An example usage of this to solve the example of the intersection of two circles, function twocircle above, is as follows. global nvar degrees FFUN nvar=2; degrees=[2 2 ] ; FFUN='twocircle'; LPDstruct=ones(4,3) ; °/0 t o t a l degree structure HomStruct=[l 1 1]; °/0 1-homogeneous % 6 random, complex parameters pi = crand(6,l); global ParGoal ParGoal = p i ; Ipd2par dispOThe solutions a r e : ' ) ; disp(dehomog(xsoln,le-8))

HomLab User's Guide

371

This sets up and solves a homotopy of the form 1ftg(x) + (l-t)f{x;p1) Here, we have chosen random, complex parameters, using the function crand, as this is the desired first step in establishing a parameter homotopy. One can use the same script with nonrandom values of ParStart to solve other problems in the family using a linear-product homotopy, but each such run uses the full linear-product root count number of paths. If any of the endpoints are degenerate in the run of Ipd2par for random target parameters, then correspondingly fewer paths can be used in solving subsequent members of the family by parameter homotopy. Just copy pi to ParStart and copy the nondegenerate endpoints into startpoint and you are ready to apply the parameter homotopy of the previous section. Here, "degenerate" can mean singular solutions, solutions at infinity, or solutions on any pre-specified (i.e., independent of the random choice of parameters) irreducible quasiprojective algebraic set. See Chapter 7 for details. C.6

Defining a Homotopy Function

In all the above usages, HOMLAB automatically constructs a homotopy in accord with the instructions provided by the user. Alternatively, one can define a complete homotopy from scratch and then call up HOMLAB'S path tracker to solve it. The homotopy function must be denned with the following interface: function [h,hx,ht]=myriomotopy(x>t) where myhomotopy can be any name of the user's choosing. The user must also provide a list of start points, whereupon the corresponding endpoints can be obtained with the command [xsoln,stats,xendgame]=endgamer(startpoint,'myhomotopy'); See § C.7 for details. C.6.1

Defining a Parameter

Path

In linear-product decompositions, the homotopy path is automatically chosen by HOMLAB as a straight line through the corresponding coefficient space, as justified by Theorem 8.3.1. In parameter homotopies, however, one must ensure that the homotopy path stays in the desired parameter space for all t, not just for the start and target systems at t = 1 and t = 0. If the parameter space is Euclidean, then a linear path is acceptable. As in the example usage of parsolve above, this is easily obtained by the declaration PATHFUN=' lin_path'; which makes use of a pre-defined function lin_path for linearly interpolating between points in parameter space. If

372

Numerical Solution of Systems of Polynomials Arising in Engineering and Science

the parameter space is non-Euclidean, a more general type of path is needed. The user must provide the definition in the form function

[p,dpdt]=mypath(pl,pO,t)

where mypath. m is a user-written m-file function. Then, set PATHFUN=' mypath'; before calling parsolve to execute the homotopy. See the source code for lin_path.m for an example to follow. C.6.2

Homotopy Checking

Most errors in coding a homotopy function can be revealed by checking if computed derivatives agree with a computation based on numerical differentiation. The following routine is provided for this purpose. function [hxerr,hterr]=chekhfun(fname,nx,epsO) —> checks homotopy functions [f,fx,ft]=myfunc(x,t) The checking is done at a random point (x,t) € C nx x C. The functions provide a numerical comparison and also use the Matlab spy function to graphically show which elements are suspicious, having an error greater than espO. If epsO is omitted from the call, it defaults to 10~6. Note that high-level scripts define a global HFUN, which can be used for f name. C.7

The Workhorse: Endgamer

The workhorse routine is endgamer. m which tracks solution paths for a homotopy h(x,t) = 0 from a list of startpoint solutions of h(x, 1) — 0 to their endpoints satisfying h(x, 0) = 0. Specifically, endgamer has the usage [xsoln,stats,xendgame]=endgamer(startpoint,hfun) with thefollowinginputs and outputs. Inputs startpoint An n x N matrix of N start points, listed columnwise. hfun A string name of the homotopy function, h(x,t) : Cn x C - » C n . The function routine must provide derivatives (see § C.6). It is recommended that the homotopy be homogenized. Outputs xsoln Ann x N matrix of the endpoints of the homotopy paths. stats A6xJV matrix of statistics regarding the paths and their endpoints. xendgame An n x N matrix recording the solutions for t at the start of the endgame.

HomLab User's Guide

373

There are a number of control settings regarding path-tracking tolerances and the like which must be set prior to calling endgamer. These global variables can be set by calling htopyset, as is done automatically by the high-level solving scripts totdtab, mhomtab, lpdsolve, and parsolve. To change the default settings, one just puts a copy of htopyset in the current working directory and edits the values. Matlab will find and use the copy in the current directory, overriding the copy in HOMLABIO, which is best left in its original condition. Comments in the original copy ofhtopyset.m tell the default settings in case the user needs them for reference. Routine endgamer loops through the start points and for each one does the following: (1) tracks the path to the beginning of the endgame, t=t_endgame, a global control variable; (2) records the solution at t=t_endgame as a column in xendgame; (3) executes the power-series endgame (§ 10.3.3), monitoring the convergence criterion and stopping when either convergence is reached or when one of several protective stopping conditions is satisfied; (4) records the best solution estimate, as judged by the convergence criterion, as a column in xsoln and certain statistics concerning the solution are recorded as a column in stats. The details of all the required control settings are given next, followed by a detailed description of the outputs. C.7.1

Control Settings

As mentioned above, the control settings are established in htopyset.m, which is called automatically by the high-level scripts. Here, we give a detailed list and describe what each control means, as well as give the default value. We group these into three general categories. These are all global variables. LPD Start System (used by lpdstart) • epsstart = le-12; Each solution of the linear-product start system is found by choosing one linear factor from each equation and solving the resulting linear system. Choices that give a singular linear system are ignored. The solver builds the linear system one equation at a time, using Gaussian elimination to triangularize as it proceeds. If at any stage the magnitude of the largest available pivot is less than epsstart, that combination of linear factors is declared invalid, and the solver moves on to the next combination. Path Tracking (used by tracker). This variable step-size tracker is a correctorpredictor type as described in § 2.3.

374

Numerical Solution of Systems of Polynomials Arising in Engineering and Science

• stepmin = le-6; The minimum step size in t, below which a path is declared as having failed. • maxit = 3; The maximum number of Newton iterations allowed in the corrector. If the designated convergence criterion is not met within this number of iterations, the step is a failure and the step size will be halved. • maxnf e = 1500; The maximum number of function evaluations allowed per path. This limits the amount of computing time that a diverging path may consume. For well-scaled, homogenized homotopies, this criterion should rarely come into play. • epstiny = le-12; In rare instances, a path may fail due to vanishing of the tangent vector (dh/dx)~1dh/dt. This is detected using the tolerance epstiny. Typically, when this occurs, it is a signal that the homotopy is not properly formed, possibly an error in a user-written function for evaluation of the derivatives. End Game (used by endgamer) This routine calls tracker to get to the start of the endgame, then runs the power-series endgame. • stepstart = 0.1; The initial step size for t in the tracker. • epsbig = le-4; The tracking accuracy to be maintained in the initial phase of tracking. This is the convergence tolerance for the corrector. If a path does not successfully reach the endgame, it is tried once more from the beginning with a tighter tolerance of epsbig/100. • epssmall = le-6; The tracking accuracy to be maintained in the endgame. • t_endgame = 0.1; The value of t where the endgame starts. • tstop = le-10; The value of t where the endgame gives up. • t r a t i o = 0.3; During the endgame, samples are taken for t in a geometric series where £& = tratio*£/c_i. The value 0.3 is a compromise between the need to spread the samples out for a well-conditioned fit (tratio smaller) and the need to stay away from t = 0, where the path may be singular. • eps_end = le-10; The criterion for deciding when the endpoint estimate has converged. When two successive estimates agree to this tolerance, success is declared. • CycleMax = 4; This is the maximum winding number tested by the powerseries endgame. In double precision, the endgame is rarely successful above winding number c = 4. • maxerrup = 10; The endgame keeps a record of the smallest change in the endpoint estimate in successive iterations. (This is compared to eps_end for declaring success.) Usually, this measure improves with each successive iteration, unless the path gets too close to t = 0 before converging. However, in the early stages of the endgame, the convergence measure can sometimes increase briefly before entering the endgame operating zone. If there are more than maxerrup successive iterations without improving on

HomLab ,User's Guide

375

the best iteration, the path is stopped. • allowjump = 1; When nonzero, this flag allows the endgame to predictcorrect across the origin in s, where s = t1//<2 is the un-wound path variable. This allows the endgame to sample on both sides of s = 0 to estimate the value of the endpoint by seventh-order interpolation. If allowjump=O, samples are only taken for s > 0, and the endpoint is estimated using cubic extrapolation to s — 0. C.7.2

Verbose Mode

By declaring global verbose and setting verbose=l;, the user will cause endgamer to print out its progress during the endgame for each path. This allows one to see how well the endgame is performing. Usually this is not of great interest, but if one is running a huge problem, it may be worth monitoring a small sample of paths and tuning the control settings for greater efficiency. It is also a useful way of confirming that all is working well: if superlinear convergence is obtained in the endgame, it is a strong indicator that everything is in good order. The five columns of information printed in verbose mode are: • the t value of the current endgame sample, • the difference between the last two endpoint estimates (maximum absolute value of the difference in any variable), • the current best guess for the winding number c, • the status of the endgame, which is the number of samples involved in estimating the endpoint. Each sample includes derivative information. "1" means there is only one sample, so the estimate will be done by linear extrapolation. "2" means two samples, so cubic extrapolation is available. "3" means an additional sample has been acquired on the other side of s = 0, but cubic extrapolation is still used. "4" means there are two samples on each side, so seventh-order interpolation is used for the estimate. • the fifth column is the number of successive iterations that have not improved on the best estimate. C.7.3

Path Statistics

The main tool for interpreting the results is to examine the s t a t s matrix. It has one column per path and six rows. The rows are as follows. • s t a t s (1,:) The value of t at which the endgame gave its best estimate. • s t a t s (2,:) The convergence estimate at the endpoint, which is the maximum absolute value of the difference in any variable between two successive endpoint estimates. • s t a t s (3,:) The function residual, that is the maximum absolute value of any entry in h(x*,0) for the endpoint estimate x*.

376

Numerical Solution of Systems of Polynomials Arising in Engineering and Science

• s t a t s (4, :) The estimated winding number. If the true winding number is higher than CycleMax, this will typically result in a best guess of c=CycleMax in this place. • stats (5,:) Condition number of the Jacobian matrix |^ (x*, 0) at the endpoint estimate x*. • stats (6,:) The total number of function evaluations used in computing this path. For large runs, it is tedious to examine stats by looking at the raw numbers. It is much easier to look at histograms and other types of summary statistics. Any endpoint that does not have a small function residual, s t a t s ( 3 , :), has failed in a serious way; quite likely the path tracker stopped with a large value of t in s t a t s ( l , : ) . A histogram plot of Iogl0(stats(3,:)) gives a quick check whether all the paths have ended in at least an approximate solution. If the endpoint is singular, its function residual can be small while it is still relatively far from the true endpoint. Check loglO (stats (2,:)) to see the endpoint convergence measure. One hopes that all endpoints are computed to the desired accuracy, eps_end, but some may not, especially if they are singularities with cycle number of 4 or greater. If the accuracy is only moderate, say better than 10~6 but not at the 10~10 ones desires, check if the condition number is at least moderately high, say 108 or greater. This would indicate that the root really is singular and failed to be computed accurately for that reason. Depending on one's purpose, that may be enough. When the singular endgame works well, the endpoint accuracy will be better than 10~10 and the condition number of a singular point will be greater than 1010 often as high as 1016 or more. C.8

Solutions at Infinity and Dehomogenization

When the solutions are computed in homogeneous coordinates or multihomogeneous coordinates, they can be scaled in each projective factor. Usually the original formulation is in Cn and it has been recast in P", or in a cross product of projective spaces, by introducing one or more homogenizing coordinates. Solutions at infinity are indicated by a small homogenizing coordinate, or if multihomogenized, by at least one homogenizing coordinate being near zero. Here, being near zero means, typically, being of the same magnitude as the convergence estimate in s t a t s ( 2 , : ) . If the homogenizing coordinate is in row k of xsoln, then a histogram of absdoglO(xsoln(k,:))) can be very revealing. For a finite solution, we wish to rescale to make the homogenizing coordinate(s) equal to one. Subroutine dehomog does this. The short form is x=dehomog(xsoln,epsO) ; where epsO is the magnitude of the homogenizing coordinate below which a solu-

HomLab User's Guide

377

tion is declared to be at infinity. This form assumes that the solutions are onehomogenized and that the homogenizing coordinate is the last entry. Any solution determined to be at infinity is rescaled by its largest element, while a finite one is rescaled by the homogenizing coordinate. This is usually what one wants, but the result can be a bit surprising if epsO is made too small so that a poorly computed solution at infinity gets erroneously rescaled as if it were finite. A more elaborate form must be used for multihomogenized solutions: x=dehomog(xsoln,espO,HomStruct,homvar); where HomStruct identifies the membership in the various homogeneous groupings, and homvar is a list of the row number for each homogenizing variable. If homvar is missing, the last variable of each group is assumed by default to be the homogenizing variable for that group. In either the short form or the long form, dehomog sets one variable of each homogeneous group to one.

Bibliography

Abhyankar, S. S. (1990). Algebraic geometry for scientists and engineers, Vol. 35 of Mathematical Surveys and Monographs. Providence, RI: American Mathematical Society. Alefeld, G., k Herzberger, J. (1983). Introduction to interval computations. Computer Science and Applied Mathematics. New York: Academic Press Inc. [Harcourt Brace Jovanovich Publishers]. Translated from the German by Jon Rokne. Allgower, E. L., Erdmann, M., k Georg, K. (2002). On the complexity of exclusion algorithms for optimization. J. Complexity, 18(2), 573-588. Algorithms and complexity for continuous problems/Algorithms, computational complexity, and models of computation for nonlinear and multivariate problems (Dagstuhl/South Hadley, MA, 2000). Allgower, E. L., k Georg, K. (1993). Continuation and path following. In Ada numerica, Vol. 2 (pp. 1-64). Cambridge: Cambridge Univ. Press. Allgower, E. L., k Georg, K. (1997). Numerical path following. In Handbook of numerical analysis, Vol. V (pp. 3-207). Amsterdam: North-Holland. Allgower, E. L., k Georg, K. (2003). Introduction to numerical continuation methods, Vol. 45 of Classics in Applied Mathematics. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM). Reprint of the 1990 edition [SpringerVerlag, Berlin]. Allgower, E. L., Georg, K., k Miranda, R. (1992). The method of resultants for computing real solutions of polynomial systems. SIAM J. Numer. Anal., 29(3), 831-844. Allgower, E. L., k Sommese, A. J. (2002). Piecewise linear approximation of smooth compact fibers. J. Complexity, 18(2), 547-556. Algorithms and complexity for continuous problems/Algorithms, computational complexity, and models of computation for nonlinear and multivariate problems (Dagstuhl/South Hadley, MA, 2000). Alt, H. (1923). Uber die Erzeugung gegebener ebener Kurven mit Hilfe des Gelenkvierecks. Zeitschrift fur Angewandte Mathematik und Mechanik, 3(1), 13-19. Arbarello, E., Cornalba, M., Griffiths, P. A., & Harris, J. (1985). Geometry of algebraic curves. Vol. I, Vol. 267 of Grundlehren der Mathematischen Wissenschaften 379

380

Numerical Solution of Systems of Polynomials Arising in Engineering and Science

[Fundamental Principles of Mathematical Sciences]. New York: Springer-Verlag. Auzinger, W., & Stetter, H. J. (1988). An elimination algorithm for the computation of all zeros of a system of multivariate polynomial equations. In Numerical mathematics, Singapore 1988, Vol. 86 of Internat. Schriftenreihe Numer. Math. (pp. 11-30). Basel: Birkhauser. Bates, D., Peterson, C , & Sommese, A. J. (2005a). A numerical-symbolic algorithm for computing the multiplicity of a component of an algebraic set. in preparation. Bates, D., Sommese, A. J., & Wampler, C. W. (2005b). Multiprecision endgames for homotopy continuation, in preparation. Beltrametti, M. C , Howard, A., Schneider, M., &, Sommese, A. J. (2000). Projections from subvarieties. In Complex analysis and algebraic geometry (pp. 71-107). Berlin: de Gruyter. Beltrametti, M. C , & Sommese, A. J. (1995). The adjunction theory of complex protective varieties, Vol. 16 of de Gruyter Expositions in Mathematics. Berlin: Walter de Gruyter & Co. Bernstein, D. N. (1975). The number of roots of a system of equations. Functional Anal. Appl., 9(3), 183-185. Translated from Funktsional. Anal, i Prilozhen 9(3):1-4,1975. Borel, A. (1969). Linear algebraic groups. Notes taken by H. Bass. W. A. Benjamin, Inc., New York-Amsterdam. Bottema, O., h Roth, B. (1979). Theoretical kinematics, Vol. 24 of North-Holland Series in Applied Mathematics and Mechanics. Amsterdam: North-Holland Publishing Co. Burmester, L. E. H. (1888). Lehrbuch der Kinematik. Leipzig A. Felix. Calabri, A., & Ciliberto, C. (2001). On special projections of varieties: epitome to a theorem of Beniamino Segre. Adv. Geom., 1(1), 97-106. Canny, J. (1990). Generalised characteristic polynomials. J. Symbolic Comput., 9, 241-250. Canny, J., & Manocha, D. (1993). Multipolynomial resultant algorithms. J. Symbolic Comput., 15, 99-122. Canny, J., & Rojas, J. M. (1991). An optimal condition for determining the exact number of roots of a polynomial system. Proceedings of the 1991 International Symposium on Symbolic and Algebraic Computation (pp. 96-101). ACM, New York. Chablat, D., Wenger, P., Majou, R., & Merlet, J.-P. (2004). An interval based study for the design and the comparison of three-degrees-of-freedom parallel kinematic machines. Int. J. Robotics Research, 23(6), 615-624. Chen, N. X., & Song, S.-M. (1994). Direct position analysis of the 4-6 Stewart platform. ASME J. Mech. Design, 116(1), 61-66. Chow, S. N., Mallet-Paret, J., & Yorke, J. A. (1979). A homotopy method for locating all zeros of a system of polynomials. In Functional differential equations and approximation of fixed points (proc. summer school and conf, univ. bonn,

Bibliography

381

bonn, 1978), Vol. 730 of Lecture Notes in Math. (pp. 77-88). Berlin: Springer. Chu, M. T., Li, T.-Y., & Sauer, T. (1988). Homotopy method for general A-matrix problems. SI AM J. Matrix Anal. AppL, 9(4), 528-536. Cox, D., Little, J., & O'Shea, D. (1997). Ideals, varieties, and algorithms. Undergraduate Texts in Mathematics. New York: Springer-Verlag, second edition. An introduction to computational algebraic geometry and commutative algebra. Cox, D., Little, J., & O'Shea, D. (1998). Using algebraic geometry, Vol. 185 of Graduate Texts in Mathematics. New York: Springer-Verlag. D'Andrea, C , & Emiris, I. Z. (2003). Sparse resultant perturbations. In Algebra, geometry, and software systems (pp. 93-107). Berlin: Springer. Datta, R. S. (2003). Using computer algebra to find Nash equilibria. Proceedings of the 2003 International Symposium on Symbolic and Algebraic Computation (pp. 74-79). New York: ACM. Davidenko, D. F. (1953a). On a new method of numerical solution of systems of nonlinear equations. Doklady Akad. Nauk SSSR (N.S.), 88, 601-602. Davidenko, D. F. (1953b). On approximate solution of systems of nonlinear equations. Ukrain. Mat. Zurnal, 5, 196-206. Davis, P. J. (1975). Interpolation and approximation. New York: Dover Publications Inc. Republication, with minor corrections, of the 1963 original, with a new preface and bibliography. Decker, W., Greuel, G.-M., & Pfister, G. (1999). Primary decomposition: algorithms and comparisons. In Algorithmic algebra and number theory (Heidelberg, 1997) (pp. 187-220). Berlin: Springer. Decker, W., & Schreyer, F.-O. (2001). Computational algebraic geometry today. In Applications of algebraic geometry to coding theory, physics and computation (Eilat, 2001), Vol. 36 of NATO Sci. Ser. II Math. Phys. Chem. (pp. 65-119). Dordrecht: Kluwer Acad. Publ. Decker, W., & Schreyer, F.-O. (2005). Solving polynomial equations: Foundations, algorithms, and applications, to appear. Denavit, J., & Hartenberg, R. S. (1955). A kinematic notation for lower pair mechanisms based on matrices. J. Appl. Mechanics, 22, 215-221. Trans. ASME, vol. 77. Dhingra, A., Kohli, D., & Xu, Y. X. (1992). Direct kinematic of general Stewart platforms. DE-Vol. 45, Robotics, Spatial Mechanisms, and Mechanical Systems (pp. 107-112). ASME. Dian, J., & Kearfott, R. B. (2003). Existence verification for singular and nonsmooth zeros of real nonlinear systems. Math. Comp., 72(242), 757-766. Dickenstein, A., & Emiris, I. Z. (Eds.), (preprint). Solving polynomial equations: Foundations, algorithms, and applications. Berlin Heidelberg New York: Springer-Verlag. Dietmaier, P. (1998). The Stewart-Gough platform of general geometry can have 40 real postures. In J. Lenarcic, & M. L. Husty (Eds.), Advances in robot kinematics:

382

Numerical Solution of Systems of Polynomials Arising in Engineering and Science

Analysis and control (pp. 1-10). Dordrecht: Kluwer Academic Publishers. Dixon, A. L. (1909). The eliminant of three quantics in two independent variables. Proc. London Math. Soc, 2(7), 49-69. Drexler, F. J. (1977). Eine Methode zur Berechnung samtlicher Losungen von Polynomgleichungssystemen. Numer. Math., 29(1), 45-58. Drexler, F. J. (1978). A homotopy method for the calculation of all zeros of zerodimensional polynomial ideals. In Developments in statistics, vol. 1 (pp. 69-93). New York: Academic Press. Duffy, J., & Crane, C. (1980). A displacement analysis of the general spatial 7-link, 7R mechanism. Mechanism Machine Theory, i5(3-A), 153-169. Eisenbud, D. (1995). Commutative Algebra with a view toward algebraic geometry, Vol. 150 of Graduate Texts in Mathematics. New York: Springer-Verlag. Emiris, I. Z. (1994). Sparse elimination and applications in kinematics. PhD thesis, Computer Science Division, Dept. of Electrical Engineering and Computer Science, University of California, Berkeley. Emiris, I. Z. (1995). A general solver based on sparse resultants. Proc. PoSSo (Polynomial System Solving) Workshop on Software (pp. 35-54). Paris. Emiris, I. Z. (2003). Discrete geometry for algebraic elimination. In Algebra, geometry, and software systems (pp. 77-91). Berlin: Springer. Faugere, J. C , & Lazard, D. (1995). The combinatorial classes of parallel manipulators. Mechanism Machine Theory, 30(6), 765-776. Feinberg, M. (1980). Chemical oscillations, multiple equilibria, and reaction network structure. In W. E. Stewart (Ed.), Dynamics and modelling of reactive systems (pp. 59-130). Academic Press, Inc. Fischer, G. (1976). Complex analytic geometry. Berlin: Springer-Verlag. Lecture Notes in Mathematics, Vol. 538. Fischer, G. (2001). Plane algebraic curves, Vol. 15 of Student Mathematical Library. Providence, RI: American Mathematical Society. Translated from the 1994 German original by Leslie Kay. Freudenstein, F., & Roth, B. (1963). Numerical solution of systems of nonlinear equations. J. ACM, 10(4), 550-556. Frisch, J. (1967). Points de platitude d'un morphisme d'espaces analytiques complexes. Invent. Math., 4, 118-138. Fritzsche, K., & Grauert, H. (2002). From holomorphic functions to complex manifolds, Vol. 213 of Graduate Texts in Mathematics. New York: Springer-Verlag. Fulton, W. (1998). Intersection theory, Vol. 2 of Ergebnisse der Mathematik und ihrer Grenzgebiete. 3. Folge. A Series of Modern Surveys in Mathematics [Results in Mathematics and Related Areas. 3rd Series. A Series of Modern Surveys in Mathematics]. Berlin: Springer-Verlag, second edition. Gao, T., & Li, T.-Y. (2000). Mixed volume computation via linear programming. Taiwanese J. Math., 4(4), 599-619. Gao, T., & Li, T.-Y. (2003). Mixed volume computation for semi-mixed systems.

Bibliography

383

Discrete Comput. Geom., 29(2), 257-277. Gao, T., Li, T.-Y., Verschelde, J., & Wu, M. (2000). Balancing the lifting values to improve the numerical stability of polyhedral homotopy continuation methods. Appl. Math. Comput, 114(2-3), 233-247. Gao, T., Li, T.-Y., & Wang, X. (1999). Finding all isolated zeros of polynomial systems in C" via stable mixed volumes. J. Symbolic Comput., 28(1-2), 187-211. Polynomial elimination—algorithms and applications. Garcia, C. B., & Zangwill, W. I. (1979). Finding all solutions to polynomial systems and other systems of equations. Math. Programming, 16(2), 159-176. Garcia, C. B., & Zangwill, W. I. (1980). Global continuation methods for finding all solutions to polynomial systems of equations in n variables. In Extremal methods and systems analysis (Interned. Sympos., Univ. Texas, Austin, Tex., 1977), Vol. 174 of Lecture Notes in Econom. and Math. Systems (pp. 481-497). Berlin: Springer. Gelfand, I., Kapranov, M., & Zelevinsky, A. (1994). Discriminants, resultants and multidimensional determinants. Boston: Birkhauser. Georg, K. (2001). Improving the efficiency of exclusion algorithms. Adv. Geom., 1(2), 193-210. Georg, K. (2003). A new exclusion test. J. Comput. Appl. Math., 152(1-2), 147160. Proceedings of the International Conference on Recent Advances in Computational Mathematics (ICRACM 2001) (Matsuyama). Giusti, M., Hagele, K., Lecerf, G., Marchand, J., & Salvy, B. (2000). The projective Noether Maple package: computing the dimension of a projective variety. J. Symbolic Comput, 30(3), 291-307. Goedecker, S. (1994). Remark on algorithms to find roots of polynomials. SI AM J. Sci. Comput, 15(5), 1059-1063. Goresky, M., & MacPherson, R. (1988). Stratified Morse theory, Vol. 14 of Ergebnisse der Mathematik und ihrer Grenzgebiete (3) [Results in Mathematics and Related Areas (3)]. Berlin: Springer-Verlag. Greuel, G.-M. (2000). Computer algebra and algebraic geometry—achievements and perspectives. J. Symbolic Comput, 30(3), 253-289. Greuel, G.-M., & Pfister, G. (2002). A singular introduction to commutative algebra. Berlin: Springer-Verlag. With contributions by O. Bachmann, C. Lossen and H. Schonemann, With 1 CD-ROM (Windows, Macintosh, and UNIX). Griewank, A., & Osborne, M. R. (1983). Analysis of Newton's method at irregular singularities. SIAM J. Numer. Anal, 20(4), 747-773. Griffis, M., & Duffy, J. (1993). Method and apparatus for controlling geometrically simple parallel mechanisms with distinctive connections. US Patent 5,179,525. Griffths, P. A., & Harris, J. (1994). Principles of algebraic geometry. Wiley Classics Library. New York: John Wiley & Sons Inc. Reprint of the 1978 original. Gunning, R. C. (1970). Lectures on complex analytic varieties: The local parametrization theorem. Mathematical Notes. Princeton, N.J.: Princeton University

384

Numerical Solution of Systems of Polynomials Arising in Engineering and Science

Press. Gunning, R. C. (1990). Introduction to holomorphic functions of several variables. Vol. II. The Wadsworth & Brooks/Cole Mathematics Series. Monterey, CA: Wadsworth k Brooks/Cole Advanced Books & Software. Local theory. Gunning, R. C, k Rossi, H. (1965). Analytic functions of several complex variables. Englewood Cliffs, N.J.: Prentice-Hall Inc. Hamming, R. W. (1986). Numerical methods for scientists and engineers. New York: Dover Publications Inc., second edition. Harris, J. (1995). Algebraic geometry, Vol. 133 of Graduate Texts in Mathematics. New York: Springer-Verlag. A first course, Corrected reprint of the 1992 original. Hartenberg, R. S., & Denavit, J. (1964). Kinematic synthesis of linkages. McGrawHill, N.Y. Hartshorne, R. (1977). Algebraic geometry. New York: Springer-Verlag. Graduate Texts in Mathematics, No. 52. Hille, E. (1959). Analytic function theory. Vol. 1. Introduction to Higher Mathematics. Ginn and Company, Boston. Hille, E. (1962). Analytic function theory. Vol. II. Introductions to Higher Mathematics. Ginn and Co., Boston, Mass.-New York-Toronto, Ont. Hodge, W. V. D., k Pedoe, D. (1994a). Methods of algebraic geometry. Vol. I. Cambridge Mathematical Library. Cambridge: Cambridge University Press. Book I: Algebraic preliminaries, Book II: Projective space, Reprint of the 1947 original. Hodge, W. V. D., k Pedoe, D. (1994b). Methods of algebraic geometry. Vol. II. Cambridge Mathematical Library. Cambridge: Cambridge University Press. Book III: General theory of algebraic varieties in projective space, Book IV: Quadrics and Grassmann varieties, Reprint of the 1952 original. Hodge, W. V. D., k Pedoe, D. (1994c). Methods of algebraic geometry. Vol. III. Cambridge Mathematical Library. Cambridge: Cambridge University Press. Book V: Birational geometry, Reprint of the 1954 original. Ho§ten, S., k Shapiro, J. (2000). Primary decomposition of lattice basis ideals. J. Symbolic Comput., 29(4-5), 625-639. Symbolic computation in algebra, analysis, and geometry (Berkeley, CA, 1998). Huang, Y., Wu, W., Stetter, H. J., k Zhi, L. (2000). Pseudofactors of multivariate polynomials. Proceedings of the 2000 International Symposium on Symbolic and Algebraic Computation (St. Andrews) (pp. 161-168). New York: ACM. Huber, B., Sottile, F., k Sturmfels, B. (1998). Numerical Schubert calculus. J. Symbolic Comput., 26(6), 767-788. Symbolic numeric algebra for polynomials. Huber, B., k Sturmfels, B. (1995). A polyhedral method for solving sparse polynomial systems. Math. Comp., 64(212), 1541-1555. Huber, B., k Sturmfels, B. (1997). Bernstein's theorem in affine space. Discrete Comput. Geom., 17(2), 137-141. Huber, B., k Verschelde, J. (1998). Polyhedral end games for polynomial continuation. Numer. Algorithms, 18(1), 91-108.

Bibliography

385

Huber, B., & Verschelde, J. (2000). Pieri homotopies for problems in enumerative geometry applied to pole placement in linear systems control. SIAM J. Control Optim., 38(4), 1265-1287. Husty, M. L. (1996). An algorithm for solving the direct kinematics of general Stewart-Gough platforms. Mechanism Machine Theory, 31(4), 365-380. Husty, M. L., & Karger, A. (2000). Self-motions of Griffis-Duffy type parallel manipulators. Proceedings of the 2000 IEEE Int. Conf. Robotics and Automation, CDROM, San Francisco, CA, April 24-28, 2000. IEEE. Iitaka, S. (1982). Algebraic geometry, Vol. 76 of Graduate Texts in Mathematics. New York: Springer-Verlag. An introduction to birational geometry of algebraic varieties, North-Holland Mathematical Library, 24. Innocenti, C. (1995). Polynomial solution to the position analysis of the 7-link Assur kinematic chain with one quaternary link. Mechanism Machine Theory, 30(8), 1295-1303. Isaacson, E., & Keller, H. B. (1994). Analysis of numerical methods. New York: Dover Publications Inc. Corrected reprint of the 1966 original [Wiley, New York]. Kearfott, R. B. (1996). Rigorous global search: continuous problems, Vol. 13 of Nonconvex Optimization and its Applications. Dordrecht: Kluwer Academic Publishers. Kearfott, R. B. (1997). Empirical evaluation of innovations in interval branch and bound algorithms for nonlinear systems. SIAM J. Sci. Comp., 18(2), 574-594. Kearfott, R. B., & Novoa, M. (1990). Algorithm 681: INTBIS, a portable interval Newton/bisection package. ACM Trans. Math. Softw., 16(2), 152-157. Kearfott, R. B., & Xing, Z. (1994). An interval step control for continuation methods. SIAM J. Numer. Anal., 31(3), 892-914. Keller, H. B. (1981). Geometrically isolated nonisolated solutions and their approximation. SIAM J. Numer. Anal., 18(5), 822-838. Kendig, K. (1977). Elementary algebraic geometry. New York: Springer-Verlag. Graduate Texts in Mathematics, No. 44. Khovanski, A. G. (1978). Newton polyhedra, and the genus of complete intersections. Funktsional. Anal, i Prilozhen., 12(1), 51-61. Kleiman, S. L. (1986). Tangency and duality. Proceedings of the 1984 Vancouver conference in algebraic geometry, Vol. 6 of CMS Conf. Proc. (pp. 163-225). Providence, RI: Amer. Math. Soc. Knuth, D. E. (1981). The art of computer programming. Vol. 2. Addison-Wesley Publishing Co., Reading, Mass., second edition. Seminumerical algorithms, Addison-Wesley Series in Computer Science and Information Processing. Krick, T. (2004). Straight-line programs in polynomial equation solving. In F. Cucker, R. DeVore, P. Olver, & E. Siili (Eds.), Foundations of computational mathematics, Minneapolis 2002. Cambridge University Press. Kuo, Y.-C, Li, T.-Y., & Wu, D. (2004). Determining whether a numerical solution of a polynomial system is isolated, preprint.

386

Numerical Solution of Systems of Polynomials Arising in Engineering and Science

Kushnirenko, A. G. (1976). Newton polytopes and the Bezout theorem. Funktsional. Anal, i Prilozhen., 10(3), 82-83. Lazard, D. (1993). On the representation of rigid-body motions and its application to generalized platform manipulators. In J. Angeles, P. Kovacs, & G. Hommel (Eds.), Computational kinematics (pp. 175—182). Kluwer. Lecerf, G. (2001). Une alternative aux methodes de reecriture pour la resolution des system.es algebriques. PhD thesis, Ecole Polytechnique. Lecerf, G. (2002). Quadratic Newton iteration for systems with multiplicity. Found. Comput. Math., 2(3), 247-293. Lee, H.-Y., & Liang, C.-G. (1988). Displacement analysis of the general spatial 7-link 7R mechanism. Mechanism Machine Theory, 23(3), 219-226. Leykin, A., Verschelde, J., & Zhao, A. (2004). Newton's method with deflation for isolated singularities of polynomial systems, preprint. Li, T.-Y. (1983). On Chow, Mallet-Paret and Yorke homotopy for solving system of polynomials. Bull. Inst. Math. Acad. Sinica, 11(3), 433-437. Li, T.-Y. (1993). Solving polynomial systems by homotopy continuation methods. In Computer mathematics (Tianjin, 1991), Vol. 5 of Nankai Ser. Pure Appl. Math. Theoret. Phys. (pp. 18-35). River Edge, NJ: World Sci. Publishing. Li, T.-Y. (1997). Numerical solution of multivariate polynomial systems by homotopy continuation methods. In Ada numerica, Vol. 6 (pp. 399-436). Cambridge: Cambridge Univ. Press. Li, T.-Y. (1999). Solving polynomial systems by polyhedral homotopies. Taiwanese J. Math., 3(3), 251-279. Li, T.-Y. (2003). Numerical solution of polynomial systems by homotopy continuation methods. In Handbook of numerical analysis, Vol. XI (pp. 209-304). Amsterdam: North-Holland. Li, T.-Y., & Li, X. (2001). Finding mixed cells in the mixed volume computation. Found. Comput. Math., 1(2), 161-181. Li, T.-Y., & Sauer, T. (1987a). Homotopy method for generalized eigenvalue problems Ax = XBx. Linear Algebra Appl., 91, 65-74. Li, T.-Y., & Sauer, T. (1987b). Regularity results for solving systems of polynomials by homotopy method. Numer. Math., 50(3), 283-289. Li, T.-Y., &; Sauer, T. (1989). A simple homotopy for solving deficient polynomial systems. Japan J. Appl. Math., 6(3), 409-419. Li, T.-Y., Sauer, T., & Yorke, J. A. (1987a). Numerical solution of a class of deficient polynomial systems. SIAM J. Numer. Anal, 24(2), 435-451. Li, T.-Y., Sauer, T., & Yorke, J. A. (1987b). The random product homotopy and deficient polynomial systems. Numer. Math., 51(5), 481-500. Li, T.-Y., Sauer, T., & Yorke, J. A. (1988). Numerically determining solutions of systems of polynomial equations. Bull. Amer. Math. Soc. (N.S.), 18(2), 173-177. Li, T.-Y., Sauer, T., & Yorke, J. A. (1989). The cheater's homotopy: an efficient procedure for solving systems of polynomial equations. SIAM J. Numer. Anal.,

Bibliography

387

26(5), 1241-1251. Li, T. Y., Wang, T., & Wang, X. (1996). Random product homotopy with minimal BKK bound. In The mathematics of numerical analysis (Park City, UT, 1995), Vol. 32 of Lectures in Appl. Math. (pp. 503-512). Providence, RI: Amer. Math. Soc. Li, T.-Y., & Wang, X. (1991). Solving deficient polynomial systems with homotopies which keep the subschemes at infinity invariant. Math. Comp., 56(194), 693-710. Li, T.-Y., & Wang, X. (1992). Nonlinear homotopies for solving deficient polynomial systems with parameters. SIAM J. Numer. Anal, 29(4), 1104-1118. Li, T.-Y., & Wang, X. (1996). The BKK root count in C". Math. Comp., 65(216), 1477-1484. Li, T.-Y., & Zheng, Z. (2004). A rank-revealing method and its applications. preprint. Lipman, J. (1975). Introduction to resolution of singularities. In Algebraic geometry (Proc. Sympos. Pure Math., Vol. 29, Humboldt State Univ., Arcata, Calif., 1974) (pp. 187-230). Providence, R.I.: Amer. Math. Soc. Lo Cascio, M. L., Pasquini, L., & Trigiante, D. (1989). Simultaneous determination of polynomial roots and multiplicities: an algorithm and related problems. Ricerche Mat, 38(2), 283-305. Losch, S. (1995). Parallel redundant manipulators based on open and closed normal Assur chains. In J.-P. Merlet, & B. Ravani (Eds.), Computational kinematics '95, Proceedings of the Second Workshop held in Sophia Antipolis, September 4-6, 1995, Vol. 40 of Solid Mechanics and its Applications (pp. x+310). Dordrecht: Kluwer Academic Publishers Group. Lu, Y., Sommese, A. J., & Wampler, C. W. (2005). Finding all real solutions of polynomial systems: I the curve case, in preparation. Macaulay, F. (1902). On some formulas in elimination. Proc. London Math. Soc, 3, 3-27. Manocha, D. (1993). Efficient algorithms for multipolynomial resultant. The Computer Journal, 36, 485-496. Manocha, D. (1994). Solving systems of polynomial equations. IEEE Comput. Graph. Appl, 36, 46-55. Manocha, D., & Canny, J. F. (1994). Efficient inverse kinematics for general 6R manipulators. IEEE Trans. Rob. Auto., 10(5), 648-657. Manseur, R., & Doty, K. (1989). A robot manipulator with 16 real inverse kinematic solution set. Int. J. Robotics Res., 8(5), 75-79. Marden, M. (1966). Geometry of polynomials. Second edition. Mathematical Surveys, No. 3. Providence, R.I.: American Mathematical Society. Mavroidis, C, & Roth, B. (1995a). Analysis of overconstrained mechanisms. ASME J. Mech. Design, 117, 69-74. Mavroidis, C, & Roth, B. (1995b). New and revised overconstrained mechanisms. ASME J. Mech. Design, 117, 75-82.

388

Numerical Solution of Systems of Polynomials Arising in Engineering and Science

Mayer St-Onge, B., &: Gosselin, C. M. (2000). Singularity analysis and representation of the general Gough-Stewart platform. Int. J. Robotics Research, 19, Li 1— ZOO.

Meintjes, K., & Morgan, A. P. (1987). A methodology for solving chemical equilibrium systems. Appl. Math. Com/put., 22, 333-361. Merlet, J.-P. (1989). Singular configurations of parallel manipulators and Grassmann geometry. Int. J. Robotics Research, 8, 45—56. Merlet, J.-P. (2000). Parallel robots. Kluwer Academic Publishers, Dordrecht, The Netherlands. Merlet, J.-P. (2001). A parser for the interval evaluation of analytical functions and its applications to engineering problems. J. Symbolic Computation, 31, 475-486. Mignotte, M., & Stefanescu, D. (1999). Polynomials. Springer Series in Discrete Mathematics and Theoretical Computer Science. Springer-Verlag, Singapore. An algorithmic approach. Milnor, J. W. (1965). Topology from the differentiate viewpoint. Based on notes by David W. Weaver. The University Press of Virginia, Charlottesville, Va. Moller, H. M. (1998). Grobner bases and numerical analysis. In Grobner bases and applications (Linz, 1998), Vol. 251 of London Math. Soc. Lecture Note Ser. (pp. 159-178). Cambridge: Cambridge Univ. Press. Moller, H. M., & Stetter, H. J. (1995). Multivariate polynomial equations with multiple zeros solved by matrix eigenproblems. Num. Math., 70, 311-329. Moore, R. E. (1979). Methods and applications of interval analysis, Vol. 2 of SIAM Studies in Applied Mathematics. Philadelphia, Pa.: Society for Industrial and Applied Mathematics (SIAM). Morgan, A. P. (1983). A method for computing all solutions to systems of polynomial equations. ACM Trans. Math. Software, 9(1), 1-17. Morgan, A. P. (1986a). A homotopy for solving polynomial systems. Appl. Math. Comput., 18(1), 87-92. Morgan, A. P. (1986b). A transformation to avoid solutions at infinity for polynomial systems. Appl. Math. Comput., 18(1), 77-86. Morgan, A. P. (1987). Solving polynomial systems using continuation for engineering and scientific problems. Prentice-Hall, Englewood Cliffs, N.J. Morgan, A. P., & Sommese, A. J. (1987a). A homotopy for solving general polynomial systems that respects m-homogeneous structures. Appl. Math. Comput., 101-113. Morgan, A. P., & Sommese, A. J. (1987b). Computing all solutions to polynomial systems using homotopy continuation. Appl. Math. Comput., 115-138. Errata: Appl. Math. Comput. 51 (1992), p. 209. Morgan, A. P., & Sommese, A. J. (1989). Coefficient-parameter polynomial continuation. Appl. Math. Comput, 29(2), 123-160. Errata: Appl. Math. Comput. 51:207(1992). Morgan, A. P., & Sommese, A. J. (1990). Generically nonsingular polynomial

Bibliography

389

continuation. In Computational solution of nonlinear systems of equations (Fort Collins, CO, 1988), Vol. 26 of Lectures in Appl. Math. (pp. 467-493). Providence, RI: Amer. Math. Soc. Morgan, A. P., Sommese, A. J., & Wampler, C. W. (1990). Polynomial continuation for mechanism design problems. In Computational solution of nonlinear systems of equations (Fort Collins, CO, 1988), Vol. 26 of Lectures in Appl. Math. (pp. 495-517). Providence, RI: Amer. Math. Soc. Morgan, A. P., Sommese, A. J., & Wampler, C. W. (1991). Computing singular solutions to nonlinear analytic systems. Numer. Math., 58(7), 669-684. Morgan, A. P., Sommese, A. J., & Wampler, C. W. (1992a). Computing singular solutions to polynomial systems. Adv. in Appl. Math., 13(3), 305-327. Morgan, A. P., Sommese, A. J., & Wampler, C W. (1992b). A power series method for computing singular solutions to nonlinear analytic systems. Numer. Math., 63(3), 391-409. Morgan, A. P., Sommese, A. J., & Wampler, C. W. (1995). A productdecomposition bound for Bezout numbers. SIAM J. Numer. Anal, 32(A), 13081325. Morgan, A. P., Sommese, A. J., & Watson, L. T. (1989). Finding all isolated solutions to polynomial systems using HOMPACK. A CM Trans. Math. Software, 15(2), 93-122. Morgan, A. P., & Wampler, C. W. (1990). Solving a planar four-bar design problem using continuation. ASME J. Mech. Design, 112, 544-550. Morgan, A. P., & Watson, L. T. (1987). Solving polynomial systems of equations on a hypercube. In Hypercube multiprocessors 1987 (Knoxville, TN, 1986) (pp. 501-511). Philadelphia, PA: SIAM. Morgan, A. P., & Watson, L. T. (1989). A globally convergent parallel algorithm for zeros of polynomial systems. Nonlinear Anal., 13(\1), 1339-1350. Mourrain, B. (1993, July). The 40 generic positions of a parallel robot. In M. Bronstein (Ed.), Proc. ISSAC'93 (Kiev) (pp. 173-182). ACM Press. Mourrain, B. (1996). Enumeration problems in geometry, robotics and vision. In Algorithms in algebraic geometry and applications (Santander, 1994), Vol. 143 of Progr. Math. (pp. 285-306). Basel: Birkhauser. Mourrain, B. (1998). Computing the isolated roots by matrix methods. J. Symbolic Comput., 26(6), 715-738. Symbolic numeric algebra for polynomials. Mumford, D. (1966). Lectures on curves on an algebraic surface. With a section by G. M. Bergman. Annals of Mathematics Studies, No. 59. Princeton, N.J.: Princeton University Press. Mumford, D. (1970). Varieties denned by quadratic equations. In E. Marchionna (Ed.), Questions on algebraic varieties (C.I.M.E., III Ciclo, Varenna, 1969) (pp. 29-100). Rome: Edizioni Cremonese. Mumford, D. (1995). Algebraic geometry. I. Classics in Mathematics. Berlin: Springer-Verlag. Complex projective varieties, Reprint of the 1976 edition.

390

Numerical Solution of Systems of Polynomials Arising in Engineering and Science

Mumford, D. (1999). The red book of varieties and schemes, Vol. 1358 of Lecture

Notes in Mathematics. Berlin: Springer-Verlag, expanded edition. Includes the Michigan lectures (1974) on curves and their Jacobians, With contributions by E. Arbarello. Nanua, P., Waldron, K. J., & Murthy, V. (1991). Direct kinematic solution of a Stewart platform. IEEE Trans, on Robotics and Automation, 6(4), 438-444. Neumaier, A. (1990). Interval methods for systems of equations, Vol. 37 of Encyclopedia of Mathematics and its Applications. Cambridge: Cambridge University Press. Nielsen, J., & Roth, B. (1999). Solving the input/output problem for planar mechanisms. ASME J. Mech. Design, 121(2), 206-211. Ojika, T. (1987). Modified deflation algorithm for the solution of singular problems. I. A system of nonlinear algebraic equations. J. Math. Anal. Appl., 123, 199-221. Ojika, T., Watanabe, S., & Mitsui, T. (1983). Deflation algorithm for the multiple roots of a system of nonlinear equations. J. Math. Anal. Appl., 96, 463-479. Pan, V. Y. (1997). Solving a polynomial equation: some history and recent progress. SI AM Rev., 39(2), 187-220. Pasquini, L., & Trigiante, D. (1985). A globally convergent method for simultaneously finding polynomial roots. Math. Comp., ^^(169), 135-149. Pernkopf, F., & Husty, M. L. (2002). Singularity analysis of spatial stewart-gough platforms with planar base and platform. Proc. ASME Design Eng. Tech. Conf, Montreal, Canada, Sept. 30~Oct. 2, 2002. Pieper, D. L. (1968). The kinematics of manipulators under computer control. PhD thesis, Computer Science Dept., Stanford University. Primrose, E. J. F. (1986). On the input-output equation of the general 7Rmechanism. Mechanism Machine Theory, 21(6), 509-510. Raghavan, M. (1991). The Stewart platform of general geometry has 40 configurations. Proc. ASME Design and Automation Conf, vol. 32-2 (pp. 397-402). ASME. Raghavan, M. (1993). The Stewart platform of general geometry has 40 configurations. ASME J. Mech. Design, 115, 277-282. Raghavan, M., & Roth, B. (1993). Inverse kinematics of the general 6R manipulator and related linkages. ASME J. Mech. Design, 115, 502-508. Raghavan, M., & Roth, B. (1995). Solving polynomial systems for the kinematic analysis and synthesis of mechanisms and robot manipulators. ASME J. Mech. Design, 117, 71-79. Roberts, S. (1875). On three-bar motion in plane space. Proc. London Math. Soc, VII, 14-23. Rojas, J. M. (1994). A convex geometric approach to counting the roots of a polynomial system. Theoret. Comput. Sci., 133(1), 105-140. Selected papers of the Workshop on Continuous Algorithms and Complexity (Barcelona, 1993). Rojas, J. M. (1999). Toric intersection theory for affine root counting. J. Pure Appl.

Bibliography

391

Algebra, 136(1), 67-100. Rojas, J. M., & Wang, X. (1996). Counting affine roots of polynomial systems via pointed Newton polytopes. J. Complexity, 12(2), 116-133. Ronga, F., & Vust, T. (1995). Stewart platforms without computer? In Real analytic and algebraic geometry (Trento, 1992) (pp. 197-212). Berlin: de Gruyter. Roth, B. (1962). A generalization of Burmester theory: Nine-point path generation of geared five-bar mechanisms with gear ratio plus and minus one. PhD thesis, Columbia University. Roth, B., & Freudenstein, F. (1963). Synthesis of path-generating mechanisms by numerical means. J. Eng. Industry, 298-306. Trans. ASME, vol. 85, Series B. Roth, B., Rastegar, J., & Scheinman, V. (1974). On the design of computer controlled manipulators. On the Theory and Practice of Robots and Manipulators: First CSIM-IFToMM Symposium (pp. 93-113). Springer-Verlag. Rump, S. M. (1999). INTLAB - INTerval LABoratory. In T. Csendes (Ed.), Developments in reliable computing, Proc. of (SCAN-98), Budapest, September 22-25, 1998 (pp. 77-104). Dordrecht: Kluwer Academic Publishers. Rupprecht, D. (2004). Semi-numerical absolute factorization of polynomials with integer coefficients. J. Symbolic Comput., 37(5), 557-574. Sasaki, T. (2001). Approximate multivariate polynomial factorization based on zero-sum relations. In B. Mourrain (Ed.), Proceedings of the 2001 international symposium on symbolic and algebraic computation (ISSAC 2001) (pp. 284-291). ACM. Schenck, H. (2003). Computational algebraic geometry, Vol. 58 of London Mathematical Society Student Texts. Cambridge: Cambridge University Press. Shiftman, B., & Sommese, A. J. (1985). Vanishing theorems on complex manifolds, Vol. 56 of Progress in Mathematics. Boston, MA: Birkhauser Boston Inc. Sommese, A. J., & Verschelde, J. (2000). Numerical homotopies to compute generic points on positive dimensional algebraic sets. J. Complexity, 16(3), 572-602. Complexity theory, real machines, and homotopy (Oxford, 1999). Sommese, A. J., Verschelde, J., & Wampler, C. W. (2001a). Numerical decomposition of the solution sets of polynomial systems into irreducible components. SIAM J. Numer. Anal., 38(6), 2022-2046. Sommese, A. J., Verschelde, J., & Wampler, C. W. (2001b). Numerical irreducible decomposition using projections from points on the components. In Symbolic computation: solving equations in algebra, geometry, and engineering (South Hadley, MA, 2000), Vol. 286 of Contemp. Math. (pp. 37-51). Providence, RI: Amer. Math. Soc. Sommese, A. J., Verschelde, J., & Wampler, C. W. (2001c). Using monodromy to decompose solution sets of polynomial systems into irreducible components. In Applications of algebraic geometry to coding theory, physics and computation (Eilat, 2001), Vol. 36 of NATO Sci. Ser. II Math. Phys. Chem. (pp. 297-315). Dordrecht: Kluwer Acad. Publ.

392

Numerical Solution of Systems of Polynomials Arising in Engineering and Science

Sommese, A. J., Verschelde, J., & Wampler, C. W. (2002a). A method for tracking singular paths with application to the numerical irreducible decomposition. In Algebraic geometry (pp. 329-345). Berlin: de Gruyter. Sommese, A. J., Verschelde, J., & Wampler, C W. (2002b). Symmetric functions applied to decomposing solution sets of polynomial systems. SIAM J. Numer. Anal, 40(6), 2026-2046. Sommese, A. J., Verschelde, J., & Wampler, C. W. (2003). Numerical irreducible decomposition using PHCpack. In Algebra, geometry, and software systems (pp. 109-129). Berlin: Springer. Sommese, A. J., Verschelde, J., & Wampler, C. W. (2004a). Advances in polynomial continuation for solving problems in kinematics. ASME J. Mech. Design, 126(2), 262-268. Sommese, A. J., Verschelde, J., & Wampler, C. W. (2004b). Homotopies for intersecting solution components of polynomial systems. SIAM J. Numer. Anal., 42(4), 1552-1571. Sommese, A. J., Verschelde, J., & Wampler, C. W. (2004c). An intrinsic homotopy for intersecting algebraic varieties. J. Complexity, to appear. Sommese, A. J., Verschelde, J., & Wampler, C. W. (2004d). Numerical factorization of multivariate complex polynomials. Theoretical Computer Science, 315, 651— 669. Sommese, A. J., Verschelde, J., & Wampler, C. W. (2004e). Solving polynomial systems equation by equation, in preparation. Sommese, A. J., & Wampler, C. W. (1996). Numerical algebraic geometry. In The mathematics of numerical analysis (Park City, UT, 1995), Vol. 32 of Lectures in Appi Math. (pp. 749-763). Providence, RI: Amer. Math. Soc. Sosonkina, M., Watson, L. T., & Stewart, D. E. (1996). Note on the end game in homotopy zero curve tracking. ACM Trans. Math. Software, 22(3), 281-287. Sreenivasan, S. V., & Nanua, P. (1992). Solution of the direct position kinematics problem of the general Stewart platform using advanced polynomial continuation. DE-Vol. 45, Robotics, Spatial Mechanisms, and Mechanical Systems (pp. 99-106). ASME. Sreenivasan, S. V., Waldron, K. J., & Nanua, P. (1994). Closed-form direct displacement analysis of a 6-6 Stewart platform. Mechanism Machine Theory, 29(6), 855-864. Stetter, H. J. (2004). Numerical polynomial algebra. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM). Stoer, J., & Bulirsch, R. (2002). Introduction to numerical analysis, Vol. 12 of Texts in Applied Mathematics. New York: Springer-Verlag, third edition. Translated from the German by R. Bartels, W. Gautschi and C. Witzgall. Sturmfels, B. (2002). Solving systems of polynomial equations, Vol. 97 of CBMS Regional Conference Series in Mathematics. Published for the Conference Board of the Mathematical Sciences, Washington, DC.

Bibliography

393

Sturmfels, B., & Zelevinsky, A. (1994). Multigraded resultants of Sylvester type. J. of Algebra, 163(1), 115-127. Su, H.-J., Wampler, C. W., & McCarthy, J. M. (2004). Geometric design of cylindric PRS serial chains. ASME J. Mech. Design, 126(2), 269-277. Tsai, L. W. (1999). Robot analysis: the mechanics of serial and parallel manipulators. New York: John Wiley & Sons Inc. Tsai, L. W., & Lu, J.-J. (1989). Coupler-point curve synthesis using homotopy methods. In B. Ravani (Ed.), Advances in Design Automation-1989: Mechanical Systems Analysis, Design and Simulation, Vol. DE-Vol. 19-3 (pp. 417-424). ASME. Tsai, L. W., & Morgan, A. P. (1985). Solving the kinematics of the most general six- and five-degree-of-freedom manipulators by continuation methods. ASME J. Mech., Trans., Auto. Design, 107, 48-57. van der Waerden, B. L. (1949). Modern Algebra. Vol. I. New York, N. Y.: Frederick Ungar Publishing Co. Translated from the second revised German edition by Fred Blum, With revisions and additions by the author. van der Waerden, B. L. (1950). Modern Algebra. Vol. II. New York, N. Y.: Frederick Ungar Publishing Co. Translated from the first German edition by Theodore Benac. Verschelde, J. (1996). Homotopy continuation methods for solving polynomial systems. PhD thesis, Katholieke Universiteit Leuven. Verschelde, J. (1999). Algorithm 795: PHCpack: A general-purpose solver for polynomial systems by homotopy continuation. A CM Trans, on Math. Software, 25(2), 251-276. Verschelde, J. (2000). Toric Newton method for polynomial homotopies. J. Symbolic Comput., £9(4-5), 777-793. Symbolic computation in algebra, analysis, and geometry (Berkeley, CA, 1998). Verschelde, J., & Cools, R. (1993). Symbolic homotopy construction. Appl. Algebra Engrg. Comm. Comput., ^(3), 169-183. Verschelde, J., Gatermann, K., & Cools, R. (1996). Mixed-volume computation by dynamic lifting applied to polynomial system solving. Discrete Comput. Geom., 16(1), 69-112. Verschelde, J., Verlinden, P., & Cools, R. (1994). Homotopies exploiting Newton polytopes for solving sparse polynomial systems. SI AM J. Numer. Anal., 31 (3), 915-930. Verschelde, J., & Wang, Y. (2004). Computing feedback laws for linear systems with a parallel Pieri homotopy. In Y. Yang (Ed.), Proceedings of 2004 International Conference on Parallel Processing Workshops, August 15-18, 2004 (PP- 222-229). IEEE. Walker, R. J. (1962). Algebraic curves. Dover, New York. Wampler, C. W. (1992). Bezout number calculations for multi-homogeneous polynomial systems. Appl. Math. Comput, 51(2-3), 143-157.

394

Numerical Solution of Systems of Polynomials Arising in Engineering and Science

Wampler, C. W. (1994). An efficient start system for multihomogeneous polynomial continuation. Numer. Math., 66(4), 517-523. Wampler, C. W. (1996a). Forward displacement analysis of general six-in-parallel SPS (Stewart) platform manipulators using soma coordinates. Mechanism Machine Theory, 31, 331-337. Wampler, C. W. (1996b). Isotropic coordinates, circularity and Bezout numbers: planar kinematics from a new perspective. In J. M. McCarthy (Ed.), Proceedings of the 1996 ASME Design Engineering Technical Conference, Irvine, California August 18-22, 1996. American Society of Mechanical Engineers, CD-ROM. Also available as GM Technical Report, Publication R&D-8188., 1996. Wampler, C. W. (1999). Solving the kinematics of planar mechanisms. ASME J. Mech. Design, 121, 387-391. Wampler, C. W. (2001). Solving the kinematics of planar mechanisms by Dixon determinant and a complex-plane formulation. ASME J. Mech. Design, 123(3), 382-387. Wampler, C. W. (2004). Displacement analysis of spherical mechanisms having three or fewer loops. ASME J. Mech. Design, 126(1), 93-100. Wampler, C. W., & Morgan, A. P. (1993). Solving the kinematics of general 6R manipulators using polynomial continuation. In Robotics: applied mathematics and computational aspects (Loughborough, 1989), Vol. 41 of Inst. Math. Appl. Conf. Ser. New Ser. (pp. 57-69). New York: Oxford Univ. Press. Wampler, C. W., Morgan, A. P., & Sommese, A. J. (1990). Numerical continuation methods for solving polynomial systems arising in kinematics. ASME J. Mech. Design, 112, 59-68. Wampler, C. W., Morgan, A. P., & Sommese, A. J. (1992). Complete solution of the nine-point path synthesis problem for four-bar linkages. ASME J. Mech. Design, 114, 153-159. Wampler, C. W., Morgan, A. P., & Sommese, A. J. (1997). Complete solution of the nine-point path synthesis problem for four-bar linkages - closure. ASME J. Mech. Design, 119, 150-152. Watson, L. T., Billups, S. C , k Morgan, A. P. (1987). Algorithm 652. HOMPACK: a suite of codes for globally convergent homotopy algorithms. ACM Trans. Math. Software, 13(3), 281-310. Watson, L. T., Sosonkina, M., Melville, R. C , Morgan, A. P., & Walker, H. F. (1997). Algorithm 777: HOMPACK90: a suite of Fortran 90 codes for globally convergent homotopy algorithms. ACM Trans. Math. Software, 23(4), 514-549. Weil, A. (1962). Foundations of algebraic geometry. Providence, R.I.: American Mathematical Society. Wilkinson, J. H. (1984). The perfidious polynomial. In Studies in numerical analysis, Vol. 24 of MAA Stud. Math. (pp. 1-28). Washington, DC: Math. Assoc. America. Wilkinson, J. H. (1994). Rounding errors in algebraic processes. New York: Dover

Bibliography

395

Publications Inc. Reprint of the 1963 original [Prentice-Hall, Englewood Cliffs, NJ]. Xu, Z.-B., Zhang, J.-S., & Wang, W. (1996). A cell exclusion algorithm for determining all the solutions of a nonlinear system of equations. Appl. Math. Comput., 80'(2-3), 181-208. Zhang, C.-D., & Song, S.-M. (1994). Forward position analysis of nearly general Stewart platform. ASME J. Mech. Design, 116(1), 54-60.

Index

Z r e g , 44, 215 # , xxii Sing(X), 44 Sing(Z), 306 C*, xxii (x,L), 328 A, xxii P N , 29 Gr(m,N), 325 V(f), 8 Opi(d), 342 \, i.e., setminus, xxii

Local Dimension, 251 LocalDimen, 251 Memberl, 268, 275 Member2, 269, 276 Monodromy, 269, 277 Rank, 240 TopDimen, 250 Trace, 270, 284 WitnessSuper, 247 WitnessSupi, 245 WitnessSupi(intrinsic), 246 algorithm for the rank of a system, 319 analysis, 163 analytic continuation, 278 analytic parameter spaces, 349 analytic Zariski open set, 350

affine algebraic set, 43, 47, 56, 207, 209 affine hyperplane, 232 affine space, 209 affine variety, 215 algebraic function, 210, 212 algebraic map, 208, 210, 212, 219, 220 algebraic probability one, 50 algebraic set, 43, 44, 207, 209 affine, see affine algebraic set constructible set, see constructive set projective, see projective algebraic set quasiprojective, see quasiprojective set algebraic set associated to / , 8 algebraic set of / see algebraic set associated to / , 8 algorithm Inclusion, 252 LocalDimen, 251 Equal, 253 IrrDecompl, 268 IrrDecomp2, 271 IrrDecompPure, 270, 284 JunkRemove, 269

base locus, 323 Bertini Theorems, 313, 323, 330-333 big system, 319 biholomorphic mapping, 301 biholomorphic to, 301 BKK bound, 139 body guidance, 163, 165 branched covering, 314 Buchberger's algorithm, 82 Burmester centers, 166 Burmester points, 166 cascade algorithm, 255, 259 Cauchy integral, 199 Cauchy integral endgame, 285 Cauchy integral method, 186, 187, 189 Cauchy's Lemma, 58 center of a projection, 213, 328 Chebychev polynomials, 65 397

398

Numerical Solution of Systems of Polynomials Arising in Engineering and Science

chemical equilibria, 152-154, 170 Cauchy integral method, see Cauchy Chern class, 343 integral method Chevalley's Theorem, 222 cluster method, see trace method classical topology, see complex topology, power-series method, see power-series 211 method cluster method, 187 trace method, see trace method coefficient, 5 endgame convergence radius, 180 coefficient-parameter homotopy, 91 endgame operating zone, 179, 182, 183, coefficient-parameter theory, 92 185 compact affine set, 220 equation-by-equation, 292 companion matrix, 4 Exclusion method, 68 complex analytic set, 301 extension theorems, 302 complex analytic space, 302 extrinsic slicing, 234 complex dimension, see dimension, 306 complex manifolds, 302 finite affine set, 210 complex projective space, see projective finite map, 312 space first Chern class, 342 complex topology, 211, 300 five-point path synthesis, 166, 174 condition number, 198 four-bar analysis, 164 cone with vertex x, 320 four-bar equations, 163 constellation of algebraic sets, 331, 332 four-bar function generation, 173 constructible algebraic set, 207, 208 four-bar linkages, 169 constructible set, 208, 209, 221 four-bar synthesis, 162, 163 convex polytope, 138 four-body guidance, 174 corank of a polynomial system, 239 fractional power series, 180 corank of an algebraic system, 318 function generation, 162, 164 coupler curve, 162 Fundamental Theorem of Algebra, 55 covering map, 314 cuspidal cubic, 282 gamma trick, 18, 94, 95 general point, 44 deflation, 190-193, 195 generic, 45, 46 degree, 230 simply, 332 degree of a polynomial, 5 generic Bezout number, 346, 351 desingularization, 310 generic factorization, 316, 317 diagonal intersection, 289 generic line, 46 differentiable manifold, 301 generic linear change of coordinates, 213 dimension, 44, 207, 216, 306 generic linear projection, 213, 324 upper semicontinuity, see upper generic point, 44 semicontinuity of dimension generic projection, see generic linear dimension of a germ, 309 projection dimensional complex manifold, 302 generic root count, 346, 351 discriminant, 57 generic with respect to an algebraic set, disk, 58 233 Dixon determinant, 77 generically, 45 dominant map, 222, 311 genericity, 43 dual curve, 338 germ, 308 dimension of a, 309 elementary symmetric functions, 280 irreducible, 309 elimination methods, 72 germ of a complex analytic set, 308 endgame, 177 germ of an affine algebraic set, 308

399

Index germ of an analytic set, 308 germs, 181 Grobner bases, 81 Grobner basis, 82 graph of a map, 219 Grassmannian, 325, 326 Grauert's Proper Mapping Theorem, 311 ground link, 162 grounded link, 13 growth estimates, 60 Hartogs' Theorem, 302, 303 heuristic eliminant, 79 hidden variable resultant, 73 Hironaka Desingularization Theorem, 310 holomorphic function, 300 holomorphic mapping, 301 homogeneous coordinates, xxii, 29 homogeneous polynomial, 33, 34 homogeneous polynomials, 218 homotopy continuation method, 15 homotopy membership test, 275 hyperplane, 232 hyperplane at infinity, 320, 327, 335-337 image of an irreducible set, 222 Implicit Function Theorem, 304 interval arithmetic, 201 intrinsic slicing, 234 irreducible algebraic set, 44, 207, 215 irreducible at a point, 309 irreducible component, 56, 207 irreducible decomposition, 56, 207, 215, 219 irreducible germ, 309 dimension of an, 309 irreducible witness sets, 230 isomorphic, 210, 212 isotropic coordinates, 160 joint offset, 158 junk points, 245, 249 Laurent monomial, 138 Laurent polynomial, 139 level i nonsolutions, 258 line at infinity, 33 line bundle, 341, 342 linear projection, 213, 324 generic, see generic linear projection

linear projections, 212 linear slicing, 231 link length, 158 locally irreducible, 309 losing the endgame, 188 manifold, 301 manifold point, 44, 306 map finite, 312 proper, 212 maximum principle, 304, 311 membership test, 266 Minkowski sum, 139 mixed strategy, 150 mixed volume, 138, 140 monodromy, 275-277, 339, 348 monodromy action, 278 monomial, 5 Mount Everest of Kinematics, see six-revolute serial-link robots multidegree notation, xxi, 5, 301, 322 multihomogeneous polynomial, 35 multiplicity, 8, 209, 223, 224, 236 multiprojective space, 35 Nash equilibria, 149-151, 170 nested parameter homotopy, 101 Newton polytope, 138 Newton's method, 17, 18, 24, 71, 177, 182 Newton-Raphson method, 17 nine-point path synthesis problem, 112, 161, 167 Noether Normalization Theorem, 214, 336 nonreduced, 236 nonsolutions, 258 normal, 281, 303, 308 normal complex analytic space, 308 normalization, 189, 311 Nullstellensatz, 307 numerical algebraic geometry, vii, 227-229, 241 numerical elimination theory, 266 numerical irreducible decomposition, 228, 230, 231, 253, 265 overdetermined, 241 parameter homotopy, see coefficient-parameter homotopy

400

Numerical Solution of Systems of Polynomials Arising in Engineering and Science

patch switching, 38 path generation, 162 path synthesis problems, 166 Plucker embedding, 326 point at infinity, 30 polyhedron, 138 polynomial system, 209 polytope, 138 polytope root count, 139 power-series endgame, 199, 285 power-series method, 183, 185, 186, 189, 194 precision-point methods, 163 primary decomposition, 216 probabilistic algorithm, 249 probability one, 43, 50, 313 probability-one methods, 207 projective transformation, 39 projective algebraic set, 34, 207, 217 projective line, 30 projective plane, 32 projective rank of an algebraic system, 319, 320, 330 projective set, 43 projective space, 27-30 projective transformation, 38, 40, 198 proper, 189 proper algebraic map, 212 proper map, 212 proper mapping theorem, 311 Puiseux's Theorem, 310 pure-dimensional, 216, 219

Riemann Bounded Extension Theorem, 303

quadric surface, 334 quasiprojective algebraic set, 44, 207, 208 quasiprojective set, see quasiprojective algebraic set, 219

sampling, 272, 273 Sard's Theorem, 313 secant variety, 335 section of a line bundle, 218 Segre embedding, 293, 334, 335 set of indeterminacy, 317 seven-bar structures, 172 simply generic, 332 singular path tracking, 273, 284 singular point, 44, 306 singular set, 307 six-revolute inverse position, 172 six-revolute serial-link robots, 156 slicing, 231 smooth immersion, 279 smooth point, 44, 306 solution sets, 8 spanned, 342 square system, 241 Stein factorization Theorem, 312 Stewart-Gough forward kinematics, 154 Stewart-Gough platform robots, ix, 101, 104-106, 108, 109, 111, 113-115, 154, 171 straight-line function, 6, 11, 12, 48, 70, 85, 362 submatrix, 332 Sylvester determinant, 56 Sylvester matrix, 65 Sylvester Resultant, 57 symmetric group, 340 synthesis, 163 synthesis problems, 164, 169 system of coordinates, 304

radical, 216 rank of a polynomial system, 228, 239, 240 rank of an algebraic system, 318, 319, 329 rational mapping, 317, 338 real dimension, 210, 306 reduced, 236 reduction to the diagonal, 290 regular point, 215, 306 Remmert-Stein Factorization Theorem see Stein Factorization Theorem, 312 resultant, 57, 73

topologically unibranch, 309 topology, 211 classical, see complex topology complex, see complex topology Zariski, see Zariski topology total degree of a polynomial, 5 trace, 187, 279-281 trace method, 187, 189 trace test, 279 trigonometric equations, 7 twist angle, 158

Index

underdetermined, 241 universal field, 52 universal function, 323 universal system, 323 upper semicontinuity of dimension, 312 variety, 8 vector bundle, 341, 343 Veronese embedding, 334 Wilkinson polynomials, 11 winding number, 180, 182, 183 witness point superset, 244, 245, 255 witness set, see witness point set, 8, 229, 235 witness superset, 253, 256 Zariski closed set, 211 Zariski open set, 92, 211 Zariski topology, 211, 221

401