W!HflUHlMWHW“WI“WWW“W1M 130 120 __THS VHEai‘S unwea l\\\\\\\\\\\ W \\\\\\\\\\\\\\\\\l\\‘.‘ 3 129300 008952 l\2\\\\\\\\\\\\\l This is to certify that the dissertation entitled HO ”LC-to Pj 'mefiLOCJS 5C3? Scl'v'r‘n‘cj deficient POijnomicd S‘thfi’émS presented by \[UA/L’CT, 7< (A 08 H E/V has been accepted towards fulfillment of the requirements for Pt’l . D. degree in l!£ gj' [L mQ‘tZCS 0 Major ’rofessor I l, LIBRARY Michigan State 1 University p 1- PLACE IN RETURN BOX to remove this checkout from your record. TO AVOID FINES return on or before date due. I DATE DUE DATE DUE DATE DUE Jl L__¥ __'| MSU Is An Affirmative AotiorVEquel Opportunity Institution cmmhf HOMOTOPY METHODS FOR SOLVING DEFICIENT POLYNOMIAL SYSTEMS By Xiaoshen Wang A DISSERTATION Submitted to Michigan State University in partial fulfillment of the requirements for the degree of DOCTOR OF PHILOSOPHY Department of Mathematics 1990 ABSTRACT HOMOTOPY METHODS FOR SOLVING DEFICIENT POLYNOMIAL SYSTEMS By Xiaoshen Wang By a deficient polynomial system of n polynomial equation in n unknowns we mean a system that has fewer solutions than that predicted by the Bézout number of the corresponding homogeneous system. Sometimes if the system is m-homogenized, the Bézout number can be considerably reduced. In this paper, we introduce homo- topies for numerically determining all isolated solutions of deficient m-homogeneous systems. The homotopy H (2:,t) is chosen such that H (3,0) = Q is a trivial system and H (2:, 1) = P is the system to be solved and such that the subschemes or the number of solutions of H (x,t) at infinity remains invariant when t varies in [0,1). Thus the number of paths to be followed is reduced. To my wife Yingni. iii ACKNOWLEDGMENTS I would like to thank Professor Tien Yien Li, my dissertation advisor, for his con- stant encouragement and support during my graduate study at Michigan State Uni- versity. I would also like to thank him for suggesting the problem and the helpful directions which made this work possible. I would like to thank Professor Bernd Ulrich under whose guidance I took reading course in algebraic geometry which laid the foundation for this research. I would also like to thank my dissertation committee members Prof. R. Hill, Prof. W. Kuan, Prof. C. Seebeck and Prof. D. Yen for their valuable suggestions and their time. iv Contents 1 Introduction 1 1.1 Linear Homotopies ............................ 1 1.2 Nonlinear Homotopies .......................... 5 1.3 Preliminaries ............................... 5 2 Linear Homotopies 8 2.1 Main Results ............................... 8 2.2 Applications ................................ 16 3 Nonlinear Homotopies 22 3.1 Main Results ............................... 22 3.2 Applications ................................ 25 Appendix 36 References 38 List of Tables 2.1 Solutions to (2.14) ............................ 17 2.2 Solutions to (2.18) with given parameters ............... 20 2.3 Solutions to (2.24) ............................ 21 3.1 Solutions to (3.7) with given parameters ................ 34 vi List of Figures 1.1 The four solution paths. ......................... vii Chapter 1 Introduction 1 . 1 Linear Homotopies Let P(a:) = 0 be a system of n polynomial equations in n unknowns, where P 2 (p1, . . . ,pn) and m = (x1, . . . , 23,.) We want to find all isolated solutions of p1(a:1,...,:c,,) = 0 ' (1.1) pn(:rl,...,:r,,) = 0 in C". The homotopy continuation method for solving this system is to find a system H(a:,t) =0 (1.2) such that the solutions of H(a:,0) = 0 are known, H(:r, 1) = P(:r) and then to follow the curves in the real variable t which make up the solution set of H(:I:,t) = 0. (1.3) More precisely, we choose H(a:, t) such that the following three assumptions hold: 1. (Triviality) The solutions of H (2:, 0) = O are known. 2. (Smoothness) The solution set of H (x,t) = 0 for O S t < 1 consists of a finite number of smooth paths, each parameterized by t in [0,1). 3. (Accessibility) Every isolated solution of H (2:,1) = P(a:) = 0 is reached by some path originating at t = 0. It follows that this path starts at a solution of H(:L',0) = Q(:L‘) 7- 0. When the three assumptions hold, we try to follow the solution paths from the initial points (known because of property 1) at t = 0 to all solutions of the original problem P(:r) = O at t = 1 . It is important to realize that even though Properties (1) — (3) imply that each solution of P(:c) = 0 will lie at the end of a solution path, it is also consistent with these properties that some of the paths may diverge to infinity as the parameter t approaches 1. This approach has the virtue of locating all isolated solutions of the system P(:r) = 0. A typical choice of H that satisfies the three properties [9,16,21] is H(2:,t) = (1 —t)cQ+tP, (1.4) where (11(33) = (173“ -1) W) = (x3: -1) where d1, . . . ,dn are the degrees of p1(:1:),. . . , . . . ,pn(x), and c is a random complex number . In this case, the number of paths which need to be followed to arrive at all solutions of P(.r) = 0 is the product d 5 d1, . - - ,dn. This number, often called the Bézout number of the corresponding homogeneous system, is a classical upper bound on the number of isolated solutions, counting multiplicities. However, in most practical cases that we have seen, the number of solutions of (1.1) can turn out to be smaller than d, and in some cases only a small fraction of d. Such systems are called deficient. When applying the homotopy continuation method to a deficient system, by sending out (1 paths in search of solutions, the paths which do not converge to solutions of (1.1) will go to infinity, representing wasted computation. 2 For deficient systems, various homotopies have been introduced ([10,11,12, 17,19]). Sometimes we can m-homogenize (1.1) , to get a smaller Bézout number ([17]) and hence if we use a homotopy with same m-homogeneous structure as P we can reduce number of paths needed to be followed. Given a polynomial p of degree d in the n variables :31, . . . , 2:", we can define its homogenization 13(30, . . . ,3") = (2:0)d p(:rl/:z:o, . . . , :rn/xo). For polynomial system P = (p1, . . . , p") we use P to represent ([51, . . . , fin). A typical suggestion in [10], [11] and [12] for deficient polynomial system is to choose Q(:c) in (1.4) which shares a similar type of deficiency as P(:r), with the basic assumption that the zeros of Q(a:) at infinity, i.e. zeros of Q(a:) with 1:0 = 0, are nonsingular. Then, we need follow fewer solution paths to obtain all isolated solutions of P. However a flaw was discovered in one of main theorems of [19]. Basically they claimed a general result that the nonsingularity of the zeros of Q(:r) at infinity can be replaced by the following. Let the common zeros of P and Q in (1.4) at infinity be denoted by S. If for each s E S the multiplicity of s as a solution of Q08) = 0 is less than or equal to that of s as a solution of P(a:) = 0 and all other zeros of Q(:r) are isolated and nonsingular, then for ‘almost all’ a E C, by following the solution paths of 1:1(x,t) = a(1—t)Q(a:)+tP(a:) = 0 (1.5) starting from the isolated zeros of Q(:r) outside 5', one can obtain all isolated zeros of P(a:) = 0 outside 5'. This assertion can be shown to be in error as the following example indicates. Example: Let P = (p1,p2) and Q = (q1,q2) be defined as P1($1,$2) = $3 + $1 (1.6) P2($1,$2) = $3 + $2 91(31,$2) = 117;— 1 (1.7) 92($I,$2) = 113% + 331552- 3 (0,1,0) (1,1,—1) \ (1,0,0) Figure 1.1: The four solution paths. The nontrivial common solution set of P(:ro,:rl,:r2) = 0 and Q(a:o,:c1,:1:2) = 0 at infinity is (0, 1, 0) with multiplicity 2. However, for any nonzero a E C which is not a negative real number, by following the solution paths of (1.4) starting from the 2 zeros of Q in affine space (1, —1, 1) and (1, 1, —1), one can only find one of the isolated zeros of P(:z:), (1, —1, —1), in affine space. For a = .59032965 + .15799344i the computation results are shown in Figure 1.1. The solution path starting with (1, —1, 1) can reach (1, -1, -1) and the solution path starting from (1,1, —1) goes to infinity as t tends to 1. A proof of this assertion for almost all a is given in an appendix. In view of this counterexample, we suggest an alternative which guarantees the accessibility of the homotopy for deficient polynomial systems. In our homotopy, we choose Q(a:) in such a way that its subscheme at infinity contains the subscheme of P(a:) at infinity. Then, for ‘almost all’ a E C, the subschemes of f1(a:,t) in (1.4) at infinity remain the same for all t 6 [0,1). Consequently, solution paths of (1.4) originated at zeros of Q(a:) in affine space stay in affine space for all t 6 [0,1). As a result, the typical assumption of nonsingularity of Q(:r) at infinity in [10,11,12] can be dropped. The main results are stated and proved in Chapter 2 for general m—homogeneous deficient polynomial systems . When m = 1 the conditions given in Theorem 2.1 and Proposition 2.1 are equivalent to the condition (2.4) of Theorem 2.3 in [12](See [14] for the proof). However, the condition here is much easier to be verified. In chapter 2, we also give several examples for which our main results apply. 1.2 Nonlinear Homotopies Many polynomial systems in applications are a family of systems parameterized by q E C‘, and for generic family members the number of solutions at infinity are the same. To deal with this kind of deficient systems, various homotopies have been introduced ([13,18] ). But each of those homotopies can be used to solve only a small group of systems in that family. In Chapter 3, we suggest an alternative which can be used to solve the whole family of systems. We also show how the result can be used to solve a very important problem arising from the robot arm design. 1.3 Preliminaries The complex n-space C" can be naturally embedded in complex projective space P. = {(mo,...,xn) e cn+1\(o,....o>}/~ where the equivalent relation “~” is given by 3 ~ y if a: = cy for nonzero c E C. Similarly, the space N = C"1 x ~ .. x Ck'" can be naturally embedded in M = P"1 x - - - x Pk'". A point (y1,. . .,ym) in N with y,- = (y{,. . . ,yzi),i = 1, . . . ,m corresponds to a point (21,...,zm) in M with z,- = (23,...,z;;..) and 23:1,i=1,...,m. The set of such points in M is usually called the affine space in this setting. The points in M with at least one 23 = 0 are called the points at infinity. Given a polynomial p in the n variables 2:1, . . . ,asn, if we partition the variables into m groups y1 = (:r],...,z},l),y2 = (x¥,...,:cfi2),...,ym = (x?,...,:r;”m) with k1 + - - - + km = n and let d,- be the degree of p with respect to y;(more precisely, to the variables in y,), then we can define its m-homogenization as P(zl,°'° ’27") = (2(1))d1 X X (Zan)dmp(yl/z(1)a°' .,ym/z6n) which is homogeneous with respect to each 2, = (26,...,z;;i),i = 1,.. . ,m. Here 2;: = mg, forj :,£ 0. Such a polynomial is said to be m-homogeneous. To illustrate this definition, let us consider the polynomial p()\,:r1, . . . ,xn) = /\2(a1:r1 + - - - + anal:n — a) +/\(b1$1 + ' - ° + bnan — b) + (Cl-131 + '- - + Cnxn - C)- We may let y1 = (/\),y2 = (2:1, . . . ,3") and 21 = (A0,A),zg = (170,31, . . . ,3"). The de- gree of p is 2 with respect to yl and is 1 with respect to yg. Hence its 2-homogenization is [3(A0, A,:r0,:c1, . . . ,atn) = /\2(a1:r1 + --- + anxn — are) +A/\0(b1.’131+ ° ° ° + bnxn '— (3170) + A3(C1$1 + ' ' ' + Cnxn — 61:0), which is homogeneous with respect to (A0, A) and (2:0, 171, . . . , 1:”). For m-homogeneous polynomial systems P(z) = 0, we are interested in the solutions in P"1 x x Pk'". So often, by abuse of terminology, we say 2 E P"1 x x Pk'". For 2,- = (zé, . . . , 2}“) ,i = 1, . . . ,m, let S = C[z(§, z], . . . ,zf‘m] be the polynomial ring of the variables in z,’s with complex coefficients. If A is an ideal generate by m-homogeneous poly- nomials and T is a prime ideal of 5', denote by AT the ideal {f E S I hf E A for some m-homogeneous h g T}. For a point z = (21, . . . ,zm) E P"1 x x Pkm, let 1,, denote the maximal ideal {f E S I f(2) = 0}. If f1, . . . , fn are m-homogeneous polynomials in the variables (21, . . . , 2",), let V(f1, . . . , fr) he the common zero set of f1,...,f,. in P"1 x X Pk'". We say a point y E V(f1,...,f,) is nonsingular if 5(f1,---,fr) _ . k, t... ranka(21,.n,zm)_c0dzmy(V(f1,...,f,.),P xonxP ) where codim denotes complex codimension. We use (f1, . . . , f,) to represent the ideal generated by f1, . . . ,f,. To be more precise, (f1, . . .,f,) is the set of all polynomials of form 2: gif.’ 6 where the gg’s are polynomials in S. For a 2-homogeneous polynomial system P = (151, . . .,15,,) in the variables 2; = (23,...,z;;..) i = 1,2 with k1 = k , k2 = l, and k +3 :2 n and deg 13,- : (d‘i,d§), i = 1, - - - ,n the Bézout number B of this system is ([6, p. 146]) the coefficient of akfl‘ in the product it H(d‘ia + dam- (1.8) i=1 That means the number of isolated solutions of the system in P" x P’, counting multiplicities, is at most B. For m > 2 we have similar formula(See[17]). Chapter 2 Linear Homotopies 2.1 Main Results Given the system P(:1:) = (p1(x),...,pn(a:)) in (1.1) let Q(:1:) = (q1(:r),...,qn(x)) and H(a,:r,t) = (1 — t)aQ(:r) +tP(a:), a E C. (2.1) Here, we consider at E C"1 x C"2 x x Ck'" with k1 + k2 + + km = n, t real , H : C"1 x C"2 x x Ck'" ———> C" and degp, = degq,,i=1,...,n, here by degree we mean the m-degree. Let PI(a, z,t) = (1 -— t)aQ(z) + t P(z) t E [0,1], (2.2) which is the m-homogenization of (2.1). Let (Q) = (61],. . .,(j,,) and (P) = (151,. . .,13,,) and M = P"1 X .. - x Pk'". The main result is the following. Theorem 2.1 Suppose that the polynomial system Q in (2.?) satisfies the following assumptions: (1) for every point z E M at infinity, (62)" 2 (13)"; (2) the set T = {the points ofV(('1'1,.. .,ijn) C M in afi‘ine space} consists of non- singular isolated points (1:1, . . . , 3:". Then, there exists an open dense subset D ofC with full measure, such that for a“1 chosen from D, we have a. (Smoothness) For each isolated zero at" E T,k = 1,...,r there is a function x"(t) : [0, 1] —+ M which is analytic and contained in affine space for allt in [0, 1) and satisfies H(a,:1:"(t),t) = 0. b. (Accessibility) Each isolated solution of P(:1:) = 0 in the affine space is reached by :r"(t) for some k at t = 1. Remark 2.1 Ifz E V(131,. . . ,jin) then there exists h E (131, . . . ,pn) such that h(z) yé 0, i.e. h g 1,.. Thus, (13)1= = {f e s | fh e (P) for some h g! 1.} = 5. Hence, condition (1) above implies that every point of V(q1, . . . , (7,.) at infinity is also a point of V051, . . . ,pn). By the same argument, ifz E V(§1, . . . ,6”) then (Q)I‘ = S and {1) is obvious. So, in order to check the condition (I) of Theorem 2.1 one only needs to check this condition for those points at infinity which lie in V(q~1,. . . ,qn). Con- sequently, the condition (1) implies that the subscheme at infinity of the polynomial system Q(z) contains the subscheme of P(z) at infinity. (For general definitions and properties of scheme and subscheme, see [7, pp. 60-190].} Remark 2.2 By a straightforward verification one can easily see that ((Q)’*)“ = (Q)"- Hence, 17(0)" 2 (13), than (0)" 2 (13)". Remark 2.3 In the counterexample (1.5), (1.6) we give in Chapter I, I31($0,$1,$2) = 133+ :1:le 132(330, $1, $2) = mg + :7:ng C'1'1(5l?o,€131, $2) = 133+ .103 51.20130, 331,332) = so: + :3le. At 2 = ($0,231,552) = (0,1,0) 6 bfP2,(Q)" 2 (PW This can be shown as follows. Since 132 —p1 = x0(:r2 — 2:1) E (15)“ and $2 — :51 # 0 at z = (0,1,0),a:o E (P)I‘. Thus at: E (P)I'.So (P)" = (2:0,:23). Since (151 — [32)x2 — [311:1 = 223051 + 9:2) E (Q)I‘ and 31+ 1:; 7f 0 at 2,1236 (Q)". Therefore (Q)I‘ = ($2,333). Apparently, (Q)" 2 (15)“. 9 We need several lemmas for the proof of the theorem. Let R be a ring of poly- nomials (perhaps a quotient of S) and q a prime ideal of R. We denote by R01) the localization of R at q. The local ring R(q) is made up of “formal fractions” {i I f E R, 9 Eq, deg f = deg g with respect to each 2,, i = 1,...,m} 9 such that 5—: = £- if and only if flgg = fggl in R. Lemma 2.1 If ~ 0} such that for any y at infinity and c E D1 (61 + 0151, - - . Kin + 61372),” = (Qlly- (2-4) Proof. From (2.3), for any y at infinity we have ayp,=b§’,q1+...+b?nqm i=1,...,n where af’, bf,- E S and a?(y) # 0, i=1,...,n, j :2 1,...,n. Thus, ai(<'1'1 + 6151) = (at + Obit) (it + - - . + cbi’n (in. ' (2.5) 0?,(51'71 + 615”) : cbi’fl q, + . . . + (a3, + cbg’m) (in for any c E C. For f E (q1+c131, . . . ,q'n+c;3,,)’v there exists h E S, such that h(y) yé 0, and fh = Zn: dim; + 615;), (2.6) i=1 where d.- E S, i = 1, . . . , n. Multiplying both sides of (2.6) by a? x . . . x a% and using (2.5), we have f E (Q)Iv. Hence, (61 + CPD ' ' ' iqn + Cfin)ly g 1y 10 for any c E C. For the reverse inclusion, let P - ai(Z) + cbit(2) "° Obin(z) Cbiik) Ay(c, z) = (2 7) 055110) 031(2) + 053mb) then (2.5) can be written as (Ii/((31 + €151) q~1 ' = Ay(c, z) E . (2.8) _ “#671 + CPn) J . 6n . Let By(c, 2) be the determinant of Ay(c, z) and Ade, 2) be the adjoint matrix of Ay(c, z). Multiplying both sides of (2.8) by Ay(c, 2) yields, r ~ ~ 1 ' ' ai’(q1 + 0191) <11 Ade, z) E = By(c, z) E . (2.9) “31(4): + 61511) 91: b cl t- .l Consider By(c,z) as a polynomial in C x M. Denote its homogenization with respect to c in P1 x M by By(co,c, 2). Let B be the ideal generated by the By’s. Its zero set at infinity, denoted by v, is an algebraic set. Let in : P1 x M —-t P1 be the natural projection. By the proper mapping theorem ([5, p.64]) 1rl(v) is an algebraic set in P1. The only algebraic subsets in P1 are the empty set, the finite-element subsets and P1 itself. Since By(1,0,y) 915 0 for any y at infinity, (1,0) E 7r1(v). So 1r1(v) is a proper algebraic set of P1 and hence is a finite set {(c,-,d,-), i = 1,. . . , 1:}. Let F1 = {0,- = arg (it) | c,- 75 0} and D1 = {reio E C | r > 0, 0 E [0,27r)\F1}. Then for any y at infinity and c E 01, (1,c,y) E v, that is, there exists b E B such that b(1,c,y) 31$ 0. Since b E B, b = ngy, + + g,By, where y1,...,ys are some points at infinity and g1, . . . , g, are polynomials. 11 From (2.9) we see that bq'; E (q, + cp1,...,q,, + cpn), i = 1,...,n. Hence, (Q) S; (61 + 0151, - - - , (in + 015,1)!" and we conclude that, by Remark 2.2, (QlIy _C. (<71 + C151, - . - ,fin + Cfinlly- This completes the proof. C1 Under the same assumption of Lemma 2.1, we have the following three corollaries: Corollary 2.1 For fixed nonzero a, with a"1 E D1 and any y at infinity (H(a,z,t))’v = (Q)’v for all t 6 [0,1). (2.10) Proof. From (2.2), Ii(a,z,t) = (1 — t)aQ(z) + tP(z) = (1 — t)a (Q(z) + ([13:30). Since a‘1 E D1, for t 9é 1, (Ti—{)3 E DI. The assertion follows. Cl Corollary 2.2 For fixed a"1 E D1, t E [0,1) and y at infinity, we have (I) the quotient rings S/(Iil(a,z,t)) and S/(Q) have the same localization at the maximal ideal]y = {f E S I f(y) = 0}. That is, (5/(H(a,z,t))>uy) = (S/(Qlltn)- Here I1, is considered as maximal ideal in S/(Iil(a,z,t)) and S/(Q) through canonical projections. (2) For any prime ideal q of S, considered as prime ideal in S/(B(a,z,t)) and S/(Q), with zero set V(q) lying at infinity, we have (S/>(9) = (S/(0) = ((5/(H(a,2,t))(1,))(q) = ((5/(Q))(1,)>(q) = (5/ 0 such that 0 <| A1 |< 61 implies A1 E B. And since (1,0, x"), k = 1,. . . ,r are nonsingular, there exists 0 < e < 61 such that for each 0 <[ A1 |< 8, Q + MP 2 0 has r isolated affine solutions x"()\1). We claim that for each k, ~ V(Q) n N n A, = <25- (2.12) Suppose this is not true. Then there is a point (1,0,20) E N 0 Ah. Since A), is connected and dim A), = 1, let c(s) be a curve such that c(0)=(1,0, 2°) and c(1)= (1, 0, x"). From (1) above, there are only finitely many (A0, A1) such that ()to, A1) can be in N D A), for suitable 2. Hence, there is 0 < so < 1 and 52 > 0 such that if 6 E (30,30 +52), c(6) E N and 7r1(c(6)) = (1,/\1) with |/\1| < 6. But then we have at least r+1 zeros of Q + MP in affine space, which leads to a contradiction. This completes the proof. Cl (Proof of Theorem 2.1.) 14 Let Tip, 2) = A0Q(z)+A1P(z) with A = (10,11) 6 P. A point (1,2) in P1 x M is said to be regular if and only if rank 7720, 2) = n. For each x", k = 1,. . . ,r in T, let A)c be the irreducible component of V(TT), the zero set of F in P1 X M, passing through x". Let Bk be the set of points in A)c which are nonregular. Nonregularity can be described in terms of vanishing subdeterminants of FAA, 2) which lead to a system of polynomial equations. Consequently, Bk is an algebraic set for each It. So 7r1(Bk) is a proper algebraic set in P1, because (1,0) E «1(Bk) by Lemma 2.2 and hence it is finite for each k. Let A := Ule 7rl(Bk) = {(c:,d:-) | i = 1,...,I}, F2 = {0,- = arg(i:fr'),i=1,...,1|c,- # 0} and D; 2 {ma9 E C | r > 0, 9 E [0,27r)\F2}. For a E C with a"1 E 0;, 11—33—6- E D2 for allt E [0,1). That is, (I’lthtF) E A, so, 772(1, (Fifi—0,2) is of rank n for any (1, (ti—5,2) E B1,. A repeat application of the Implicit Function Theorem on the affine representation of the homotopy t (1 — t)a’z) implies the smoothness property. For accessibility, it follows from Corollary 2.3 that 0 = B(a,z,t) = (1 — t)aQ(z) + tP(z) = (1 — t)a-H—(1, (2.13) for fixed a"1 E D1, the intersection schemes of B (a, z, t) at infinity are the same for all t E [0,1). By Proposition 9.1.2 and Example 9.1.10 of [6], for each t in [0, 1) the number of solutions of (2.13) in affine space are the same (= r). As a consequence, the x"(t)’s are the only solutions in affine space for each t E [0, 1). By a degree theory argument as in [3], or an algebraic argument as in [10], the accessibility property follows. By choosing D = D1 0 Dg, the proof of the theorem is completed. D The following proposition indicates that Theorem 2.1 is a generalization of the main result in [12]. Proposition 2.1 Suppose that the polynomial systems Q, P in (2.2) has the following properties: (1) every point of V(Q) at infinity is also a point of V(P); (2) the set T = {the points of V(Q) in affine space} consists of nonsingular isolated points. 15 Then for a nonsingular point z of V(Q) at infinity, (Q)I' 2 (P)I'. Proof For f E (P)" there exists h E S such that h(z) 75 0, and fh E (P). From con- dition (b), fh vanishes on the set of zeros of (Q) at infinity. Let x‘ = (x'1,. . . xi ) i = ’ n 1, . . . , r, be the isolated zeros of Q in C“, and m) =11 i mm -133) i=1 where e, E C, i = 1,...,n are chosen such that P(z) 75 0. It is easy to see that P(z‘) = 0 for each i = 1,. . . ,r, where z‘ is the corresponding point of x‘ in M, and th vanishes on V(Q). By the Nullstellensatz, (th)" E (Q) for some positive integer 11:. Since (Ph)k(z) 51$ 0, f" E (Q)I'. By Theorem 48 of [15], (Q)I' is a prime ideal. Hence, f E (62)“ which completes the proof. C] 2.2 Applications Example 2.1. Suppose we want to solve the system many) = xy+y+1=0 (2.14) 112017,?!) = $3312 - Icy +1 = 0. By considering (x,y) E C1 X C1, we may 2-homogenize (2.14) as 151($0,$,y0,3/) = xy + 3303/ + 1703/0 = 0 (2-15) 152(xo, 32,310.11) = $3312 — nit/yo + 33y?) = 0 where (x0,x,yo,y) E P1 X P1. Then this system P = (151,132) has 1 solution (0,1,1, 0) at infinity with multiplicity 2 and 3 affine solutions. Our starting system Q = (q1, q2) can be chosen as q1(:v,y) = xy+y+1=0 (2.16) (May) = $3.212 —— xy = 0. 16 Parameter a = —.13960695 — .6281187i Starting Point Solution Reached x y x y 0 —1 —.4301591 —1.7648765 2—1/2 + t/31/2—1/2 + t/31/2 —.78492 + 1.307138i —.1225614 + 74486092’ 3H/2 — «7.1/24 /2 — fii/2—.78492 —1.3071413i—.1225611 — .74486182‘ Table 2.1: Solutions to (2.14) Its 2-homogenization is 61(xo,x,yo,y) = $11 + 1:031 + $0310 = 0 62(330, 3719013!) = $3312 — 337121990 2 0. The system Q has 3 nonsingular solutions (x,y) = (0, —1), (-1/2 + x/3i/2, —1/2 + x/Si/Z) and (—1/2— \f3i/2, —1/2— JIM/2) and its solution at infinity is the same as that of P. Write (1'2 = xg with g = xzy2 -—x3yoy. Since x # 0 at z = (0,1,1,0),x E 12, so, 9 E (Q)I'. Further, q'lxy—g = xoy(xoyo+xy+xyo) E (Q)I’ and xoy0+xy+xyo 74 0 at 2 imply xoy E (Q)I'. Since xoyoél E (Q)I' xoyo) E (Q)" and thus {12 = q; + xo(x3y3) E (Q)I'. Along with 131 = a, E (Q)I', we have (Q)!2 2 (P)I‘. So Theorem 2.1 applies. It provides a homotopy and 3 paths, we have 231/3 = $031061 - $oy($y0 + beginning from the roots of (2.16), which lead to all roots of (2.14). The table 2.1 shows the computing result. The notion of m-homogeneous when m = 1 is the same as homogeneous. For ho- mogeneous polynomials f1, . . . , f, we use (f1, . . . , f,.)e to denote the subset of (f1 , . . . , fr) consisting of homogeneous polynomials of degree e. In [12], the following condition of P, Q in (2.2) is used to guarantee the accessibility of the “random product homotopy” paths: For each positive integer k, (ql,'°°aqnaxg)e 2 (P19---afina$3)e (2.17) 17 for all sufficiently large e. The condition (2.17) is equivalent to condition (1) in Theorem 2.1 when m = 1(See [14]). However, we shall illustrate in Example 2.2 that condition (1) in Theorem 2.1 can be much easier to verify. Example 2.2. The following system is the mathematical model of a lumped- parameter chemically reacting system [2]. p1(x1, x2,x3,x4) = —a1x1(1 — x3 — x4) + a2x3 — (x1 — b1) (2.18) P2($1,$2,$3, $4) = —as$2(1 — $3 — $4) + a4$4 — ($2 — b2) p3(x1, x2, x3, 3:4) '2 (113:1(1 — $3 — $4) — a2m3 — 0151:3174 p4(x1, x2, x3, x4) = a3x2(1 — x3 — x4) — a4x4 — a5x3x4. While the Bézout number of the corresponding homogeneous system of P = (p1, p2, p3, p4) is 16, for generic ag’s and (25,8 there are only 4 zeros of (2.18) in C4([2]). Define Q : (q11q2aq33q4) by q1(x1,x2,x3,x4) = (x1 — 1)(1 — x3 — x4) (2.19) q2(x1, x2, x3, x4) = (x2 - i)(2 — x3 — x4) (13(331, $2,133,934) = $1(2 - $3 - $4) + $3$4 ( 04 :61, $2,033.22) = ($2 +1)(1- x3 — x4) + 23334 The homogenization Q of Q is 61(20, x1, x2, x3, x4) = (x1 — xo)(xo — x3 — x.,) (2.20) 172m), x1,x2,x3, x4) = (x2 — ixo)(2xo — x3 — x4) §3($o, $1, :82, x3, x4) = 31(2330 - x3 — x4) + 323124 §4($o, $1, $2, $3, $4) = ($2 + $o)($o — $3 — $4) + $3134- The points of V(Q) at infinity are (xo,x1,x2,x3,x4) = (0,0,0,0,1),(0,0,0,1,0) and a line I = (0,x1,x2,0,0). The rank of 18 [ 1 —1 0 0 0‘ 8(qlvq2263aq4) _ Z 0 “'1 0 0 a($o,$1,$2,$3,$4) (0,0,0,0,1) 0 _1 0 1 0 _—1 0 —1 1 0‘ is 4 and hence, (0,0,0,0,1) is nonsingular, similarly for (0,0,0,1,0). These two points also belong to V(P). Further, the system (2.19) has 4 nonsingular isolated zeros: (x1,x2,x3,x4) = (1,—1,0,2),(1,—1,2,0),(0,i,0,1) and (0,i,1,0). So, Propo- sition 2.1 applies. That is, (duflzfiatitll’ 2 (21,22,2311301' for z = (0, 0,0,0, 1), (0,0, 0, 1,0). For 2 E I = (0,x1,x2,0,0), either x1 75 0 or 2:2 915 0, say x1 gé 0. Then x1 -— x0 7i 0 at 2. So, from (1'1, x0 — x3 — x, E (Q)I‘. (2.21) It follows, from (74,232., E (Q)1* and hence x1(2xo — x3 — x4) E (Q)I' from (73. Since x1 5‘4 0 at z,2xo — x3 — x4 E (Q)I’. Comparing with (2.21), yields 230 E (Q)". Accordingly, it is easy to see that (Q)" Q (P). Thus by Remark 2.2 we have (Q)" Q (P)I'. So Theorem 2.1 provides a homotopy and 4 paths which lead to all roots of (2.18). The table 2.2 shows a computing result with given parameters. Parameters a1 = .76771879 + .32820278i a2 = .54890949+ .1093949i a3 = .33010021+ .89058417i a4 = .11129092 + .67177492i a5 = .89248163 + .45296562i bl = .04796080 + .88868678i b2 2 .82915151 + .66987747i a = .59527814 + .71154547i Example 2.3. For generalized eigenvalue problems (or A-matrix problem), the system P has the following form: AkBox + Ak’lle + ..-+ ka = 0 (2.22) 1+01$1+-~+01n$n=0 19 Starting Points Solution Reached 1.131 = 1:132 = —1 x1 = —.731938 + .3453089i x2 = .049258 + .1264814i $3=0$4=2 x3 = 2.9605355 + 7.79467i $4 .0547949 — .0998576i 2.131 = 11172 = -1 x1 = -2.214090 + 1.074372i x2 = —1.43290 + .8555617i x3=2x4=0 x3 = .6873539 — 1.0286067i x4 = 1.6660806 + .7643948i 3.231 = 0172 =2 x1 = .0433732 + .750366i x2 = .8245659 + .5315566i $3=0$4=1 x3 = .1027011 + .2787743i x4 = .4602318 — .0694782i 4. 1=0$2=i x1 = .8908184 — .8041871i x2 = 1.6720086 — 1.0229946i $3=1$2=0 113 = 1.6573049 — 1.6070461 x4 = —.5652349 + .591969i Table 2.2: Solutions to (2.18) with given parameters where x = (x1, . . .,x,,),k > 1 and Bo, . . .,Bk are n X n matrices. Consider (A,x1, . . . ,xn) E C'1 X C". With 2-homogenization, (2.22) becomes W301: + 121101311 + ...+ (10¢ka = 0 (2.23) x0+a1$1 +"’+anxn = 0 with (A0,)\,xo, . . .,x,,) E P1 X P". If Bo is a nonsingular matrix, it is quite obvious that (2.23) has kn solutions for generic ag’s. In [4], a homotopy is given for nonsingular Bo, which provides kn paths leading to all roots of (2.22). Here, we give an example on which Theorem 2.1 can be applied when Bo is singular. Forn=3andk=2,let [0 1 01 '0 1 0- 30:010131‘4001 _0 0 1‘ _1 0 OJ and aI=---=an=1. Then (2.23) becomes, 131 = A2$2+Abo$2+hg$1=0 152 = A2$2+/\/\o$3+A3333:0 23 = A2$3+AA0$1+A3$2=0 154 = $0+x1+22+23=0 20 100] 001 010 (2.24) Parameter a = -—.74127114 + .70628309i x1 x2 x3 A 1. —4.0795970 3.075972 0 .7548779 2. —.4602 -- .1825814i —.5397982 + .1825814i 0 —.8774412 + .7448597i 3. -—.4602 + .1825814i —.5397982 — .1825814i 0 -.8774414 — .7448597i 4. -—.33333333 —.333333333 —.3333333 —.5 — .866025i 5. -.33333333 -.333333333 —.3333333 —.5 + .866025i Table 2.3: Solutions to (2.24) and the solution set at infinity is v = {(Ao,A,xo,x1,x2,x3) | A0 = 0, A = 1, x2 = 0, x0 + $1 = 0, $3 = 0}- Define Q =(911921931‘14) by 91 = (A - 1)(’\ " 2)$2 = 0 q2 = (A — 3)(A — 4)x3 = 0 q3 = (A — 3)(A — 4)x3 + Axl = 0 24 = 1+$1+$2+$3=0- It is easy to check that the zero set at infinity of z: (A -- A0)(/\ -~ 2A0)$2 Z 0 (A — 3A0)(A — 4A0)$3 = 0 (A - 3A0)(/\ - 4A0)$3 + AonI =2 0 = $o+$1+$2+$3=0 (2.25) (2.26) is the same as that of (2.24). The system (2.25) has 5 nonsingular solutions (A, x1, x2, x3) = (0,—-1,0,0), (1,0,—1,0), (2,0,-—1,0), (3,0,0,-—1) and (4,0,0,-—-1). For any z E v, A0 = 0 and A = 1 hence (A -3Ao)(A —4A0) 75 0 and (A — A0)(A — 2A0) yé 0. From 11 and (72 both 2:; and x3 are in (Q)!2 and from (1'3, on1 E (Q)I'. In summary, (Q)" 2 (P)!1 and Theorem 2.1 applies. The table 2.3 shows our computing result. 21 Chapter 3 Nonlinear Homotopies It occurs sometimes in practice that the polynomial system P(x) is associated with a set of parameters q = (q1, ...,q,-) E Cj. In this situation we write P(q, x). It is often the case that the system needs to be solved repeatedly with varying parameters of q’s. In this chapter we give a procedure that begins with solving P(q,x) for a particular parameter qo. Then for each subsequent choice of the parameters q of the system, a nonlinear homotopy is used to find all isolated solutions with amount of computation approximately proportional to the actual number of solutions. The theorem on which the method is based is described in section 3.1. As an application, we show, in section 3.2, how to compute the 32 solutions of the Tsai-Morgan manipulator problem in [20] by following only 32 solution paths. 3. 1 Main Results Definition 3.1 We say that a property K holds for generic q E C 5 (P’), if there exists an algebraic subset E C C’(P’) of dimension < s such that q E E implies K hold. Theorem 3.1 Suppose that the polynomial system P(q,x) of n equations with z E M = P"1 X x Pkm and q E 0’, which is m-homogeneous with respect to 2, satisfies the following conditions: 1. For generic q E Cj, the solutions of P(q,x) = 0 at infinity are isolated and its number, counting multiplicities, equals B - r, where B is the Bézout number of the system H (112}; 22 2. There is a fixed generic point q0 such that the solution set of P(qo, z) = 0 in the a fiine space consists of nonsingular isolated points x1, ..., x'. For any point q1 in Cj, let H(a, z,t) = P((l — t + t(1 — t)a)q0 +(t(1— a(1 — t))ql, z). (3.1) Then there exists an open dense full measure subset D of C, such that for a E D, we have a. (Smoothness) For each isolated zero x" E T,k = 1, . . .,r there is a function x"(t) : [0, 1] -—+ M which is analytic and contained in afl‘ine space for all t in [0,1) and satisfies H(a,x"(t),t) = 0. b. (Accessibility) Each isolated afi‘ine solution of P(q1,x) = 0 is reached by xk(t) for somek att= 1. Before proving Theorem 3.1, we need the following lemma. Let E be the algebraic set associated with the genericity of the parameter q in the condition (1) above. That is, if q E E, then the system P(q, 2) satisfies condition (1). Lemma 3.1 Suppose that q0 and q1 are as in Theorem 3.1 and consider the homotopy 3(A12)= 1"((I - r040 + A4112) = 0, (3-2) where A E C. Let H(Ao, A, 2), (A0, A, z) E P1 X M, be the homogenization of]? with respect to A. Then for each k=1,...,r, the irreducible component of B‘1(0) passing through x" satisfies the following: (1) Let N be the set of points (A0,A1,z) with 2 at infinity, then 1r1(A;c n N) E P1 is a finite set, where 171 is the natural projection; (2) Let J = {A e 0|(1— A)q° + Aql e E}. (3.3) Then J is a finite set. (3) (1,0) g “(4,. n N). Proof. The proof of (1) follows the same line of arguments in Lemma 2.2 , so we omit it. 23 (2) Without loss of generality we may assume q0 = (0, ..., 0) and q1 = (1, 0, ..., 0). Because E is an algebraic set , it is the set of common zeros of polynomials f1, ..., ft. Since q0 E E, f.-(0, ...,0) 7‘— 0 for some i. Thus f;(A,0, ...,0) i 0. Hence there are only finite many solutions to g(A) E f,-(A,0,...,O) = 0. Therefore the line (1 — A)q0 + Aq1 = (A,0, ...,0) intersects with E at finitely many points. This completes the proof of (2). (3) From the proof of (2), there exists a set D = {C\ a finite set} such that for A0 = 1 and A1 E D the number of solutions of IT(1,/\1,Z) = 0 (3.4) at infinity are the same. The rest of the proof is the same as the proof of Lemma 2.2, so we omit it. For each A in J, the set I,\ = {(1, A,z) E P1 X Mlz E M} is an algebraic set, so is its union Uye‘, J,\ since J is finite. Proof of Theorem 3.1 For each x", k = 1,. ..,r in T, let Ak be the irreducible component of V(B), the zero set of IT in P1 X M, passing through x". Let B). be the set of points (A0,A,z) in Ak which are nonregular or at infinity or 7r1(Ao,A,z) = (LA) with A in J. Bk is an alge- braic set for each It. So 1r1(Bk) is a proper algebraic set in P1, because ( 1, 0) E 7r1(Bk) by Lemma 3.1 and hence it is finite for each It. Let A = U2=1 7r1(Bk) = {(c;,d,) | i = 1,. . .,I}, F = {aglag = g],(c£, d:) E A,c{- 7i 0}. Aslongas a E DI = {(t—a,)/t(1—t)|a,- E F,t E [0,1)}, (1,t(1 - a(1—t))) ¢ (1,a,-) for any i and t6 (0, 1). Thus (1,t(1 — a(1 - t)),z) E 8;, for any k, t E (0,1) and z E M. Let D = C\D1. By a similar argument as in the proof of theorem 2.1, the smoothness property and the accessibility property follow. When the polynomial system P(q, 2) satisfies the property that P(q,z) = 0 implies P(aq, z) = 0 for any a E C then, in Lemma 3.1 and Theorem 3.1, instead of considering the line (1 — A)q0 + Aql and the quadratic curves [(1 — t + t(1 — t)a]q0 + [t — t(1 — t)a]q1 through q0 and q1 we may consider Aoq0 + Aq1 and (1 — t)Aoq° + tAq1 and we can take the homotopy H(zJ) = P((l-t)aq°+tql,z) 24 to solve P(ql, z) = 0. In this situation we have a linear homotopy. In particular, we have Theorem 3.2 Suppose that for generic {a,b)E P1 the solutions to H(a, b, 2) = aQ(z) + bP(z) (3.5) at infinity are isolated and the number of them , counting the multiplicities, equals B-r, where B is the Bézout number of the system . And the set T = { the points of V(Q) in afl‘ine space } consists of nonsingular isolated points x1, . . . ,x”.Then, there exists an open dense subset D of C with full measure, such that for a"1 chosen from D, we have a. (Smoothness) For each isolated zero 2:" E T,k = 1, . . .,r there is a function x"(t) : [0, 1] -+ M which is analytic and contained in afline space for all t in [0, 1) and satisfies B(a,xk(t),t) = (1 — t)aQ(xk(t)) + tP(xk(t)) = 0. (3.6) b. (Accessibility) Each isolated solution of P(z) = O in afl‘ine space is reached by x"(t) for some I: at t = 1. 3.2 Applications The very important inverse kinematics problem for the 6R manipulator of general ge- ometry (robot arm design) was reduced by Tsai and Morgan ([20]) to the solution of a polynomial system of 8 equations in 8 unknowns.The system is as follows. P1 = -$1$3/\lflzq + $1$4fl2P + $2$3AIM2P + 3725541129 — (3-7) $5$8H3A405 - $6$7tl305 - $1A2I‘14 + $2/\2#1P - 9131111120 - d1) — 33411201 + $5fl3fl4d5 - $6l13¢14 - $8F4A305 + AIM" - A1/\2dl - A2d2 - d3 - /\3d4 - A3A4d5 = 0 p2 = —x1x3A1p2v + x1x4p2u + x2x4p2v + x2x3A1p2u + $5$7fl3r\4#5 - $6$8I£3fl5 - $1 Azfliv + $2A2fl1u - $3H1M2w + $5H3fl4A5 + $7/\3#4H5 + A1 A2111 —A3A4A5 = 0 25 p3 = x1x3a2u + x1x4A1a2v + x2x3a2v — x2x4A1a2u - $5$7fl3A4flsd3 + $5$8l1503 + $6$7#5/\403 + $6$8fl3l15d3 - x1(—a1u + #16121?) + $20110 + #1d2’u)+ x4u1a2w - $5M3H4Asds + $6I£4I\503 - $7(#4/15d4 + A3fl4fl5d3) + $811504 + (111” + Aldzw + A3/\4/\5d3 + A4A5d4 + A5d5 — pu — qv — rw = 0 P4 = $1$302P + $1$4A1024 + $2$302q - $2$4A102P + x5x7a3a5 + x5x8p3A4a5d3 + x6x7p3a5d3 — $6$8A4a305 + $1(01P - #ldzq) + 32(014 + #1d2P) - $30102 + $4(-#102d1 + [1102?) + $501304 - flamdads) +$6(#4d503 + #304d3) + $70405 + $s(fl405d4 + A3p4a5d3) +d17‘ + A1012? - Aldidz + A3d3d4 + A3A4dsds + A4d4d5 +0.5(—a';’—d§—a§—d§+a§+d§+ai+d§+a§ +d§—22-qz-r2)=0 p5 = x? + x3 — = 0 p6 = x§+xZ—1=0 p7 = x§+x§—1=0 p3 = x§+x§-1=O where x;, i = 1,2, . . -,8 are the variables and the others are parameters. From various computing experiences, it has been predicted ([13, 19]) that this system has 32 isolated solutions for generic parameters. In this section, we shall prove this assertion and give an algorithm, via homotopy continuation method, for finding all 32 isolated solutions with minimal computation efforts. By letting (xo,x1,x2,x5,x6) E P4 and (y0,x3,x4,x7,x8) E P4, we may 2-homogenize (3.7) and obtain (introduced in [19]), ~ 191 = —z123A1142q + 31341421? + $2$3/\1#2P + $2$4H24 — $5$8M3A405 - $6$7fl305 - $1A2Iliqy0 + $2/\2/11Py0 - $3u1#2(7‘ - d1)$0 - $4H201$0 + $5M3fl4d5y0 - $6H3a4y0 - 26 x8p4A3a5xo + (A1A2r — A1A2d1 — Agdg — d3 — A3d4 - Ashdsfioyo = 0 p2 = —x1x3A1p2v + x1x4p2u + x2x4p2v + x2x3A1p2u + $5$7H3A4P5 - $6$8fl3115 - (DIM/110310 + $2/\2#1 H.710 — $3P1fl2w$0 + $5P3P4A5y0 + $7A3P4P5$0 + (A1 A2111 -/\3A4/\5)$oyo = 0 p3 = x1x3a2u + x1x4A1a2v + x2x3a2v - x2x4A1a2u — (3.8) $5$7P3A4flsds + $5$8P503 + $6$7P5A403 + $6$8P3l15d3 - $1(—alu + Pidzvhlo + $2011” + Pldzulyo + $4H102w$0 - $5fl3M4A5d3yo + 36H4A503y0 - 937014115614 + A3u4p5d3)xo + $sflsa4$o + (diw + Aldzw + A3A4A5d3 + A4A5d4 + A5d5 — pu — qv - rw)xoyo = 0 P4 = $1$302P + $1$4A1024 + x2x3a2q - $2$4A102P + x5x7a3a5 + $5$8#3/\4asds + $6$7P305d3 - $6$8A40305 + $1(01P - fl1d29)yo + $2011!) + #1 dzplyo - $30102$o + it'd-#102611 + P102T)$o + $5(0304 - #3P4d3d5)y0 +$6(#4d503 + [1304(13) + $70405 + $8(#4a5d4 + Asmasds) +(d17' + A1427‘ - Aldldz + A3d3d4 + A3A4d3d5 + A4d5)$oyo +0.5(—a’f—d§—a§ —d§+a§+d§+a3+dfi+a§ +d§ - 122 — r12 — r2)zoyo = 0 p5 = xf+x§-xg=0 26 = z§+z2—y§=0 p7 = x§+xg—x3=0 P8 = $i+$§—yfi=0 It is easily seen that for the system (3.8), d‘[ = d; = 1, i = 1,- ~,4, d? = d1]: d6 = d8 = 2 and d5 = d; = d? = d? = 0. Accordingly, from ( 1.7), the Bézout number of the system is the coefficient of am“ in the product (a + 5)4(2a)2(2fl)21 27 which equals 96. It was proved in [19] that this system has at most 64 isolated solutions in P4 x P4. We shall prove that the number of zeros at infinity, counting multiplicities, is 64, and consequently, the number of isolated zeros in affine space is at most 32. The points at infinity consists of 3 categories, that is, (i) x0 = yo = 0, (ii) x0 = 0, yo = 1, (iii) x0 = 1, yo = 0. We shall discuss each case separately. (1)170 = yo = 0. The last 4 equations in (3.8) gives, 155 = x¥+x§=0 p6 :: x§+x§=0 157 = x§+xg=0 P8 = $i+$§=01 and hence x2 = :lzixl, x4 = :tixg, x6 = :l:ix5 and x3 = :lzix7. There are 16 combinations. For a typical combination, say, 2:; = ix], x4 = ix3, x6 = ixs, x8 = ix7, the first 4 equations of (3.8) gives 151 220+ A1)(-q + ip)x1z3 4615;433:5370 + A4) fl2(l + A1)(—’U + iu)x1x3 + fl3fl5$5$7(1 + A4) (3.9) a2(—i)(1 + A1)(—v + 2.1033122; + [15351.7(1 + A4)(ia3 -— fl3d3) a2i(1 + A1)(q — ip)x1x3 + a5x5x7(1+ A4)(a3 + i113) If we regard (3.9) as a linear system with unknowns mm and x5x7, then it is easy to see that the only solutions are x1x3 = 0 and x5x7 = 0 for generic parameters. However, x1 and x5 cannot be zero simultaneously, for otherwise (xo,x1,x2,x5,x6) = (0,0,0,0,0) which is not in P4. Similarly, x3 and x7 cannot be zero simultaneously. Thus, only 2 solutions left, that is, (x1,x2,x3,x4,x5,x6,x7,x3) = (1,i,0,0,0,0,1,i) and (0,0,1,i,1,i,0,0). Counting multiplicities, there are 32 isolated solutions in total in this case. (ii) 20:0, 0:1 From (3.8), we have p5 : x¥+x§=0 x§+x§=0. "o q H 28 Hence, x2 = :lzixl, x6 = iixs. There are 4 combinations. Let us consider a typical situation: x2 = —ix1, x6 = ix5. It follows from (3.8), P1 = -$1(q + ip)f1($3, 1:4) — 1139:5910”, x8) = 0 152 = ‘310’ +iu)f1($3a $4) + fl3$592($7, $8) = 0 (3.10) 133 = 31(1’ + i")f2(331 934) + (503 — #3d3)$592($7, $8) = 0 P4 = 2:1(q + iP)f2(‘1531-’174) " (£03 - P3d3)3591($71$8) = 0 where fl($39 $4) = ”2(Alx3 + 1.274) + A2/1'12 f2($3, $4) = 02(-i$3 + A1$4) - (501 + d2111) and 91(3371338) = 050937 + A4138) — (#4d5 — ia4), '92($7, $8) = H5(/\4$7 - i508) + #4r\5- Now, (v+iu)><151 -(q+ip)><152 = -#3$5[(v +iu)g1(x7,x3)+ (q + z°P)92(5'3711’8)l = 0- If x5 = 0, then x6 = 0 and x1 76 0. We then have an overdetermined system of x3 and x4 for generic parameters. That is, fl($3134) : 1120\le + i334) + A2/11 = 0 f2(x3,x4) = (”(4553 'l' had-(1'01 + (12/11) = 0 ~ p6 = x§+x§-1=0, which has no solution in general. Hence, x5 75 0, and (v + iu)g1(x7,x8) + (q + ip)g2(x7, x3) = 0. Combining this linear equation with pa = x3, + xg - 1 = 0, we arrive at 2 solutions for x7 and x3. On the other hand, (d3P3 — £03) X P1 + [13134 = x1(q + ip)[(ia3 - d3P3)f1($3, $4) + #3f2($3, $4)l = 0- 29 By a similar argument, x1 9i 0 for generic parameters, and combining the linear equation (ids - d3P3)f1($3, $4) + #3f2($3, $4) = 0 with 136 = x3 + x2 — 1 = 0, we arrive at 2 solutions for x3 and x4. Substituting any combination of x3,x4,x7,x8 we have obtained back to 131 = 0,152 = 0 in (3.10), unique solution of x1,x5 can be found. As a consequence, there are 4 solutions in this case. And there are 16 solutions in total. (ill) 20 = 1, yo = 0 From (3.8), we have fig = 23:23 + 1'3 2 0 P8 = 3i + 2?, = 0 Along the same line of argument as in (ii), we consider a typical combination: x4 = —ix3 and x8 = ix7. It follows that P1 = #2$3f3($1,$2) - £053793(25136) = 0 P2 = H2$3f4($1, $2) + P5$793($5,$6) = 0 (3.11) P3 = z'02$3f4(-’1=1,$2)" P5$7g4($5,$6) = 0 P4 = i02$3f3($1,$2) + ias$794($5, $6) = 0 where f3($1,$2) = —(iP + Aiq)$1 + (A119 -i‘1)$2 +(ia1 — #1(7‘ — ‘11)) f4($1,$2) = —(iu + A1103] +(A1u — 1.10272 - [11w 93(35136) = Antares 411326 + A3114 94(335, $6) = (d3/\4l15 - i€13)$s - (idslls + A403)$6 +d3/\3#4 + P4d4 - £114. And, (—-u5i) X P1 + as X P2 = M2$3(05f4 - Psifs) = 0- It can be shown that x3 99 0 for generic parameters. And combining the linear equation 05f4($1,$2) - usif3($1,$2) = 0 30 with 135 2 xi + xg — 1 = 0, we have two solutions for x1 and x2. On the other hand, a12 X P2 + (1121') >< Pa = 2527(0293 - #2204) = 0- Again, for generic parameters, x7 75 0. The linear equation 0293(7551136) - P2i94($5136) = 0 and p7=x§+xg—1=0 yields 2 solutions for $5 and x6. Substituting any combination of x1,x2,x5,x6 back to (3.11), we have a unique solution of x3 and x7. Hence, we have 4 solutions in this case and 16 solutions in total. There are 26 parameters in the system (3.7). Let E E C26 be the vector representing all these parameters and write P(x) = P(E,x). To find a particular system with easily calculated isolated zeros, we proceed as follows. First, we add more parameters B = (b1,b2,b3,b4) into (3.7) by defining P(B, E,x) = (131, - - -,p8) as: P1 = P1 + b1 P2 = P2 P3 = P3 + 52 P4 "-‘ P4 + 53 (3~12) P5 = P5 P6 = P6 P7 = P7 P8 = P8 + 54 When we 2-homogenize the system (3.12) and look at the zeros at infinity of (3.12) as we did on the system (3.7), all the parameters in B will disappear. Thus, for generic parameters B and E, P(B, E,x) = 0 has the same number of solutions as P(O, E,x) = P(E, x). Namely, for generic parameters B and E, P(B,E,x) = 0 has at most 32 isolated solutions. For a particular choice of B and E, denoted by (Bo,Eo), with r = w = v = q = d1 = d3 = d5 :- a4=A1=A3=A4=A5=u2=O,u=p=a1=a2=a3=a5=d2=d4=111:113: 31 p4 = #5 = A2 = 1 and bl = 1,b2 = -4,b3 = —4.5,b4 = —1, the system (3.12) becomes, P1 P2 P3 P4 P5 -$6$7 + $2 -$6$8 + $2 $1$3+$5$s+$1+$2-$7-5 x1x3+x5x7+x1+x2—x3+x3—5 (3.13) x¥+x§—1 x§+x§—l x§+x§—1 x§+x§-2 There are exactly 32 isolated zeros of the system above, and each one of them can be easily obtained by straightforward eliminations. We shall briefly describe the calculations here. From 131 — p2 = 0, we have 235(37 — $3) = 0 which implies (i) x6 = O, or (ii) x7 = x8. (1) $6 = 0. In this case, x2 = 0. Consequently, x5 = :t1 and x1 = :lzl. A typical combination, say, x1 = 1 and x5 = 1 yields, from 134 = 0, $7+$g-4=0. Together with p3 = x; + x3 — 2 = 0, two solutions of x7 and x3 are obtained. That is, x7 = 2 :l: fii and x8 = 2 q: fii. Substituting back to 133 = 0, we have x3 = 4 :l: 2J3i. And, from p5 = x3 + x3 — 1 = 0, two solutions of x4 can be calculated for each value of 3:3. In total, we have 16 solutions in this category. (ii) 237 = 173. From p8 = x; + x3 — 2 = O, we have x-,- = x8 = 21:1, and, from p1 = 0, x2 = ixs. Consequently, x1 = ixs. Also, P4 - P3 = 0 yields, x3 = 2, and hence, x4 = :l:\/3i. A typical combination, say, x7 = x8 = 1, x2 = x6, x1 = x5 and x3 = 2, gives, from 133 = 0, 4x1 +x2 = 6. 32 Together with 135 = 2:? + x3 — 1 = 0, two solutions of x1 and x2 become available. That is, and x2 = .. 24:1: 191 “’1’ 17 24 191' 17 ° In total, we also have 16 solutions in this case. Now, consider the homotopy H(a,-Pat) = P([(1—t)‘l't(1—t)al(301 E0) (3-14) +1111 — a(1 — 01110. 131.2) = o, where a E C. When t = 0, we have H(a,x,0) = P(Bo,Eo,x) = 0, which is the system (3.13) and the solutions are known. When t = 1, H(a,x,1) = P(0,E,x) = P(E,x) = 0 which is the system (3.7). By the Theorem 3.1, we have the following, Proposition 3.1 For any given parameter set E E C26 and a randomly chosen a E C, the homotopy (3.14) satisfies the smoothness and accessibility properties. From this proposition, every isolated solution of P(E,x) = 0 in (3.7) can be reached by some solution path of H (a,x,t) = 0 in (3.14), originating at t = 0. The path can be parameterized by t in [0, 1) and starts at a solution of H(a, x,0) = P(Bo, E0, x) = 0 in (3.13 ). Notice that there are exactly 32 paths, which is less than all the existing homotopies for this problem by at least a half. The algorithm has been implemented and executed without any failure for different sets of parameters we tried. The table 3.1 shows a typical computing result. An application of theorem 3.2 can be found in following example. Suppose we want to solve the system P1 = $3t/3— 1 P2 = xy+x+y+1 Let (76 -1)(z - 2X1: - 3)(y —1)(v - 2)(y — 3) xy+1 (11 (11 and G(a,b,x, y) = aQ + bP. If C is the 2-homogenization of G, then the Bézout number of the system C is 12. For generic (a,b) E P1((a,b) 76 (1,-1)) , the system has two solutions 33 Parameters a 11 V W #4 #2 .336675 -.28947i .2727448 .57121 .0000 .3663635 -.5088737 01 d1 [‘1 A1 02 d2 q .982733 .4798967 - .9464922 .3227 267 .7639239 .25918 .7449497 03 d3 #3 A3 04 d4 P .5451146 .04037 -.071255 .997458 .3263 .8215618 .963759 as (15 [15 A5 A2 A4 1‘ .107496 .6027525 .803982 .594653 .8608412 .9304718 .52614 Solutions Found 1'1 x2 x3 :4 1:5 16 x7 ‘8 .4479964 -.894035 .6380733 .7699757 -.938979 .3439749 -.l59925 ..9871292 .2218439 ..975082 .4720904 .8815501 .02034 77 .999793 - .260256 .9655395 ..135018 -.990843 .0696905 .9975684 ..022661 .9997432 .0982504 .9951615 .4540939 -.890954 .5255288 .8507758 ..733651 ..6795284 - .34666 -.937991 -.540165; .842621 ; —2.32259; 5.69644; 10.09924; —15.6863:F 5.74658; 2.251062i .0356i .022824i 5.6207i 2.291703i 15.663703i 10.084 72i 2.221031 5.66893i 1 .6617053: —.5735751 —1.15989; —.56853:1: 4.53055; —7.515156:l; -1.669081¥ .98484 ; .471 729i 1 .36664 741 .359879i .7342l2i 7.486027i 8.497486i .843605i 1.429713i 1.004864i -.l4298d: 3.19571 i 8.444991: —2.379306:!: ~7.573479:F 2.41357; —2.324815¥ .024479i .172036i 8.3930401 3.176051i 7.5131491 2.3603521 2.2152511 2.297895i 1.1557953: .0002; —6.719234=F .226035; —9.35885:h —1.88501¥ —1.964046¥ —4.13826:t .0001i .579536i 2235211 6.644488i 1.87464i 9.307368i 4.038446i 1 .916653i 1.423549; —0.490041¥ 1.082638; —0.716682$ 1.00763i: -l2.81038i —1.6951t 1.31788: .3663253i 1.0641598i .457099i .6905057i 12.771532i 1.004575i l .1662l9i 1.50003i 2.955148; .7709251 -—l.185142:t —.947416; 1.687669; —4.640512}: -1 .166774; 2.65762; .728427i 2.792242i .7125328i .8913217i 4.5443491 165269861 2.494902i 1.095336 396764; —.458226$ 1.946745t 906342? -6.9181 i 1.909785zl: -1 035343? 1.0319154 4: .054138i .10595i .802069i 1.7227758i 1.891155i 6.8506121 .7526668i .7551665i 4.368425; .230832i —1 .292526i —.530158:F -—.94 7854:}: 1.240695i —1.076679¥ 2.16523; .224 721 4.252755i .3702095i .9025711 .952823i .7279286i 1.971413i .9803015i -,278632; —.972686i —.28221i .966405i —1.6677:t 6328941 4472611: -.9876348:h .1481645i .0424426i .1118686i .032668i .5240848i 1.3809831 .3815813i .172803i —.992321:t .123889i .508913? 2.0031893: —4.387059:F 9.856731? 2.7228612}: —1.03913¥ .000862i .0069071 1.7531098i .44538i 9.8143i 4.3681 736i .976045i 2.557557i 3.728055; .061396i —1.270256§: —.582666¥ —.979966:k .204924t —.517122F —1.999667i .O59146i 3.59147i .407024 7i .887345i .009874i .0472206i .1.749672i .4524 7071 .038208i —1 .012304i .276872i .970562; .832789; —.650007$ 3606323}: .9793755i .1618099i .0061071 .1313191 .03746li .2096011 .2685406i .1590995i .0423396i 1.183174i -—.466935i -3.58459¥ —.832769i —10.39366:k —9.491538¥ —1.77677i “5483762: .288567i .7312i .8014331 3.44971i 9.467553i 10.36739i .462324 7i 1.4979576i 2.8638162F —l.36066¥ —1.0717¥ —.507232:l: —3.735566¥ —2.686579t —.96021:t -2.23979¥ .291212i 2.717648i .272529i .5758127i 2.622366i 3.64628i 2.042529i .8756418i Table 3.1: Solutions to (3.7) with given parameters 34 (0,1,0) and (0,0,1) at infinity, each one with multiplicity 3. Thus by theorem 3.1 we can use the homotopy H (2:,t) = (1 — t)aQ + tP to find all isolated solutions of P by following 6 solution paths. 35 Appendix For P = (121,122) in (1.5) and Q = (q1,q2) in (1.6), let H = (h1,h2) = (1 — t)aQ + tP, where a is any nonzero number in C, which is not a negative real number. To be precise, (1) h1(a,:1:1,2:2,t) = (1 — t)a(xg — 1) + t(zrg + 2:1) = 0 (2) h2(a, 231,222,t) = (1 — t)a(xg + 2:132) + t(xg + 2:2) = 0. Multiplying (1) by 2:2(1 — t)a and subtracting t x (2), yields, (3) $3 [(1 — t)at + (1 — t)202] + 2:3 [—(1 — t)at — t2] + 2:2[—(1—t)2a2 — t2] = O. From (3), we can see that for each fixed a E C and t 6 (0,1), the zero set of H(a,:rl,:132,t) are (21,12) = (Ll—"ftl‘ififi (d1,€1) and ((12,62), where —b+\/b2—4c —b—\/b2—4c t(e;+1) dg=- — i = 1 1 (5) (1—t)a e 1 2 01' d.- z _[((e.)2 — nut— t)a — (em .= 1,2, (6) with b_ —t C_ —(1—t)2a2—t2 ' (1 —t)a’ _ (1—t)a[t+(1—t)a]' It is easy to see that as t -> 0, b —> 0, c ——> -1. Hence, from (4) and (5), (d1,€1) —> (—1, 1) and (d2,eg) —* (1,—1). When t —+ 1, g—f —-> 0, i- is bounded and 4 2 4 —2 4 f5—b+\/b2—4c=b(—1+‘/1-3§)=b(—1+1—b—:+0(b—:))=——C+0(—£). b b However, 9 _ [t2 + (1 - 020’] b” t[t+(1-t)a] —>la.st—81. 36 Hence f -—> —2, and 61 —> —1, as t —+ 1. From (6), ((11,631) —> (—1, —1). Similarly, g E —b—\/b2—4c=b(—1- 1":2‘; 26 46 = b(—1 — l1 - b_2 + 0(35”) 2c 46 When t -—> 1, b —-> +00, hence, g —-> +00 and 62 —> +oo. Therefore, (d2,62) —-> (+oo,+oo) from (6). 37 Bibliography [1] Allgower, E., K. Georg. Simplicial and continuation methods for approximating fixed points and solutions to systems of equations. SIAM Review 22 (1980), 22-85. [2] Balakotaiah, V., Luss, D., and Keyfitz, B.L. Steady state multiplicity analysis of lumped-parameter systems described by a set of algebraic equations. Chem. Eng. Com- mun. 36 (1985) 121-147. [3] Chow, S.N., Mallet-Paret, J. and Yorke, J.A.. A homotopy method for locating all zeros of a system of polynomials. Functional Differential Equations and Approxima- tion of Fixed Points, Peitgen, H.O. and Walther, H.O. ed. Springer Lecture Notes in Mathematics No. 730 (1979), 77-88. [4] Chu, M., Li, T.Y. and Sauer, T.. A homotopy method for general A-matrix problems. SIAM J., Matrix. Anal. Appl., 9 (1988), 528-536. [5] Fischer, G., Complex analytic geometry, Lecture Notes in Mathematics, 538, Springer, New York, 1977. [6] Fulton, W., Intersection Theory, Springer, New York, 1984. [7] Hartshorne, R., Algebraic geometry, Graduate Texts in Math., 52, Springer, Berlin, Heidelberg, New York, 1977. [8] Hodge, W.V.D. and Pedoe, D., Methods of algebraic geometry, V. 2, Cambridge, At the university press, 1952. [9] Li, T.Y.. On Chow, Mallet-Paret and Yorke homotopy for solving systems of polyno- mials. Bulletin of the Institute of Mathematics, Academica Sinica 11 (1983), 433-437. 38 [10] Li, T.Y. and Sauer, T.. A simple homotopy for solving deficient polynomial systems. Japan J. Appl. Math. 6 (1989) 11-21. [11] Li, T.Y., Sauer, T., and Yorke, J.A.. Numerical solution of a class of deficient polyno- mial systems. SIAM J. Numer. Anal. 24 (1987), 435-451. [12] Li, T.Y., Sauer, T., and Yorke, J .A., “The random product homotopy and deficient polynomial systems,” Numer. Math. 51 (1987), 481-500. [13] Li, T.Y., Sauer, T.and Yorke, J .A. . The Cheater’s Homotopy: An Efficient Homotopy for solving Systems of polynomial Equations. SIAM J. numer. Anal. 26 (1987) 1241- 1251. [14] Li, T.Y. and Wang, X.. Solving Deficient Polynomial Systems with Homotopies which keep the Subschemes at Infinity Invariant. To appear in Appl. Math. Comput.. [15] Matsumura, H., Commutative algebra, Benjamin, New York, 1970. [16] Morgan, A.. A homotopy for solving polynomial systems. Applied Math. Comp. 18 (1986), 86-92. [17] Morgan, A. and Sommese, A.. A homotopy for solving general polynomial systems that respects m-homogeneous structures. Appl. Math. Comput. 24 (1987), 101-113. [18] Morgan, A. and Sommese, A..Coefl‘icient-—Parameter Polynomial continuation. Appl. Math. Comput. 29 (1989), 123-160. [19] Morgan, A. and Sommese, A.. Computing all solutions to polynomial systems using homotopy continuation. Appl. Math. Comput. 24 (1987), 115-138. [20] Tsai, L.-W. and Morgan, A..Solving the kinematics of the most general six- and five- degree-of- freedom manipulators by continuation methods. ASME J. Mechanisms, Trans- missions and Automation in Design, 107 (1985): 48-57. [21] Zulehner, W.. A simple homotopy method for determining all isolated solutions to polynomial systems. Math. Comp., 50 (1988), 167-177. 39 MICHIGAN STRTE UNIV. LIBRARIES ll][W][HIIWWMI]I]ll[INN]Will] 31293008952917