\lWllWlHiHIIIIHIHHIHNUIWWWINI[IIHUHI 'V P-\ \ IHrblb IIIIIIIIIIIIIIIIIII .eiie lllllllllllllllllllllllllllllllllllllllllllllllllllllll 31293 01810 3899 This is to certify that the dissertation entitled Faulty All BOIM'ul R0923 of Polynom’w 51.91%!) In C" Via. shale. Mixed Volume. presented by Toma an 61" M has been accepted towards fulfillment of the requirements for Ma - D degree in Wm were»: éf/e/fi LIBRARY Michigan State University PLACE IN RETURN BOX to remove this checkout from your record. To AVOID FINES return on or before date due. MAY BE RECALLED with earlier due date if requested. DATE DUE DATE DUE DATE DUE MAR 26 :4 7 1/98 animal-$651114 FINDING ALL ISOLATED ROOTS OF POLYNOMIAL SYSTEMS IN C" VIA STABLE MIXED VOLUME By Tangan Gao A DISSERTATION Submitted to Michigan State University in partial fulfillment of the requirements for the degree of DOCTOR OF PHILOSOPHY Department of Mathematics 1999 ABSTRACT FINDING ALL ISOLATED ROOTS OF POLYNOMIAL SYSTEMS IN C" VIA STABLE MIXED VOLUME By Tangan Gao To find all the isolated zeroes of a polynomial system P(x) in C" (as opposed to in (C‘ )“) via the polyhedral homotopy method of Huber and Sturmfels [7], one first finds all stable mixed cells in a stable mixed subdivision and establishes a fine mixed subdivision for each stable mixed cell. One then solves a collection of polyno- mial subsystems corresponding to the stable mixed cells, and uses their solutions as starting points for the homotopy paths of a set of nonlinear homotopies which lead to all the isolated zeros of P(x) in C“. This method offers a dramatic computational improvement over earlier homotopy algorithms at the cost of many costly recursive liftings at the preprocessing step of finding the stable mixed cells and their fine mixed subdivisions. The main goal of this dissertation is to present a new strategy which can quickly (and simultaneously) find the stable mixed subdivision, the fine mixed subdivisions of the stable mixed cells, and the necessary subsystems by means of a single lifting. ACKNOWLEDGMENTS I would like to express my sincere gratitude to Professor Tien—Yien Li, my dis- sertation advisor, for his constant encouragement and kind guidance. His knowledge, insights and enthusiasm were invaluable. I’m grateful to Professor Xiaoshen Wang for ideas leading to the proof of Proposi- tion 1. I would also like to thank Professor Chichia Chiu, Professor Michael Frazier, Professor Wei-Eihn Kuan, Professor Jay C. Kurtz, Professor Christel Rotthaus, Pro- fessor William T. Sledd and Professor Zhengfang Zhou for their time and advice. iii TABLE OF CONTENTS INTRODUCTION 1 Polyhedral Homotopy Method 2 Stable Mixed Volumes 3 A Single Lifting 4 The Main Algorithm 5 Numerical Implementation BIBLIOGRAPHY iv 12 17 28 35 45 Introduction Polynomial systems arose quite commonly in many fields of science and engineer- ing, such as formula construction, geometric intersection, inverse kinematics, power flow with PQ-specified bases, computation of equilibrium states, etc.. Elimination theory-based methods, most notably the Buchberger algorithm [2] for constructing Grbbner bases, are the classical approach to solving multivariate polynomial systems, but their reliance on symbolic manipulation makes those methods somewhat unsuit- able for all but small problems. In 1977, Garcia and Zangwill [5] and Drexler [3] independently presented theorems suggesting that homotopy continuation could be used to find the full set of isolated zeros of a polynomial system numerically. During the last two decades this method has been developed into a reliable and eficient numerical algorithm for approximating all isolated zeros of polynomial systems. See [10] for a survey. For a system of polynomials P(x) = (p1(x),...,p,,(x)) with x = (x1,...,x,,), write pi(x) = Z Ctaxaa 2:1,. ' ' In) 36.4; where a = (a1,...,a,,) E N", Cg. E C‘ = C\{0} and x“ = x‘l’l ---a:g~. Here .A,-, a finite subset of N", is called the support of p,(x), and the convex hull of A,-, denoted by Q,, is called the Newton polytope of p,(x). We call A = (A1, . . . ,An) the support of P(x). The Minkowski sum of polytopes 91,. . . , Qn is defined by Ql+"'+Qn:{al+"'+an l a1 E Qlwuaane 9n}- It can be shown that the n-dimensional Euclidean volume of the polytope A191 + -- - + An Q, with nonnegative variables A1, . . . , /\,, is a homogeneous polynomial in A1,. . . ,An of degree n. The coeficient of Al x A2 x - - - x An in this polynomial is defined to be the mixed volume of A = (A1, . . . ,Afi), denoted by M(A1, . . . ,A“) or M(A) when no ambiguity exists. Theorem 1 The number of isolated zeros in (C‘)", counting multiplicities, of a polynomial system P(x) = (p1(x), . . . ,pn(x)) is bounded above by the mixed volume M(A). For generically chosen coefi‘icients, the system P(x) = 0 has exactly M(.A) zeros in (0‘)". The root count in the above theorem was discovered by Bernshtein [1], Khovanskii [8] and Kushnirenko [9] and is sometimes referred to as the BKK bound. While this bound is, in general, significantly sharper than the classical Bézout number and its variants, a limitation is that it only counts zeros of P(x) in the algebraic torus (0)". Root count in C" via mixed volume was first attempted in [14] where an upper bound was derived by introducing the notion of a shadowed set. Later, a significantly much tighter bound was given by the following theorem (and was generalized soon after in [16])- Theorem 2 [12] The number of isolated zeros in C”, counting multiplicities, of a polynomial system P(x) = (p1(x),...,p,,(x)) with supports A1,...,A,, is bounded above by the mixed volume M(A1 U{0}, . . . ,An U{0}). We shall call the set (A1 U{0}, . . . ,A,, U{0}), denoted by AU{0}, the extended support of P(x). In [7], an even tighter bound was obtained: the number of isolated 2 zeros of a polynomial system P(x) = (p1(x), . . . ,pn(x)) in C" is bounded above by its stable mixed volume. This number is always smaller than the mixed volume of the extended support of P(x). This bound has since been generalized to the root count of polynomial systems over any algebraically closed fields, and various criteria have been established for the equality in this bound [15]. Based on Theorem 1, a polyhedral homotopy was proposed in [6] to approximate all the isolated zeros of a polynomial system P(x) = (p1(x),... ,pn(x)) in (C‘)“ by homotopy continuation methods. A random lifting w is applied to the support A = (A1,” . ,Afl) of P(x) to obtain a fine mixed subdivision .52,J of A as well as the supporting systems induced by the mixed cells of type (1, . . . , 1) in S“. These supporting systems are the start systems for a finite set of nonlinear homotopies induced by to. To find all the isolated zeros of P(x) in C", rather than in (C‘ )”, a modified algorithm, based on Theorem 2, was formulated in [10, 12]. By the revised algorithm, one can locate all the isolated zeros of P(x) in C" numerically, at the expense of following extraneous homotopy curves frequently. This wasteful computation may be eliminated by following the procedures suggested in [7]: First, identify the stable mixed cells of the extended support A U {0} of P(x) by applying an initial simple lifting on AU{0}. Followed by applying secondary recursive liftings to the stable mixed cells one obtains fine mixed subdivisions on these cells. Then standard polyhedral homotopies are applied to solve the polynomial subsystems corresponding to the resulting stable mixed cells. Finally, one may trace homotopy paths originated from these solutions of the subsystems to the zeros of P(x) in C". When polyhedral homotopy algorithms are used to find all the isolated zeros of polynomial systems, the most intensive computation rests upon the preprocessing step of identifying of proper mixed cells induced by the liftings. Therefore, the algorithm proposed in [7] may require a heavy preprocessing effort for its demand of recursive liftings. In order to produce a more efficient algorithm, we wish to avoid this scheme of recursive liftings. The purpose of this dissertation is to present the strategy of a single lifting which can accomplish the goals of the multiple liftings of the above procedures simultane- ously, so the preprocessing cost of applying polyhedral homotopy algorithms can be reduced considerably. As a by-product, in addition to solving all isolated zeros of P(x) in C", the stable mixed volume of A can easily be assembled without recursive liftings. Our single lifting, along with its theoretical justifications, will be given in Chapters 3 and 4 after the necessary terminology is introduced in Chapters 1 and 2. In accordance with our lifting, a new algorithm to find all the isolated zeros of P (x) in C" has been successfully implemented, and numerical results on a substantial variety of examples are presented in Chapter 5. CHAPTER 1 Polyhedral Homotopy Method Let A = (A1, . . . ,A") where for each i = 1,... ,n, A,- is a nonempty finite subset of N". By a cell of A we mean a tuple C = (C1, . . .,C,,) of subsets C,- C A, for i = 1,. . . ,n. Define the short hand notations: type(C) := (dim(conv(C1)), . . . ,dim(conv(C,,))), which is called the type of the cell C, conv(C) :2 conv(C1) + - - - + conv(C,,), the Minkowski sum of the convex hulls of C1, . . . ,Cn, and Voln(C) :2 Vol,,(conv(C)), the n-dimensional Euclidean volume of conv(C). A face of C is a subcell F = (F1,...,F,,) of C where F,- C C,- and some linear functional or E UR")V attains its minimum over C,- at F,- for each i = 1,... ,n. We call such an a an inner normal of F. If F is a face of C then conv(F,-) is a face of the polytope conv(C,-) for each i=1,...,n. Definition 1 [6] A subdivision of A is a collection {C(I),...,C(m)} of cells of A such that (a) For allj = 1, . . . ,m, dim(conv(C(j))) = n, (b) conv(CUl) fl conv(C(’°)) is a proper common face of conv(Cm) and conv(Cm) when it is nonempty for j # k, (c) U212, conv(CUl) = conv(A). Furthermore, we call the collection a fine mixed subdivision of A if it also satisfies the following condition: (d) Forj = 1,...,m, write C(j) = (C[j),...,C,(.j)). Then, each conv(Cffl) is a simplex of dimension #ij) — 1 and for each j, dim(conv(C[j))) + - - - + dim(conv(C,(,j))) = n. A fine mixed subdivision of A = (A1, . . . ,A) can be found by the following standard process [6, 10]: Choose a real-valued function w,- : A,- ——> IR for each i = 1, . . . ,n. We call the n-tuple w = (wl, . . . ,wn) a lifting function on A, and w lifts A,- to its graph A,(w) = {(q,w,-(q)) : q 6 A} C Rn“. This notation is extended in the obvious way: 51(0)) = (mat-((1)), 4(a)) = (d1(w),---,«Aee(w))e Q,(w) =CODV(/ie(w)), C(w) = Q1(w) + - - . + Qua), etc. A lower face of a polytope in Rn“ is a face having an inner normal with positive (n + 1)-th coordinate and a lower facet is an n-dimensional lower face. The collection conv(C(w)) is a lower facet of 5“,: C=(Cl,...,C,,)cellsof A . . Ql(w) + - - ° + Qn(w) is the subdivision of A = (A1, . . . ,An) induced by the lifting function w [6]. When to = (w1,. . . ,wn) is chosen generically, 5,, gives a fine mixed subdivision of A [6]. To find all isolated zeros of P(x) = (p1(x),...,p,,(x)) (with support A = (A1, . . . ,An)) in (0)", we will use two homotopies. The first homotopy, called the polyhedral homotopy, is used to solve for all the isolated zeros in (C‘ )" of a new generic 6 system C with the same support as P. The second homotopy, a more standard linear homotopy, uses these zeros of G to find all the isolated zeros of P in (0)". To form the new generic polynomial system mentioned above, we assign generic coefficients to all the monomials in P(x). Denote the new system by C(x) = (.9100, . . . ,gn(x)) where g,(x) = 2: 6.3.3:“, i = 1,...,n, 36-44 and é,,.’s are randomly chosen complex numbers. We wish to find all the isolated zeros of this system in (0)" in the first place. Then, by following all the homotopy paths of the homotopy H(x, t) = (1 — t)C(x) + tP(x) = 0 emanating from those zeros of C(x), one can obtain all the isolated zeros of P(x) in (0)“ [6, 11]. To solve G(x)=(g1(x),...,g,,(x))= 0, we lift its support A = (A1, . . . ,An) by a generically chosen real lifting function to = (wl, . . . ,wn) and consider the polynomial system C(x, t) = (g1(x, t), . . . ,g,(x, t)) in the n + 1 variables x1, . . . , xmt, where g.(x, t) = Z axed”, 2': 1,...,n. (1.1) aeAt C(x, t) provides a homotopy with t as the parameter and when t = 1, C(x, 1) = C(x). It can be shown that for each t E (0, 1], the isolated zeros of C(x, t) are all nonsingular, and by Theorem 1, the total number of these zeros is equal to the mixed volume M(A1, . . . ,A). We write these zeros as x1(t), . . . ,x"(t) where k = M(A1, . . . ,Afl), so C(xj(t),t) = 0 for each t 6 (0,1] and j = 1, . . . , k. Let x(t) represent any one of x1(t), . . . ,x"(t), and write x(t) = (x1(t), . . . ,xn(t)). The lifting function w 2 (col, . . . ,wn) induces a fine mixed subdivision S“, of A = (A1, . . . ,An) and the mixed volume M(A1, . . . ,An) equals the sum of the volumes of 7 cells of type (1, . . . , 1) in Sw [6]. Let C = ({a10,a11}, . . . , {ano,a,,1}) be a cell of type (1, .. . ,1) in S“, and v,- 2 an - aw, i = 1,. . . ,n. Since 5,, is a fine mixed subdivision, {v1,. . . , Va} is linearly independent, and a simple calculation shows that V1 Voln(C) = det E . (1.2) Vn Let 6: = ((1,1) = (01,. . . ,an, 1) be the inner normal of conv(C(w)) = conv({am(w), a11(w)}, . . . , {ano(w), an1(w)}). Substituting x = yt", or x1 = ylt“1,. . . ,xn = ynta", into (1.1) yields, My” = Easyathmwda) 86A..- = Z 5i,ayat(é(w).d), I :: 1,. . . , n, (1.3) aE-Ai where (-, ) stands for the usual inner product in IR". Since 0‘: is the inner normal of conv(C(w)), by factoring out the lowest power in t, g,(y, t) becomes r,-(y,t) :2 5,,a,oy“'° + Qany‘“ + higher order terms in t, i = 1,... ,n. (1.4) Write R(y, t) = (r1(y,t), . . . ,rn(y,t)). Apparently, r,-(y,0) = E,-,.,,oy“"0 + 5,,a,,y"‘, i = 1, . . . ,n, (1.5) and R(y, 1) = C(x, l) = C(x). The system R(y, 0) = 0 in (1.5) is a binomial system with generic coefficients. This type of system can easily be solved [10] and it can be shown that the total number of its zeros equals Vol,.(C) in (1.2). So, by following the solution curves of R(y, t) = 0 starting from the solutions of R(y, 0) = 0 in (1.5) we find Vol,,(C) isolated zeros of G (x) in (0)". Repeating the same procedure for each cell of type (1, . . . , 1) in Sw, all M(A1, . . . ,An) isolated zeros of C(x) in (C‘)" can be found. To find all the isolated zeros of P(x) = (p1(x), . . . ,pn(x)) in C", rather than in (C‘ )”, we may modify the above procedure as follows: According to Theorem 2, when (A1U{0}, . . . ,A,.U{0}) = (A1, . . . ,An), i.e., all p,’s have nonzero constant terms, then the mixed volume M(A1, . . . ,An) also serves as a bound for the number of isolated zeros of P(x) in C", and the algorithm we described above finds all isolated zeros of P(x) in C" indeed. When (A1 U {0}, . . . ,A,. U {0}) # (A1, . . . ,A), we augment the monomial x°(= 1) to those p,’s which do not have constant terms and randomly choose the coefficients of all monomials in P(x) as well as augmented monomials x0, obtaining the system C(x) = (§1(x), . . . , §n(x)) where §,(x) = Z 5,,ax’, i = 1,. .. ,n. aEAgU{O} By Lemma 2.1 in [12], all isolated zeros of C(x) are in (0)" and, by Theorem 1, the total number of its isolated zeros is equal to M(A1 U {0}, . . . , Afl U {0}). It was shown in [11] that by following exactly the same procedure as we described above with C(x) replaced by C(x), all the isolated zeros of P(x) in C" can be found. In summary, to find all the isolated zeros of a given polynomial system P(x) = (p1 (x), . . . , pn(x)) with support A = (A1, . . . ,A,,) in C“ by the above method, which we will refer to as the Li-Wang algorithm in the remainder of this dissertation, one may proceed with the following steps: 0 Lift the extended support A U {0} by a randomly chosen real lifting function U) = (w1,...,w,,). c Find all the cells of type (1, . . . , 1) in the induced fine mixed subdivision 3,, for the extended support A U {0}. o For a polynomial system C(x) with support AU {0} and randomly chosen com- plex coeficients, trace the homotopy curves of R(x, t) = 0 in (1.4) determined by the cells of type (1, . . . , 1) in S“, to find all isolated zeros of C(x) in (0’)". 0 Use the linear homotopy H(x, t) = (1 — t)C(x) + tP(x) = 0 (1.6) to find all the isolated zeros of P(x) in C". Isolated zeros of H (x, O) = C(x) in C” are available after the last step. As we can see, the main computation of this method is on (a) Finding the cells of type (1, . . . , 1) in S“, for the extended support A U {0}, (b) Tracing 2M(A U {0}) homotopy curves. The computation in (a) is quite time consuming. In general, cells of type (1, ‘. . . , 1) in a subdivision induced by a lifting function on are determined by an exhausting search among all the possible Minkowski sums of edges from A1(w), . . . ,An(w) by linear programming techniques [18] which requires an intensive computational effort. In (b), some of the homotopy curves in (1.6) may be extraneous. For instance, . consider the bivariate system [7], 131(3)?!) = 02/ + by" + cxy3, p2(x,y) = dx + ex2 + fx3y. (1.7) For generic coefficients (a, b, c, d, e, f}, this system has six isolated zeros in (C2 and three isolated zeros in ((9)2. However, its augmented system many) = 81+ ay + by2 + 0961/3, g2(x, y) = 52 + dx + ex2 + fx3y 10 has eight isolated zeros in C2. So, one needs to follow eight homotopy paths of the homotopy H (x, t) = 0 in (1.6) to find all six isolated zeros of system (1.7) in C2, and two of them are obviously extraneous. By using the algorithm suggested by Huber and Sturmfels in [7] which we will describe in the next chapter, one can skip following those extraneous paths. Fur- thermore, by their method, isolated zeros of P(x) in C"\(C‘)" can be determined without following any paths in many situations or by following homotopy paths of much smaller systems. However, the trade-off is the requirement of the recursive liftings of the method, which drastically increases the computation effort in (a). 11 CHAPTER 2 Stable Mixed Volumes For a generic polynomial system C(x) = (gl(x), . . . , gn(x)) with support A = (A1, . . ., A"), where gi(x) = Z Emu)“, Z: 11' ° ° an, 36-44 define the homotopy C(x, t) = (g1(x, t), . . . ,g,(x, t)) : C" x (C —> C" by g,(x, t) = g,(x) + t"e,-, i = 1,. . . ,n, (2.1) where k is a positive integer and e,- = 0 if g,(x) has a nonzero constant term, otherwise 5,- is a randomly chosen complex number. This homotopy induces a lifting function too" = (w?", . . . ,wg") on the extended support A U {0} = (A1 U {0}, . . . ,A" U {0}) given by w?’°(a) = 0 if a 6 A4, w?"(0) = k if 0 ¢ A, i=1,...,n. (2.2) Let A? = A,- U {0} for i = 1,...,n and A0 =(A‘1),...,A2). Recall that for any cell C = (C1, . . . ,Cn) of A0, C(wo") = (C1(w°'°), . . . ,Cn(w°’°)) is a cell of A°(w°"), where Ci(w0k) : {(avw0k(a)) I a 6 Ci}: 2: 1a ' ' '1”; 12 and conv(C(w°")) is a lower facet of Swot = C = (C1,...,C,,) cells of A0 . conv(A°(w°")) gives the stable mixed subdivision of A = (A1, . . . , A”) [7]. The coefficients of C(x) are assumed to be sufficiently generic in the sense of Theorem 1 so that system (2.1) has M(A°) isolated zeros in (C‘)" for all but finitely many t and has no zeros in C"\(C‘)" for t ¢ 0. The zeros of (2.1) as algebraic functions x(t) can be written by the Puiseux series expansion near t = O as x(t) 2 et“ + higher order terms in t, (2.3) where a = ((11,. .. ,an) E Q" and ((1,1) is the unique inner normal of conv(C(w°'°)) whose last coordinate is equal to one for some cell C = (C1, . . . ,Cn) of Swat: and e = (e1, . . . ,e,,) E (0)" is a root of the system g,a(x) := Z Egax" = O, i = 1,...,n, 86C; which is determined by the cell C. A branch x(t) converges to a solution of C(x) = 0 in C" as t —> O precisely when the exponents a = (0:1, . . . ,n,.) are nonnegative, while the i-th coordinate of such a solution can vanish only when a,- > O. This observation leads to the following definitions [7]: Let C = (01,. . . ,C,,) be a cell of SwOIe and (ac, 1) = (of, . . . ,af, 1) be the unique inner normal of conv(C(w°“)) in conv(A°(w°’°)) whose last coordinate is equal to 1. In general, when C is a cell of 3,, induced by a lifting w, we shall call such ac the inner normal of the cell C with respect to w. A cell C of Swot. is said to be stable if ac is nonnegative. A cell C of Swot is called a stable mixed cell of A if it is stable and has nonzero mixed volume. For support A = (A1, . . . ,A,,), we define its stable mixed volume, denoted by SM(A1, . . . ,A), to be the sum of the mixed volumes M(C1, . . . , C") over all stable mixed cells C = (C1, . . . ,Cn) of A in Sth. 13 Since the points of A,- remain unlifted under co”, the cell (A1, . . . ,A") appears as a cell of the subdivision Swot. It is, in fact, the unique cell C in Swot. with ac = 0. This stable mixed cell contributes M(A1, . . . ,A") branches in (2.3) which converge to points in (C‘ )" when t —> 0. Each other stable mixed cell C of A in Sth contributes, by Theorem 1, M(C) branches converging to points in C"\((C")" as t —-+ 0. By (2.1), those points constitute the full set of isolated zeros of C(x) in C". We summarize the above discussion in the following theorem. Theorem 3 [7] Counting multiplicities, the number of isolated zeros of P(x) = (p1(x), ...,p,,(x)) in C“ with support A = (A1,...,A,,) is bounded above by the stable mixed volume SM(A1, . . . ,Afl). This bound is exact for P(x) with generic coefficients, provided that P(x) has only finitely many isolated zeros in C“. Remark 1 The stable mixed volume was originally defined in [7] with k = 1. It is easy to see that if C is a cell of Swot with inner normal ac with respect to w“, then C is also a cell of Ska with inner normal kaC with respect to wo" for any real It > 0. Consequently, the set of stable mixed cells remains invariant as It varies since kaC is C nonnegative as long as a is nonnegative. This variation plays an important role in our construction in the next chapter. Based on the derivation of Theorem 3, an algorithm for finding all isolated zeros of a polynomial system P(x) = (p1(x), . . . , pn(x)) in C" with support A = (A1, . . . ,An) where pi(x) = Z ci,axa1 i: 13° ° ' an: aE-Ai which we will refer to as the Huber-Sturmfels algorithm, was suggested in [7] as follows: First of all, if all p,’s have nonzero constant terms, then, as indicated before, the standard polyhedral homotopy described in the beginning of Chapter 1 can find all the isolated zeros of P(x) in C”. When some of the p,’s have no constant terms, namely, (A1 U {0}, . . . ,A,, U {0}) 515 (A1, . . .,A,,), then 14 0 Let fii(x) = Z CiAXn + 5i, 2: 11' ° ° in, :64.- where e, is randomly chosen and is set to be zero if p,(x) already has a nonzero constant term. 0 Use lifting function ka on the extended support AU {0} = (A1 U {0}, . . . ,A,, U {0}) and identify all the stable mixed cells of A in the induced subdivision :3ka. Let S be the set of those cells. 0 For each cell C = (01,...,C,,) E 3, let ac = (a?,...,af) be its inner nor- mal with respect to a)“ with nonnegative components, and find the zeros of 13,0 (x) = (pluck), . . . , pmc(x)) where agape): Z agrees-5,, i=1,...,n, (2.4) 8605M ,3 1 if0¢A,but0€C,, 0 otherwise in (C‘ )" by the standard polyhedral homotopy described in Chapter 1. For each zero e = (e1, . . . ,e,,) of (2.4), let ('3 = (61, . . . ,én) where e,- if 01,0: 0, m 0. ll 0 if a? > 0. Then é is a zero of P(x). If a stable mixed cell C = (C1, . . . ,C,,) in Sis of type (1, . . . , 1), then system (2.4) becomes a binomial system which can be solved easily by conventional techniques. For a stable mixed cell of type different from (1, . . . , 1) whose inner normal has some Zero components, such as the cell A = (A1, . . . ,Afl), further lifting is required to find 15 a fine mixed subdivision of this cell before the polyhedral homotopy method described in Chapter 1 can be used to obtain all isolated zeros of the system (2.4) in (C')“. As we mentioned before, multiple liftings and the identification of cells of type (1, . . . , 1) in their induced subdivisions require an intensive computation effort and occupy a great majority of the computation of this algorithm. Therefore, compared to the Li-Wang algorithm in Chapter 1, this algorithm may cost more in many situations despite it follows no extraneous homotopy paths. Remark 2 Isolated zeros e = (e1, . . . ,e,,) of system (2.4) in ((C‘ )" involve parameter 6 = (51, . . . ,5"). However, from the proof of Theorem 3 in [7], it can be easily shown that the transition from e to e in the last step of the algorithm makes the e-dependent components of e 2 (e1, . . . ,en) zero, and the zero e of P(x) we obtain eventually is independent of e. In [7], it was suggested to solve Z c,,.x‘=0, i=1,...,n (2.5) sea-n.4,- without 6 instead of finding zeros of (2.4). In that case, one must find all isolated solutions of (2.5) in (3" rather than in (0‘)". 16 CHAPTER 3 A Single Lifting In this chapter, we shall present the strategy of a single liftng on the extended support A0 = (A9, . . . ,A2) = (A1 U {0}, . . . ,A,, U {0}) of P(x) when A0 # A. This lifting can identify all the stable mixed cells of A and, in the mean time, provide a fine mixed subdivision for each stable mixed cell. Consequently, the stable mixed volume of the support A = (A1, . . . ,A,,) can be calculated by those fine mixed subdivisions induced by this lifting. Most importantly, recursive liftings are no longer needed as opposed to the Huber-Sturmfels algorithm described in Chapter 2. Let B,- be a nonempty finite subset of N” for i = 1,... ,n, and B = ([31,. .. ,3“). Let S“, be the fine mixed subdivision of 8 induced by a lifting function w = (w1,...,w,,) applied to B. For a cell D = (D1, . . . ,Dn) of 5“,, write Di:{ai0i'°'vaikg}i i=13"',n) where k,- 2 O and k1 + - -- + kn = ii. Let V(D(w)) be the n x (n + 1) matrix whose rows consist of ting-(cu) — 640(w) for i = 1,...,n, j = 1, . . .,k,- with k,- 2 1, and V(D) be the corresponding n x n matrix by deleting the last column of V(D(w)). It is easy to see that Vol,,(conv(D)) = |det(V(D))| which is nonzero since dim(conv(D)) = n. 17 Consider the linear function x1 . . . :137, t fD(w)(x,t) 2: 01x1 + - . ° + anxn + an+1t :2 det . V(D(W)) We may assume that amt 1, the cofactor of t, is positive, namely (—1)“ det(V(D)) > 0, otherwise, we exchange two rows of V(D(w)). Let éo(w) = a10(w) +. - ~ + ano(w). The following lemma is the main tool in our analysis. Lemma 1 The hyperplane L : f [3,“)(x, t) = f,-,(,,,(ao(w)) is the suppbrting hyperplane of conv(8(w)) which contains the lower facet conv(D(w)) and (al, . . . ,an,a,,+1) is an inner normal of conv(D(w)). PROOF: To prove the hyperplane L contains conv(D(w)), it suffices to show that the points of the form 51,,(w) +---+é.,,,-,,(w) where O S j,- S k,, i = 1,...,n all belong to L. Since l 1: fD(w)(éljl(w) + ' ' ' + fine-402)) — fb(w)(é‘0(w)) = fD(w)(élj1(w) + ' ' ' + é‘fljn(w)) _ fb(w)(510(w) + ' '° + 5no(w)) = fb(w)(élj1(wl _ é10(0)» + ' " + fb(w)(é‘njn(w) — 5110049)) and for i = 1,... , n, 51,-], (w)-a,-o(w) is either 0 or a row of V(D(w)), so, f,-,(w,(a,-,-,(w) — a,g(w)) = 0 for all i, and therefore I = 0. Hence, conv(D(w)) C L. Since conv(D(w)) is a lower facet of conv(B(w)) and an“ > 0, (al, . . . ,Otn+1), the normal of L, is an inner normal of conv(D(w)). D We now define our single lifting w = (wl, . . . ,wn) on A0 = (A3), . . . ,Ag) as follows: Fori= 1,...,n, w,(0) = k if 0 ¢ A,, here It > 0 is randomly chosen, (3.1) w,(a) = a randomly chosen number in (0,1) if a E A,» 18 Since the values of w are generically chosen, the induced subdivision conv(D(w)) is a lower facet of 5...: D=(Dl,...,D,,)cellsofA° . conv(A°(w)) is a fine mixed subdivision of A0 [6]. Recall that the stable mixed volume of A = (A1, . . . ,A") is derived from the lifting wo" = (w?", . . . ,wfl") on A”, as defined in (2.2), along with its induced subdivision conv(C(w°")) is a lower facet of 5'th = C: (01,...,Cn) C8118 Of A0 .. conv(A0 (wm‘ )) For a cell C = (C1, . . . ,Cn) of Sth, let we = (of, . . . ,wf) be the restriction of the function w = (021,. . . ,wn) on C. Its induced subdivision ch = D = (D1, . . . ,Dn) cells of C conv(D(w)) is a lower facet of conv(C(w)) gives a fine mixed subdivision of C since 010 is generic on C. Our main claim is that when the value of k in the lifting w is sufficiently large, then ch C S”. That is, the subdivision 5",, induced by the lifting w on A0 does not alter the original configuration of the subdivision 15'th induced by the lifting w” on A0. More precisely, 5,, is finer than Swab in the sense that any cell D = (D1, . . . , D") of 3,, is a subcell of a cell C of 5'th. Consequently, subcollections of cells of 5,, provide fine mixed subdivisions of cells of SwOIz. In the remainder of this dissertation, we let d = Illa-X199; deg p,-(x). Proposition 1 When It > n(n + 1)d", then for cells C = (C1,...,C,,) of Ska, we have ch Q S“. To prove Proposition 1, we first present the preliminaries. Let D = (DI, . . . ,D,,) be a cell of ch and D.={a.o,....a.,..}. i=1....,n, 19 where k,20and k1+~--+k,,=n. Then { an —310 \ 81kl - 310 V(D) = an] — anO K 3111:" — anO } Note that if k,- = 0, then D,- does not contribute any row to the n x n matrix V(D). Let a,- E A? and E be a matrix obtained by replacing one row of V(D) by a,- —— aw. Lemma 2 |det(E)| _<_ d". PROOF: We assume the rows of the matrix E are linearly independent, otherwise, det(E) = 0. For notational simplicity, we rewrite the rows of E as, b11 — b10 bnl—bnO Since b,0,b,-1 g A9, fori = 1,...,n and 1 S j, S n, CE = J: ({b10,b11}, . . . , {bno,b,,1}) is a cell of the support (AQ ”Ag-L) of the new poly- 11’“ nomial system PE(x) = (pj1 (x) + Ej1,..., pjn(x) + 5,"). Here, j1,.. . ,jn may not be all different. A positive random lifting on (A9 o ,1, - . - a Ajn) can always be arranged for which the cell CE remains unlifted, that is, the points in CE receive the lifting value 0 and lifting values for points not in C E are all positive. For such a lifting, CE becomes a type (1, . . . , 1) cell of the resulting induced fine mixed subdivision of (A9 . ,AQ ). Jl’” Jn Consequently, [det(E)] = Voln(conv(CE)) S./\/l(AQ .71" ..,.43n) 20 < II};1 deg pj,(x) (the total degree of PE(x)) 3d". :1 Remark 3 The most important case is when the cell D = (D1, . . . , D“) is of type (1, . . . ,1). Let (1, = deg p,(x) for i = 1,. . . ,n. Without loss of generality, we assume d1 3 d2 3 S d,,. Then a similar argument shows ldet(E)| S MMQ Ji" --w43..) < d2X---xd,,xd,,. For sparse polynomial systems arose in applications, both M(A§e’1, . . . ,Ag) and d2 x - - - x d,, x d,, are usually much smaller than at”. Lemma 3 For any ahb, 6 A9, let 6.- = lwdae') " w,(b,-)] — lw?k(3e') " w?’°(b,-)], i: 1, - - - ,n. Then —1 S 5,51 and fl,- is independent ofk for alli = 1, . . . ,n. PROOF: For fixed i, if 0 E A,, or 0 g A,- but none of a,,b,- equals 0, then w?’°(a,-) = w?’°(b,-) = O and both w,(a,~) and w,(b,-) are between 0 and 1. So, fl,- 6 (—1,1). If one of m,b,- is 0 52 A,-, say a,, then w,(a,) = w?"(a,~) = k and w?"(b,~) = 0, and so, lat = —wi(bi) 5 (—1,1). D Proof of Proposition 1: Since D is a cell of C which by itself is a cell of the subdivision 5'ka of A0, so, by Lemma 1 the supporting hyperplane which contains 21 conv(D(w°")) is fb(wo,.)(x, t) = fb(wo,,)(ao(w°")) where i (let) ) 9110.00") __ 510(0)“) £111: (0)“) — é100110") ff)(w°k)(x: t) = det 1 51:1 (600k) — éno(w°") (MM) — and“) j and éo(w°") = 510000") +- . -+a,,o(w°’°). Again, only those D,’s with k,- 2 I contribute to the rows of the above matrix. Assume the normal of this supporting hyperplane is an inner normal of conv(D(w°")), i.e., the coefficient of t in fb(wo..)(x, t) is positive. On the other hand, since D is a cell of ch, the supporting hyperplane of C (w) containing conv(D(w)) is fb(w)(x, t) = fb(w)(ao(w)) where f (x, t) \ A a11(w) -" 510(0)) 511:; (w) — é11000) fD(w)(xi t) = det . i A én1(w) - 511.0(0)) (and) — 5.0M ) and éo((.U) = é10(LU) + ' ' ‘ 'l‘ 5,100.0). To prove D is a cell of S”, we need to show that conv(D(w)) is a lower facet of conv(A°(w)). That is, for any a = a1 + - - - + an E conv(A°)\conv(D) where a,- E A? 22 for i = 1, . . . ,n, we want to prove fD(w)(a(w)) > f,-,(,,,(ao(w)), or, fb(w)(é(w) " é()(Wll > 0- (3-2) If a E conv(C), then the inequality in (3.2) is true since D is a cell of ch and (.00 E w on C. If a Q conv(C), we actually have fD(w0,,)(é(w0k)) > ff)(w0h)(é0(w0k))' Namely, ( awn—sow“) ) 511 (010k) - é10W“) . . fine. (w°") — éio(w°") fb(uo~)(a(w0k) — 30(w0k)) = det > O. 501(w0k) _ 51,0(w0k) (agar) — anew“) ) The entries of the last column of the matrix above consist of either 0 or iii except the first entry which equals imlk for certain integer 0 g m1 3 n. So, expending the determinant by its last column gives fD(w0k)(é(w0k) " 50(w0k)) = mk, 23 where m is a positive integer. Now, n f a — ao Elna-(ale) - we(a.-o)l \ i=1 a11 — a10 011(311) — w1(a10) . det 31k; - a10 w1(31k1) — w1(alo) fb(..,)(é(w) - ao(w)) = anl — anO wn(an1) — wn(ano) ( an)... — ano wn(ankn) - wn(a..o) ) { a—ao le?k(ae)—w?k(aeo)l+fio\ 811 — a10 w?"(an) — wImam) + ,611 __ det alkl — alO w?k(alk1) — w?k(310) + ,Blkl an] — anO w9.*(an1) — w2"(ano) + 57:1 ( an]... — anO w9.’°(ame,.) — w2*(ae.o) + flea... } wherefori=1,...,nandlgjgk,, [30 = lee(ae) — we(ae-o)l - le?"(ae) — w?"(ae-o)l i=1 and fies = lwdav) — we(a.-o)] - [w?k(a,-j) — w?"(a,~o)]. 24 It follows that 1ka) __ 50(w0k) \ N 93 511 (010k) — 5110(w0") é1k: (ka) - é10(W0k) (w) — 50(0)» det m) éfl1(w0k) — éno(w0k) \ angle“) — snow“) ) ‘ l = fb(w0k)(5(w0k) — é0(u1m°)) -i- det + det ( a—ao 50\ all — a10 511 811:1 — a10 filkl anl — anO 57:1 \ ankn - anO .Bnlcn } a—ao flol a11 ‘ a10 311 811:1 “ a10 511:1 as: - ano ,Bnl { 81—310 a11 — a10 31k — a10 = mk + 22;, det 1 ani—ano \ankn — ano 25 \ fink” — anO ,Bnkfl f a0 ) a. fine, ,Bnl rank" ) where, by Lemma 3, for all 1 S i S n and 1 g j S k,, 5:5 E (—1, 1) and flea = [we(ae-) - w.(a.-o)] - IW?k(ae-) — w?'°(aeo)l 6 (—1,1)- Expanding the determinants above according to their last columns whose elements all have absolute values less than one, we have, by Lemma 2, ( ai-aiO fii0\ a11 — a10 511 all: —310 51k det l 1 <(n+1)d", i=1,...,n. 31:1 — anO finl K fink“ - 3110 finkn f Thus, f,-,,,,,(s(w) - ao(w)) > mk — n(n + 1)d" > 0 since It > n(n +1)d" and m is a positive integer, and thus (3.2) is proved. C] We are now in a position to identify the stable mixed cells of A0 and their fine mixed subdivisions induced by the lifting 0.). Let SW = {D= (D1,...,D,,) E 5,, | D,- §A,-,i = 1,...,n}. Apparently, SW4 gives a fine mixed subdivision of the stable mixed cell A = (A1,...,A,,). For D = (D1,...,D,,) E Sw\S,,,.4, where D, = {mo,...,a,k,} for 26 i=1,...,n, thenx (n+1) matrix ( 611(w0k)—élo(w0k) \ 511:1(w0k) — 310(w0k) V(DWOkll — finl(w0k) _ én0(w0k) ( are“) — anew) ) is of rank n. Therefore, one can find a vector 610 = (exp, 1) = (a?,...,a2,1) such that V(D(w°"))&D = o. (3.3) Clearly, aD = (a9, . . . , af) is the inner normal of D with respect to the lifting wo". For the collection of cells {D(1), . . .,D(‘l} g Sw\S,,,.4 with the same inner normal or = (a1, . . . ,0") with respect to cum“, let Q=Uwfit=rmm i=1 and C = (Cl, . . . , Cn). It is clear that conv(C(w°")) is a lower facet of conv(A°(w°’°)) with inner normal (0,1). So, C becomes a cell of Swat with inner normal 0: = (011, . . . ,m,) with respect to too" and has a fine mixed subdivision ch := {D(1), . . . , Dm}. When a is nonnegative, C is a stable mixed cell of A in :5th and the mixed volume of C, M(C), is equal to the sum of the volumes of cells of type (1, . . . , 1) in ch. In this way, we have discovered all the stable mixed cells of A with their fine mixed subdivisions. And, the stable mixed volume, defined to be the sum of the mixed volumes of all those stable mixed cells, can easily be calculated by adding all the volumes of cells of type (1, . . . , 1) in those subdivisions. 27 CHAPTER 4 The Main Algorithm From what we have derived in Chapter 3, we now propose a new algorithm for finding all isolated zeros of the polynomial system P(x) = (p1(x), . . . ,pn(x)) in C". As indicated in Chapter 2, the Huber-Sturmfels algorithm requires recursive liftings, which is computationally costly. Our algorithm, a refinement of the Huber-Sturmfels algorithm, employs only one lifting in the whole course. The main algorithm consists of three major parts: First of all, by assigning lifting w = (w1,...,w,,) defined in (3.1) on the extended support A0 = (All), . . . ,Ag) 75 A, we find all stable mixed cells C of A with M(C) > 0 along with all cells of type (1, . . . , 1) in their fine mixed subdivisions induced by wC, the restriction of w on C. Secondly, we choose a generic polynomial system C(x) = (91 (x), . . . ,g,,(x)) with the support A0, where g,-(x) = Z 5,,.x‘, i = 1,...,n. 86A? And for a given stable mixed cell C = (C1,...,C,,) with M(C) > 0 and inner k C normal ac = ((11,. . . ,m,) with respect to (do (a can be found simply by solving the linear system in (3.3) with a cell of ch as D), we solve all isolated zeros of Gac(x) = (glac(x), . . . , gnac(x)) where g,ac(x) = Z aux", i = 1,... ,n. 860.- 28 in (0)". Third, we find all isolated zeros of P(x) in C" by linear homotopies between Gac(x) and Pac(x) = (plac(x), . . . ,pmc(x)) where piac (X) = Z Cifixa + mam, i = 11' ' ° an) aECJM“ '6 1 if0¢A,-but0€C,-, 0 otherwise. Algorithm : 0. Let d = mans-5,, deg p,(x). Choose a real number k > n(n + l)d” at random. 1. Lift the extended support A0 = (A?,...,A9,) by a random lifting w = (w1,.. .,w,,) as defined in (3.1), that is, for i = 1, . . . ,n, w,(a) = a randomly chosen number in (0,1) if a E A,. Find the cells of type (1, . . . , 1) in the induced fine mixed subdivision 5,, of A0. 2. Choose a generic polynomial system C(x) = (gl(x), . . . ,g,,(x)) where g,(x) = Z me“, i: 1,...,n. aEA? The collection of cells Swat 2 {(D1,...,Dn) ES“, I Di QA for all 1 Sign} gives a fine mixed subdivision of A = (A1, . . . ,Afl). Let 5(0) be the set of cells of type (1,. . . ,1) in 5,” found at step 1. Use these cells in 5(0) to find all the isolated zeros of P(x) in (0’)“ by the polyhedral homotopy described in Chapter 1 with lifting a)", the restriction of w on A. 29 3. For a cell D = (D1, . . . ,D,,) of type (1, . . . , 1) in 5w\5,,,4, write D, = {810,841}, 2: 1, . . . ,n. (4.1) I: For i = 1, . . . ,n andj = 0,1, let é,,(w°’°) = (a,,-,w°"(a,-j)) as before, where w” is defined in (2.2), and form the n x (n + 1) matrix 511(w0k) _ 910(w0k) V : Find the unique vector (0:0 , 1) = (ofJ , . . . ,af , l) in the kernel of V. Apparently, 010 is the inner normal of D with respect to too". Let 5(a) be the collection of all cells of type (1,... ,1) in 5,,\5,,,.4 with the same nonnegative inner normal (1 = ((11,... ,m,) with respect to too". 4. (a) Choose a cell D from 5 (0), using the same notations as in (4.1), let 0.- = {a e .42 I <é(w°"),d> = (ao(w°’°),a>}. 2': 1, . . . ,n. Then C = (C1, . . . , Cu) is a stable mixed cell of A in Swab with mixed volume M(C) >0. Let 5,,c={(D1,...,D,,)65,,, | D,§C,fora111§ign}. Then ch is a fine mixed subdivision of C and 5(0) consists of all the cells of type (1,...,1) ofC in ch. We now solve the system Gac(X) = (91ac(X)ee ~ . ,gnac(X)) (4.2) in (C‘)", where giac (X) = Z mea, 2: 1, . . . ,n. HEC.’ 30 When system (4.2) is not a binomial system, then the polyhedral homotopy method described in Chapter 1 can be applied to find all its isolated zeros in (C‘ )" with the cells of type (1, . . . , 1) in 5(a) grouped at step 3, and lifting Inc, the restriction of the lifting w on C. (b) Let Pac(x) = (plac(x), . . . ,pnac(x)), (4.3) where piac (X) = Z Ci,ax. + [Biéifih i = 1) ' ° ' an) aECiO-Ai with fi 1 if0¢A,-but0€C,-, 0 otherwise. All the isolated zeros of Poo (x) in (C‘ )" can be found by following the homotopy curves of the linear homotopy H(x, t) = (I — t)Gac (X) + tPaC (x) starting from the zeros of Cac(x) at t = 0. (c) For zeros e 2 (e1, . . . ,en) of system (4.3), let é = (61,. . . ,én), where e,- if a,- = 0, 6i: 0 ifa,7é0. Then e is a zero of P(x) in C“\(C')". Remark 4 We can see that in our algorithm, only cells of type (1, . . . , 1) in 5,, are used. Therefore, as suggested in Remark 3, choosing k > n(n + 1)d2 x ---d,, x d,, is sufficient for our need, where d,’s are defined in Remark 3. Currently, we are not aware of better lower bounds for k which are also easy to obtain computationally. 31 Remark 5 It is commonly known that when the polyhedral homotopy method is used to solve polynomial systems, large differences between powers of t in the poly- hedral homotopies may cause computational instability when homotopy curves are followed. In our algorithm, the point 0 often receives very large lifting value 1:, com- pared to the rest of the lifting values in (0, 1). We will show in the following that the stability of our algorithm is independent of the large lifting value 1:. Let D = ({a11,a10},...,{a,,1,a,,0}) be a cell of type (1,...,1) E 5w\5,,4 and a subcell of a stable mixed cell C = (C1, . . . , C") of A. Using the notations introduced in the previous chapters, the inner normal of D, denoted by a”, with respect to the lifting w satisfies a11 — 310 w1(a11) — w1(alo) 01D = 0, am — anO wn(an1) - wn(an0) 1 or, V(D)aD + u(w) = 0, (4.4) where an — 310 w1(a11) - w1(aio) V(D) = 5 and u(w) = am — anO wn(a..1) — wn(an0) Let the inner normal of stable mixed cell C with respect to the lifting too" be ac, then 811 — a10 w?k(311) — w?k(310) 010 = 0, an] — anO w2’°(am) — w9.*(ano) 1 or, V(D)aC + n(wo") = 0, (4.5) 32 where w?k(311) - w?k(310) 0k) : u(a) w2k(an1) — w2k(ae.o) Let )6 = (51,. . . ,fln)T = u(w) — u(w°"). Then 5:“ = [wi(a~i1)"‘ wi(ai0)] - [winks-1) — w?k(a,-o)], i = 1,... ,n. By Lemma 3, ,8,- E (—1, 1) for i = 1,... ,n, and they are independent of the value k. Subtracting (4.5) from (4.4) yields V(D)(aD — a0) + c = 0. It follows that “(JD — 00]] is independent of It. When the polyhedral homotopy g,(y,t) = Z 5,,.y‘t<°’°>+“"(°), i = 1,... ,n (4.6) .606 as in (1.3), is used to solve the system g,ac(x) = Z 5,,ax‘, i = 1,...,n ang in (C‘ )", large differences between exponents of t will result in large exponents of t for certain terms in the final polyhedral homotopy in (1.4) when we factor out the lowest power of t. Large exponents of t in the resulting homotopies sometimes cause numerical instability of the curve-tracing of the homotopy paths. Now, for a, b E C,, since (lace 1), (aew?k(a)> = ((aC,1), (bew?"(b)>, we have