This is to certify that the dissertation entitled Balancing Lifting Values to Improve Numerical Stability of Polyhedral Homotopy Continuation Methods presented by Mengnien Wu has been accepted towards fulfillment of the requirements for PhD degree in Mcklhelvm‘tl‘CS \ / / [,/’ Malor professor I Date 0] /17(/0(> MS U i: an Affirmative Action/Equal Opportunity Institution 0-12771 _.._ .__t —- _.___- 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 DEC 2‘3 @005 6/01 e/CIRC/DataDuepSS-sz Balancing Lifting Values to Improve Numerical Stability of Polyhedral Homotopy Continuation Methods By Mengnien Wu A DISSERTATION Submitted to Michigan State University in partial fulfillment of the requirements for the degree of DOCTOR OF PHILOSOPHY Department of Mathematics 2000 ABSTRACT Balancing Lifting Values to Improve Numerical Stability of Polyhedral Homotopy Continuation Methods By Mengnien Wu Polyhedral homotopy continuation methods exploit the sparsity of polynomial sys- tems so that the number of solution curves to reach all isolated solutions is optimal for generic systems. The numerical stability of tracing solution curves of polyhe- dral homotopies is mainly determined by the height of the powers of the continuation parameter. To reduce this height we propose a procedure that operates as an interme- diate stage between the mixed-volume computation and the tracing of solution curves. This procedure computes new lifting values of the support of a polynomial system. These values preserve the structure of the mixed-cell configuration obtained from the mixed-volume computation and produce better-balanced powers of the continuation parameter in the polyhedral homotopies. 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 would also like to thank Professor Chichia Chiu, Professor Ronald Fintushel, Professor Michael Frazier and Professor William Sledd, for their time and advices. iii TABLE OF CONTENTS LIST OF FIGURES LIST OF TABLES INTRODUCTION 1 Polyhedral Homotopy 1.1 Bernshtein Theory .............................. 1.2 Polyhedral Homotopy ............................ 1.3 Numerical Stability of Polyhedral Homotopies ............... 2 Balancing the Powers by the Sandwich Model 2.1 A Fundamental Observation ......................... 2.2 Setup of The Sandwich Model ........................ 2.3 Reducing the Size of the Sandwich Model ................. 3 Numerical Experiments BIBLIOGRAPHY iv 1.1 2.1 2.2 2.3 2.4 LIST OF FIGURES Solution curves of P(x, t) = 0 ........................ 9 An illustration of normal inequality (2.13) ................. 31 Mixed cell configurations of (A1, A2) .................... 33 Cayley embedding of~A1 and A2 ....................... 34 Circuit Z = {5, b,E, d,5} and projections of T+ and T‘ ......... 36 LIST OF TABLES 3.1 Sizes of the Linear Programming problems. Here, n is the number of variables of the polynomial system and #Mw is the number of mixed cells in the mixed-cell configuration Mm. ................ 39 3.2 Height of Powers and CPU Time in Seconds. The averages are obtained from ten different random liftings ..................... 40 vi Introduction During the last two decades, homotopy continuation methods have proven to be reliable and efficient to compute numerical approximations to all isolated zeros of polynomial systems. To exploit sparsity of polynomial systems, polyhedral homotopy continuation methods emerged in [HuSt95, VVC]. For generic polynomial systems, the number of solution curves to be traced is optimal. We refer to [Li97] for a survey on recent advances in homotopy continuation methods for polynomial systems. Polyhedral homotopies are nonlinear in the continuation parameter. Powers of the continuation parameter too close to zero can be scaled away from zero by a suitable scalar multiplication. After scaling, if very high powers exist in a polyhedral homotopy, small step sizes must be taken in order to successfully trace a solution curve of the polyhedral homotopy. Although the end of the solution curve can be reached as long as the required step size is not smaller than the available machine precision, the efficiency of the curve-tracing is greatly reduced. A more serious problem occurs when the continuation parameter, starting from 0, is not yet close enough to 1, some terms of the polyhedral homotopy with high powers of the continuation parameter have values smaller than the machine precision and some solution curves may come close to “valleys” where the values of the homotopy are numerically zero, but no solution curves exist inside the “valleys”. This situation can easily cause the curve-tracings to be trapped in these “valleys” with no chance of reaching the ends of solution curves unless the curves are retraced with smaller step sizes. Two known geometric approaches to control the numerical stability of polyhedral homotopy continuation methods are recursive liftings (as in Bernshtein’s algorithm [Bern, WC]) and dynamic liftings [VGC]. However, because of using multiple liftings or flattenings, these approaches both require more expensive construction of subdi- visions and create more homotopy curves which need to be traced than a random floating-point lifting. To minimize the height of the powers of the continuation parameter in polyhedral homotopies, we search in the cone of all lifting vectors that induce the same mixed- cell configuration to obtain better-balanced powers of the continuation parameter of polyhedral homotopies. This idea can also be found in the proof of Proposition 1.11 in [St96]. This dissertation is organized in the following manner: In Chapter 1, we start with the polyhedral homotopy method and its numerical stability; in Chapter 2, the idea originated from the construction of the polyhedral homotopy to balance lifting values is given, followed by the setup of the linear programming model for balancing lifting values as well as the reduction of the size of this LP model; and finally, some numerical experiments are presented in Chapter 3. CHAPTER 1 Polyhedral Homotopy To solve a polynomial system P(x) = (p1(x), - . - ,pn(x)) in C" by the homotopy continuation method, the homotopy H (x, t) : C" x [0,1] —> C" needs to posess the following properties: 0 Property 1 (Triviality). The solutions of H (x, 0) = 0 are known. 0 Property 2 (Smoothness). The solution set of H (x, t) = 0 for 0 S t _<_ 1 consists of a finite number of smooth paths, each parametrized by t E [0, 1). 0 Property 3 (Accessibility). Every isolated solution of H (x, 1) = P(x) = 0 can be reached by some path originating at t = 0, i.e. this path starts at a solution of H(x,0) = 0. When H (x, t) = 0 defines a homotopy that satisfies above properties, the number of isolated zeros of H (x, 0) must be no fewer than the number of isolated zeros of P(x). Unfortunately, the former is in general much greater than the later, resulting in a considerable waste of computational effort in following extraneous paths in practice. The Bernshtein theory on root count of polynomial systems is essential for our at- tempt to reduce the number of homotopy curves need to be traced when the homotopy continuation method is employed to find all isolated zeros of polynomial systems. In the first section of this chapter, the Bernshtein theory on root count in (0)", where C“ = C\ {0}, as well as its extension to root count in C” are presented. In the second section, the polyhedral homotopy, based on the Bershtein theory, for finding all isolated zeros of a polynomial system is introduced. In the last section, we will discuss the method to solve a binomial system, so that initial solutions of a polyhedral homotopy can be identified. 1.1 Bernshtein Theory Let the given polynomial system be P(x) = (p1(x), - - - ,pn(x)) E C[x], where x = (9:1, - - - ,2"). With xq = :c‘fl . - - 2:3," where q =(q1, - - - ,qn), write 191(3‘) = ch’qxq, (1651 (1.1) pn(x) : Z Cquq’ qESn where 31,- - - ,5a are fixed subsets of N” with cardinals kj = #Sj, and cm 6 C“ for q E Sj, j = 1, - - - ,n. We call 33- the support of pJ-(x), denoted by spt(pj), its convex hull Qj = conv(S,-) in R" the Newton polytope of 17,-, and S = (8'1, - - - ,3“) the support of P(x), denoted by spt(P). We now embed the system (1.1) in the system P(c,x) = (p1(c,x), . ~ . ,pn(C,x)), where p1(c, x) = Z Cquq, ‘1651 (1.2) pn(C,X) = Z cfliqxq) £165.. and the coeficients Cm with q E 5,, for j = 1, - - - ,n in the system are taken to be a set of M := k1 + - -- + kn variables. Namely, the system P(x) in (1.1) is considered as a system in (1.2) corresponding to a set of specified values of coefficients c = (cm) or P(x) = P(c,x). We shall refer to the total number of isolated zeros, counting multiplicities, of a polynomial system as the root count of the system. Lemma 1 [Hu96] For polynomial systems P(c,x) in (1.2), there exists a polynomial system G(d) = (gl(d),---,g,,(d)) in the variables (1 = (dm) for q E Sj and j = 1, - - . ,n such that for those coefficients c = (cm) for which G(d) d = c 75 0, the root count in (C‘ )" of the corresponding polynomial systems in (1.2) is a fixed number. And the root count in (C‘)” of any other polynomial systems in (1.2) is bounded above by this number. Remark 1 Since the zeros of the polynomial system G (d) in the above lemma form an algebraic set with dimension smaller than M, its complement is open and dense with full measure in CM . Therefore, with probability one, G (d) 75 0 for randomly chosen coeficients d = (din) E CM . Hence, polynomial systems P(c, x) in (1.2) with G (c) 76 0 are said to be in general position. Theorem 1 (([Bern], Theorem A)) The root count in (0)" of a polynomial sys- tem P(x) = (p1(x), . . . , pn(x)) in general position equals to the mixed volume of its support. The terminology in this theorem needs explanation. For non-negative variable A1, - - - , A“ and the Newton polytopes Q; ofpj, for j = 1, ~ - -,n, let AIQI + - - - +AnQn denote the Minkowski sum of A1621, - - - , AnQn, that is, A1Q1+"'+AnQn= {A1T1+"'+An7‘n rjEQj,j=1,°--,n}. It can be shown that the n—dimensional volume vol,,()‘1Q1 + + AnQn) of this polytope is a homogeneous polynomial of degree n in A1, - - - , A". The coefficient of 5 the term Al x x A" in this homogeneous polynomial is called the missed volume of the polytopes Q1, - - - ,Qn, denoted by M(Q1, - - - ,Qn), or the mixed volume of the support of the system P(x) = (p1(x), - - - ,pn(x)), denoted by M(Sl, - - - ,5“) where 51- = spt(pj) for j = 1, - - - ,n. Sometimes, when no ambiguities exist, it is called the mixed volume of P(x). In [CaRo], this root count was nicknamed the BKK bound after its inventors, Bernshtein [Bern], Kushnirenko [Ku76] and Khovanskii [Kh78]. In general, it provides a much tighter bound compared to variant Bézout bounds [MoSo, Shat]. An apparent limitation of the theorem is that it only counts the isolated zeros of polynomial systems in (C’ )" rather than all the isolated zeros in the affine space C". For the purpose of finding all the isolated zeros of a polynomial system in C", a generalized version of the theorem which counts the roots in C" is strongly desirable. This problem was first attempted in [CaRo] where the notion of the shadowed sets was introduced and a bound for the root count in C” was obtained. Later, a significantly much tighter bound was discovered in the following theorem. Theorem 2 ([LiWa96]) The root count in C" of a polynomial system P(x) = (p1(x),--- ,pn(x)) with supports Sj = spt(pj), j = 1,-~ ,n, is bounded above by the mixed volume M(.5'1 U {0}, . . . , 3,, U {0}). In other words, the root count in C" of a polynomial system P(x) 2 (p1 (x), - - - , pn(x)) is bounded above by the root count in ((C‘ )" of a polynomial sys- tem in general position with support equal to spt(pj) U {0} for all j = 1, - - - ,n. As a corollary, when 0 E spt(pj) for all j = 1,--- ,n, namely, all pJ-(x) in P(x) have constant terms, then the mixed volume of P(x) also serves as a bound for the root count of P(x) in C", rather than in (0)" as Theorem 1 asserts. This theorem was further extended in several different ways [HuSt95, RoWa]. 1.2 Polyhedral Homotopy In light of Theorem 2 given in the last section, to find all isolated zeros of a given polynomial system P(x) = (p1(x),---,p,,(x)) in C" with support 5' = ($1, - - - ,3“), we first append the monomial x° = 1 to those pj’s which do not have constant terms. Followed by choosing coeficients of all the monomials in the system generically, a new system with support A = (A1, - - . ,An) is obtained, where, of course, Aj = Sj U {0} for j = 1, - - - ,n. In this section, we may assume 0 E A,- := spt(pj) and write Pl(x) = Z Cquq, qEAi P(x)-_- 5 (1-3) pn(x) = Z Cniqxq! qun with all generically chosen coefficients cm for q E A,- and j = 1, - . - ,n, this system may be considered as a system in general position. Namely, there exists a polynomial system G(d) = (9101),” - ,9m(d)) (1-4) in the variables d = (dm), for q E Aj, j = 1, - - - ,n, such that polynomial systems with coefficient c = (cm) for which G (d) d _ c # 0 reach the maximum root count in (C‘ )“ for the support A = (A1, - - - ,A"). Let t denote a new complex variable and consider the polynomial system P(x, t) = (fidx, t), - - - , fin(x,t)) in the n + 1 variables (x, t) given by 51(x, t) = Z claxthil‘fi, qEAi P(x, t) = (1 5) §n(x,t) = Z cu,qxqt“’"(“), qEAn where each wj : A,- -—> IR for j = 1, - - - ,n, known as a lifting is chosen generically on Aj. For a fixed 7, we rewrite the system in (1.5) as 51(X,T) = Z 0 because Cj qewfiqwtwflfl = Cj q(tei0)“”'(9) and G(d)|d = (c,-,.,(te"0)w.-(q)) = G(tew) 75 0’ Therefore, without loss of generality (choose an angle 6 at random and change the coefficients cm into cj,qe“"i(“)9 if necessary), we may suppose the systems P(x, t) in (1.5) are in general position for all t > 0. Together with Lemma 1 given in the last 8 section, it follows that for all t > 0 the systems P(x, t) in (1.5) have the same number of isolated zeros in (C‘ )". This number, say It, should equal to the mixed volume of the support of P(x) in (1.3) by Theorem 1. We shall skip this fact temporarily and will reach this assertion at the end of this section. Now consider P(x, t) = 0 as a homotopy, known as the polyhedral homotopy, de- fined on (C‘ )" x [0, 1]. We have P(x, 1) = P(x), and the zero set of this homotopy is made up of k homotopy paths, say, x1(t), - - - ,x"(t), since for each 0 < t S 1, P(x, t) has exactly k isolated zeros from the argument given above. Since each fJ‘J-(x, t) has nonzero constant term for all j = 1, - ~ - ,n, by a standard application of generalized Sard’s Theorem [ChMPYo], all those homotopy paths are smooth with no bifurca- tions. Therefore, both Property 2 (Smoothness) and Property 3 (Accessibility) men- tioned at the beginning of this chapter hold for this homotopy. However, when t = 0, P(x,0) E 0. Consequently, the starting points x1(0), - - - ,x"(0) of those homotopy paths can not be identified, causing the breakdown of the standard homotopy con- tinuation algorithm. This major obstacle can be overcome by the devise we describe below. et- II O H- H H (*v Figure 1.1: Solution curves of P(x, t) = 0 For a = (a1, - - - , an) E IR", consider the transformation x = yt" defined by $1 = 3111501, (1.6) 23,, = ynta". For q = (q1,- - - ,qn) E N", we have x‘l := 2:? - - - 233," = (y1t“1)‘“---(ynt°'")"“ (1.7) _ y‘lll , , , g» t01¢11+"-+0nqn — yq flaw!) . Here, (-, ) stands for the usual inner product in IR“. Substituting (1.7) into (1.5) yields, forj = 1,---,n, def A a ’ w- h?(yit) = pj(yt ,t) = Z Cj,qut(a q)t 1(Q) QEAJ' : Z Ci.qut((°’1)ilqij(Q))) (1.8) QEAJ' = Z cj.qut(a’a), QEAj where a := (q, w,-(q)) for q E A,- and 67 := (a, 1) E Rn“. The new homotopy Ha(yit) = (h?(ytt)1...1h:(Y)t)) = 0 retains most of the properties of the homotopy P(x, t) = 0, in particular, H “(y, 1) = P(y, 1) = P(y) and both Properties 2 (Smoothness) and 3 (Accessibility) stand. Let and define the homotopy flaky, t) : (Hf(yit)i ' ' ' fizb’, t» = 0 10 on (0‘)" X [0,1], where, forj = 1,-~-,n 5,9030 = t'm’hj-‘(LU = Z thyqt‘a’al‘m” (1645 q q <5 ii>-m- (1'9) : 2: cm" + 2: Ciqy t ' 1' QEAJ' QEAJ' (Eva)=mj (6.6))"1j Evidently, for any path y(t) defined on [0, 1], we have, for all t > 0, H (Mt) = 0 «=> Hams») = 0. Therefore, the zero set of Ha(y, t) = 0 consists of the same homotopy paths of the homotopy H c'(y, t) = 0 in (1.8). The difference is, the starting points of the homotopy paths considered in the homotopy Ha(y, t) = 0 are solutions of the system E101(3’1 0) : Z cl,qu = 0a 4641 (5.¢’i>=M1 Irila'(}',0) = 5 (1-10) H:(Yi0) = Z cu,qu:0° (£822... As shown below, when this system is in certain desired form, its isolated nonsingular solutions that lie in (C‘ )" can be constructively identified. In those situations, Prop— erty 1 (Triviality) becomes partially valid for those homotopy paths of Ha(y, t) = 0 that emanate from those nonsingular solutions of (1.10) in (C‘ )", and we may follow those paths to reach a partial set of isolated zeros of P(y) at t = 1. The system (1.10) is known as the binomial system if each h;(y,0) consists of exactly two terms, that is, 5:03 0) = cly“ + 6’13““! = 0, (1.11) 530', 0) = cnY‘" + C’ny‘i = 0, where a,-,a;- E Aj, c,- = cjm and c; = cm; for j = 1, - - - ,n. And in this case, C = ({a1,a’1},---,{a,,,a:,}) is called a mixed cell ofA with inner normal (1, or 11 C = ((31,31},---,{3,,,§’n}) is a lifted mixed cell with inner normal 6 = ((1,1). Alternatively, we say 0: supports cell 0 or 3 supports lifted cell C. Ha(y, t) = 0 is called the polyhedral homotopy on cell 0 induced by w and a. The collection of all mixed cells is called the mixed cell configuration Mu, induced by w. Proposition 1 The binomial system in (1.11) has I a1 —al kc, := det E (1.12) nonsingular solutions in (C‘)“. The number ha is called the volume of the mixed cell ({a1,a’1},-- -,{a,,,a;,}). The proof of this proposition is constructive and therefore provides an algorithm for solving the binomial system (1.11) in (0)". We will come back to this matter in the next section. In summary, for given a = (011,- -- ,an) E R", by changing variables x = yt“, as in (1.6), in the homotopy P(x, t) = (1’51(x, t),---,fn(x,t)) = 0 in (1.5), the ho- motopy H"(y,t) = (h‘f(y,t), - - -,h:(y,t)) = 0 in (1.8) is obtained, where h?(y, t) = @(yta, t). Followed by factoring out the lowest power th' oft among all monomials in each individual hfly, t) = 0 for j = 1, - - - ,n we arrive at the homotopy H°(y, t) = 0 in (1.9). When the start system Ha(y, 0) = 0 of this homotopy is binomial, its non- singular solutions in (C‘ )“, lea (as given in (1.12)) of them, become available. We may then follow those homotopy paths of Ha(y, t) = 0 originated from those he, regular solutions of Ha(y,0) = 0 in (0)", and reach k0, isolated zeros of P(y) at t = 1. Worth notifying here is the fact that the system P(x), or P(y), stays invariant at t = 1 during the process. Now, the existence of a E IR" for which the start system Ha(y, 0) = 0 is binomial is warranted by the following 12 Proposition 2 For all the real functions wj : Aj —-> R, j = 1, - - - ,n being generically chosen, there must exist a E R", for which the start system Ha(y,0) = 0 of the homotopy Haw, t) = 0 in (1.9) is binomial with a nonempty set of nonsingular solutions in (0')”, i.e., ha 76 0 in (1.12). The assertion of this proposition was proved implicitly in [HuSt95] with terminolo- gies and machineries developed in combinatorial geometry, such as, random liftings, fine mixed subdivisions, lower facets of convex polytopes, etc., see also [Li97]. Here, we elect to reinterpret the result without those specialized terms. Now, different a E IR” given in Proposition 2 lead to different homotopy Ha(y,t) = 0 in ( 1.9). Henceforth, following homotopy paths of those different ho- motopies will reach difierent sets of isolated zeros of P(y). By taking the Puiseux series expansions of those homotopy paths of Ha(y, t) = 0 originated at (C‘ )" into consideration, it is not hard to see that those different sets of isolated zeros of P(y) reached by different sets of homotopy paths are actually disjoint from each other. Most importantly, it can be shown that every isolated zero of P(y) can be obtained this way by following certain homotopy curve of the homotopy Ha(y, t) = 0 associ- ated with certain a E R" given by Proposition 2. Thus the total number of isolated zeros of P(y) must equal to the sum of those ka’s corresponding to all the possi- ble a’s provided by Proposition 2, respectively. In [HuSt95], it was shown that this sum actually equal to the mixed volume of P(y). This yields an alternative proof of Theorem 1, it is very different from Bernshtein’s original approach [Bern]. Solving Binomial Systems Another major step in solving polynomial systems by using the polyhedral homo- topy method as we described in the previous section is finding the solutions of the 13 corresponding binomial system clyIll + Glyn; : 0‘) (1.13) cnyan +C’nya; : 0) produced by the mixed cell ({a1,a'1}, - - - , {an,a:,}) as in (1.11). We now discuss the method for solving (1.13) in (0')". Let , o vj=aj—a,-a J=1,---,n, and, with y E (C‘ )" in mind, we rewrite the system (1.13) as yvl = bl) (1.14) yvn = bni where b_,- = —-C-1 forj= 1,---,n. Let i V:],,1T]... v5] (1.15) and for brevity, write yV=(yvl,.H,yvn) and b:(bli'”1bn)- Then, (1.14) becomes, yV = b. (1.16) With this notation, it is easy to verify that for an n x n integral matrix U, we have, by)” = 34"”)- Now, when the matrix V in ( 1.15) is an upper triangular matrix, i.e., ' ] v11 v1n 14 then the equation in (1.16) becomes ylm : b1, yUIva22 = b2, 1 2 (1.17) yi‘"y§”"---yi’.“" = b... By forward substitutions, all the solutions of the system (1.17) in (C‘ )" can be found, and the total number of solutions is |v11| x x |v,,,,| = |det V]. In general, we may upper triangularize V in (1.15) by the following process. Recall that the greatest common divisor d of two nonzero integers a and b, denoted by gcd(a, b), can be written as d := gcd(a, b) = ka + (b, for certain nonzero integers k and Z. Let 11: Z B = _9 2 d d We have det(B) = 1, and a k f a d B = = b —3 g b 0 Similar to using Givens rotation to produce zeros in a matrix for its QR factorization, the matrix B may be used to upper triangularize V as follows. For v E Z", let a and b be its ith and the jth (nonzero) components where i < j, that is, Let d := gcd(a, b), and F1 ' I k 8 2th 1 Ugj I: (1.18) l b a, 'th _3 d J 1 1 .l Evidently, U,,- is an integeral matrix with |det Uijl = 1 and d ith U,,-v= Thus a series of matrices in the form of U,,- in (1.18) may be used to successively produce zeros in the lower triangular part of the matrix V in (1.15), resulting in an upper triangular matrix. In simple terms, we may construct an integeral matrix U , as a product of those Uij,s, with |det U | = 1 and UV is an upper triangular integeral matrix. Now, as mentioned above, the solutions of the system (zU)V = zUV = b (1.19) in (C‘ )" can be found by forward substitutions, since UV is an upper triangular integeral matrix. And the total number of solutions in (0')" is |det(UV)| = |det U| - |det V] = |detVl. By letting y = zU for each solution 2 of (1.19) in (C’ )", we obtain all the solutions of the system (1.19) in (C‘ )", and hence, solve the system (1.13) in (0‘)". 16 1.3 Numerical Stability of Polyhedral Homot0pies To solve a specific polynomial system P*(x) of support spt(P*) = A = (A1, - - - ,A), where A,- C Z", 3' = 1, - - - ,n, we first solve a corresponding generic system P(x) with spt(P) = spt(P*), and then use the linear homotopy H(x, t) = (1 — t)P(x) +tP*(x) = 0 to solve P*(x) = 0. To solve the generic system P(x) = 0, we use the polyhedral homotopy method. Let’s briefly recall the procedure: A random lifting w = (w1,--- ,wn) will induce the mixed cell configuration M“, of support A. For a cell 0 = (C1, . . . , C") E M“, with inner normal 0:, the corresponding polyhedral homotopy Holy, t) = 0 yields that Ha(y,0) is a binomial system with support 0’ and Ha(y, 1) = P(y). If powers of t in the polyhedral homotopy Ha(y, t) = 0 are too high or too close to zero, instability might occur in tracing solution curves of Holy, t) = 0 unless very small step sizes are taken. For the standard prediction-correction method [AlGe93] in tracing a curve, the number of steps required for homotopy curves with high powers of t is usually much greater than those for other curves. This may severely reduce the efficiency of the algorithm. A more serious problem can occur when curve-tracings are trapped into “valleys” where the values of the polyhedral homotopy are numerically zeros, but no solution curves exist inside the “valleys”. Example 1 Consider the polynomial system P(x) = (p1(x),p2(x)) = 0 with x = (x1, x2), where p1(x) = c1x§+ c2x§ + c3 = 0, p2(x) = c4x§xg + c5x1 + c6332 = 0, with support A = (A1,A2), where A1 = {(2,0), (0,2), (0,0)} and A2 = {(3,3), (1,0), (0, 1)}. This system has mixed volume M(A) = 12. 17 Choose a random lifting w = (021,022) where col : A1 —> IR and 022 : A2 —+ IR with 01((2, 0)) = 0.655416, w1((0, 2)) = 0.200995, 01((0, 0)) = 0.893622, 02((3,3)) = 0.281886, w2((1,0)) = 0.525000, w2((0,1)) = 0.314127. Then the mixed cell configuration Mw in the fine mixed subdivision of A induced by (12 consists of two mixed cells: C = ({(2,0), (0,2)}, {(3,3), (1,0)}) with inner normal (1, C" = ({(0, 2), (0, 0)}, {(1,0), (0, 1)}) with inner normal 6. To construct the system P(x) = 0, we choose the following set of randomly generated coeficients, c1 = —0.434847 — 0.169859i, c2 = 0.505911 + 0.405431i, c3 = 0.0738596 + 0.177798i, c4 = —0.0906755 + 0.208825i, c5 = 0.175313 — 0.163549i, c6 = 0.527922 — 0.364841i. The polyhedral homotopy induced by w,a,C is Ha(y,t) = (hf(y,t),h2°(y,t)) = 0, where What) = clyi + 629% +C3t5°'63523, H(y,t) = C4yl’yg + 65311 + c6y2t2. There are ten solution curves of Ha(y,t) = o emanating from ten solutions of Ha(y, 0) = 0. At t = 0.65, five of those ten curves have phase space tangent vectors (iv; a; dt ’ dt standard prediction-correction method, starting at these points, the prediction step ) all roughly pointing to y = (0,0) at the points on the curves. For the with step size 0.025 will give the predicted points close to (y, t) = (0,0, 0.675) for all those five curves. Since t50'63523 is about 10‘9 for t = 0.675, the function values of H (y, t) in a very small neighborhood of (0,0,0.675) (the “valley”) are almost zero. Starting from these predicted points at t = 0.675, Newton iterations for the correction step will converge to the “valley” rather than the points on the curves at t = 0.675. But there are no solution curves of H “(y, t) = 0 passing through the “valley”. [I 18 CHAPTER 2 Balancing the Powers by the Sandwich Model Given the mixed cell configuration Mu, induced by a generic lifting w = (wl, - - - ,wn), assume C = (C1, - - - ,Cn) E Mw. We shall use the short hand notations: 6 == (9. Lia-((1)), q E A.- for a lifted point, A,- := {ii I q E A,} for a lifted support, C, := {Ein E C,-}, and C := (C1, - - -,C,,) a lifted cell. For a vector 8 := (a, 1) E Rn“, we say “6 supports C”, “0: supports C”, or a is the inner normal of C when the hyperplane with inner normal 3 supports conv(A1), - - - ,conv(A,,) at C1, - - - , C“, respectively. 2.1 A Fundamental Observation When constructing the polyhedral homotopy for cell C with inner normal 0, we actually execute the following transformations: 19 (here vectors are regarded as in columns) exponents of (x, t) in f,- (y,t) in h,“ (y,t) in h: A A U A A S,‘ A A q 6 «41- i——> (9, (01.9)) +—-+ (<1. (cm) - mi). (2-1) ( see (1.5) (1.8) (1.9) ) where 1 0 0 U := . . , S,- : shift of the last coordinate of elements 0 1 0 in UA, by m,- := minqu,(c’i,q). al . . . an 1 1 . - 0 o 0 Clearly, detU = 1, U-1 = ' ' , and u-Ta = 0 1 0 0 1 _al . . . _an 1 ‘ " I. .- When a vector 3 := (8,1) E IR"+1 supports another cell C’, then I 51 - 01 . U-TB‘ = .87: — an with the last coordinate > 0. For Si 2: we have U'ls, = 3,. Now, for any 37, ii, we have (’7‘, (’i) = (U'TA, U’ci). It follows that (U'T’i, SeUfi) = (U'T’U Uii - Si) = (U’T’IUii) - (U'Ti Si) = (3,3) - (EU‘lsi) = (330) - (3,5,), 20 So, ' UJA SiUA = ' AtA — A, i- gfl 7, q) $136 (1) (7 8) Therefore, U'TEE supports UC (thus, (SIUC1,...,S,,UC,,)), and at the same time, U'TB also supports UC’ (thus, (SlUCi, . . . , SnUC;)). El It is not clear how powers of t will be distributed in the homotopy Ha until S,-U transformations applied. The consequence of applying U is to “turn cell C horizontal” without changing existing mixed cells. When the powers of t in homotopy Ha are considered as another sets of liftings, obviously it gives the same mixed cells. On the other hand, if we slightly alter lifting values, mixed cell configuration can still be the same but powers of t may become more desirable. Accordingly, there may exist better liftings that preserves the mixed cell configuration previously found but induces polyhedral homotopies with more balanced powers of t. Example 2 Given a polynomial system P = (p1, p2) with spt(p1)= A1 = {a,b,c}, d a = (0,1), b = (0,0), c = (1,0), an spt(p2) = A2 = {d, e, f}, d = (0,1), e = (1,0), f = (1,1). A lifting w =(w1,w2),w1:A1——>IR, (.122 :A2—>IR, 011(3): 1.1, 01(5) = 1, 01(6) = 11, w2(d) = 12) (02(8) : 21: w2(f) = 2a will result in two mixed cells: C = ({a,b}, {d,f}) with inner normal a = (10, ~01), C' = ({b,c}, {e,f}) with inner normal 3 = (—10,0.1). Since 8 = (10, —0.1,1) supports C, in the homotopy H“ = (h‘l’,h‘2’) induced by a, 21 the distribution of powers of t are as follows: a: ((10, —0.1, 1), (0,1,1.1)) = 1 0 b : ((10,—0.1,1), (0, 0,1)) = 1 in hi". 0 in E" c: ((10,—0.1,1), (1,0,11)) = 21 20 d: ((10,-01,1), (0,1,12)) = 11.9 0 e: ((10,—01,1), (1,0,2.1)) = 12.1 in ht. 0.2 in R? r: ((10,—01,1), (1,1,2)) = 11.9 0 Namely, we have RICKY: t) = Cay. + beb + ccyct20’ H2O(y,t) = cdyd + c.y°t°'2 + cfyf. Since 3 = (—10, 0.1, 1) supports C’, in the homotopy H” = (hf, hg) induced by 5, the distribution of powers of t are a: ((—10,0.1,1), (0,1,1.1)) = 1.2 0.2 b : ((—10,0.1,1), (0, 0, 1)) = 1 in hi, 0 in EB c: ((—10,0.1,1), (1,0,11)) = 1 0 d: ((—10,0.1,1), (0,1,12)) = 12.1 20 . . —fi e: ((—10,0.1,1), (1,0, 2.1)) = -—7.9 m hf, 0 m h2 = < f (—10,0.1,1),(1,1,2))= —7.9 0 That is, H50. t) = c.)"t°'2 + beb + ccy", hf (y, t) = cdy‘lt20 + cey" + nyf. We wish to have certain lifting w, : A,- ——) IR that induces polyhe- q H wi(¢l) = wq dral homotopies in which every power of t lies between 1 and some ,1 : 1 S ((0: 1), (01%)) — ((0:1): (81%)) S It, 1 S ((a,1),(e,we)) _ ((011)1(d1wd)> S p) 22 where a is the solution to «a: 1)! (a, ‘08)) : ((011)1(131 wt)»: (2.2) ((0, 1), ((1,916)) = ((05 1), (13%)), i.e. 0: supports cell C = {{a,b}, {d,f}}, and 1 _<- «,5, l),(a,w.)) — ((311)1(bawb)> S ”1 1 S ((H, 1), ((1,924)) - ((fi, 1), (6,925)) S u, where B is the solution to ((fl,1),(b,wb)> = ((fi,1),(c,wc)>, (2.3) ((fl, 1), (61%)) = ((6,1),(f,wr)>. that is, 6 supports 0’ = {{b,c}, {e,f}}. Hence, C and C’ remain mixed cells. Consider a linear programming problem with the variables y and wq’s: LPO : min 12 (exponents of t) st. 1 _<_ ((a, 1), (c, we» — ((a,1),(a,w.)) g u, 1 S ((0 1) (6 we)>- ((0,1),(d,wd)> S It, 1 S ((5,1) (8 W.» - ((5,1),(bwbl) S u, 1 S ((3,1),(d,wd)> - ((3,1) (e we» < u, where a is the solution of (ma— 1))) : :23; w. dby (2. 2), fl is the solution of (fie : c)) :w w: _ _S: by (2. 3), variables: p3w87%)wC)wdtwetwf° The powers of t in H“ can be regarded as another lifting which induces the same mixed cells C and C’ with C staying “on the ground”. By restricting 02., wb, wd, (10“ = 0, we have a = (0, 0)T in LPG and obtain a new linear programming model LPl: 23 LPl : min a (exponents of t) s.t. l g wc S u, 1 S we S ll. 1 S (5.8) - (Ab) S )1, 1 S (16. d) - ((6.1).(e.we)) S #1 we where 6 is the solution of { Eg:::;)> : _we by (2.3), variables: [1, we, 02.. LPl is of course preferable if its optimal solution p and corresponding exponents of t are better than the ones in LPO. I] 2.2 Setup of The Sandwich Model As indicated in the last section, generic random liftings can induce highly nonlinear polyhedral homotopies which may produce numerical instabilities. To overcome this problem, our strategy is to find a new lifting function V = (V1, . . . , 11,.) where V,- : A,- —+ IR for i = 1,. . . ,n, based on the already computed mixed-cell configuration M2,. The mixed-cell configuration My induced by the new lifting u will be the same as Mw, but the highest power of the continuation parameter t in the polyhedral homotopies induced by u is the smallest among all those polyhedral homotopies induced by liftings which keep the mixed-cell configuration M“, invariant. In this way, reidentifying the mixed-cell configuration M”, which is very time consuming, becomes unnecessary. Let C = (C1,...,C,,) E M“, where C,- = {a,,b,-} C A,-, i = 1,...,n. To keep Mu, invariant, we impose on any new lifting function V = (V1, . . . , 11,.) the conditions: <0.1).>> = <0.1>.>. i: 1 n <0.1>.> < <0.1).>. v q e A.\{a.-,b.}, 24 or, (84.7) + Vi(ai) = (bi17l + with). (2-4) (3137) + 14(84) < (Q17) + Vi(q)i V q E A1\{au bi}, (25) for i = 1,... ,n, where ('7, 1) is the inner normal of C in My. From (2.4), we have (a,- — b,-,'y) = 11,-(bi) — V,(a,-) for i = 1,...,n. Since C = (C1, . . . ,0") is a mixed cell in the fine mixed subdivision Sm the edges spanned by {a,, b,}, i = 1, . . . ,n, determine a full-dimensional parallelepiped in IR“. Equivalently, the matrix 1- - 81 —b1 b an — bn - is nonsingular, and so, 7 can be expressed uniquely as a linear combination of the lifting values 11,-(m) and u,(b,-), i = 1,. . . ,n. Namely, 1- III )- u ’71 V1(b1) — 1’1 (81) 7T 2 = A—1 ° (26) I. 7n J L Vn(bn) _ Vn(a-n) A As in (1.9), the polyhedral homotopy induced by lifting u = (V1, . . . , V") and mixed cell C = ({a1,b1}, . . . , {a,,,b,,}) with inner normal (7, l) is 3.70.0 = Quay." + any“ + Z c..qy"t‘i. 2‘: 1.... ,n. where eg, the powers of t, are given by e; := (q, '7) — (any) + Vi(Q) — Vi(ai)! V q E A,\{a.-,b.-}, and they are always positive according to (2.5). By (2.6), 7 may be removed from 25 the symbol e21. We denote the resulting expressions by eq. More explicitly, P V1031) — V1(a1) W eq 1: (q — adA-l 5 + V101) — Vi(a«')- (2-7) _ Vn(bn) — Vn(an) To avoid the powers e,l being too large or too small, it is natural to consider the following minimization problem LPO: LPO: min ,u s.t. 1 Seq 3p VqE A,\{a,-,b,-}, i: 1,...,n, V C = ({a1,b1},. . . , {an,b,,}) E M... with 6,, defined in (2.7). (2.8) Apparently, the lifting function V = (111,” . , V,,) with values obtained by the so- lution of this minimization problem satisfies (2.4) and (2.5) with '7 defined in (2.6). Therefore, the mixed-cell configuration My induced by V coincides with M”. More- over, the powers of the continuation parameter t in the polyhedral homotopies induced by V will be much better balanced. 2.3 Reducing the Size of the Sandwich Model LPO has 1+Zr=1 #A, unknowns, namely, a as well as V,-(q) for q E A,-, i = 1, . . . ,n, and 2(#Mw)2?=1(#l41' — 2) inequalities. For practical considerations, we wish to reduce both the number of unknowns and the number of inequalities in LPO. In the following, we will show that for a fixed mixed cell C = ({51,bl},.. . ,{an,B,,}), where {55.3.} C A,-, i = 1,... ,n, in the mixed-cell configuration M... with inner normal ((3,1), we may set V,—(§.-) and V,-(b,-) to be zero for i = 1,...,n in LPO, so the number of unknowns is reduced by 2n. But the solution of the new minimization problem defines a lifting function V’ = (V{,. . . , V,’,) which induces the same mixed-cell configuration as M“. 26 For the fixed mixed cell C = ({51,b1},...,{§,,,b,,}) E M“, with inner normal (5, 1), we define a lifting function 02’ = (02], . . . ,wg), where w,’ : A,- —+ IR, i = 1,. . . ,n, asfollows: fori= 1,...,nanquA,, wr’I‘l) i: mic!) — @154) + wr(Q) — wi(5i)' (2-9) Then to: vanishes at both 5,- and E, i = 1, . . . ,n. Let M”: be the mixed-cell configu- ration in the subdivision 5“,: of A = (A1, . . . , A”) induced by w’. Lemma 2 M“): = Mm. More precisely, C = (01,. . . ,0") E M... with inner normal (0, 1) with respect to to if and only if C = (C1, . . . ,Cn) E M“): with inner normal (01 — ,6, 1) with respect to w’. PROOF: Let C,- = {ahbi} C A,- for i = 1,. . . ,n. Then, C E M“, with inner normal (01,1) 4:) ((a, 1)1(aivwi(ai))) = ((a,1),(b,,w,(b,~))), ((0: 1)1(aiiwi(ai))) < ((0.1).(q.w.(q))>. V q E Ai\{aiibi}1 z 1’ ’n 01'. (0.81 - b,-) = Mlbi) — “Mail: 2 = 1’ ,n (a, cl — at) > wi(ai) — WM): V q E Ar\{aerbi}, On the other hand, 0 e M”. with inner normal (01 — s, 1) <=> ((0 — 16:1):(aiawl(ai))> = ((0 — fl11)1(biiwi(bi)))i i: 1, . . . ,n. ((0 — 3.1)r(airwl(31))> < ((01 - :61 1), (q, WWI)», V q E Ai\{aii bi}. Or, by (2.9), (a — 5131' - b.) = wai) — wi(a1') = (firth) — (3.54) + («(131) — “1454) -(<fl.ar> - (flit) + wr-(ar) - cur-(54)) = f—flrar' — b,) + w,(b,-) — 0148;), 27 i.e., (aia-i _bi> :wi(bi) _wi(ai)i 2: 1,...,n and) for q E A1\{aiibi}a (0 — H. q — a.) > «II-(8r) - 91201) = (Brat) - (5,54) +w,(a,~) — w,(a,-) -(<fl.q} - 0.5.) +e.- — w.wr(ae) -w.-(<1). 2': 1..-..-n So, the proof of the assertion is achieved. El Most importantly, a straightforward calculation shows that the polyhedral homo- topy, as in (1.9), induced by the cell C = (Cl, . . . ,C,,) in M“, with inner normal (01, 1) is exactly the same as the one induced by cell C = (C1, . . . ,0") in M”: with inner normal (0: —- fl, 1). So, we may solve P(x) = 0 by using the polyhedral homotopies produced by mixed cells in M”: together with corresponding inner normals. Now, with the lifting 02’, we consider the minimization problem LPl : LPl : min a s.t. 1 S (7.9 - a.) + 14(9) - 14(31) S A V q E As\{an be}, V C = ({alibl}i ° ° ' i {anibn}) 6 MW” 14(55): 115(35) = 0, 2: 1,. . . ,n. (2.10) Here, '7 can be expressed, as in (2.6), as a linear combination of the values of 11,-’82 r' H P -—1- q ’71 a1 — b1 V1(b1) - V1(al) 771 an _ bn Vn(bn) — Vn(an) b d I - b u 28 This problem has 2n fewer unknowns than LPO, and its solution yields a lifting function V’ = (V1,. . . ,Vl). As before, the mixed-cell configuration My: induced by the lifting V’ is the same as M21. The following proposition shows the feasibility of this problem. Proposition 3 LP1 has an optimal solution. PROOF: Apparently, the values of the lifting function 02’ = (02], . . . ,wg) satisfy 0 < (a,q—a,) +wi(q) —wi(ai)i 7': 11'°'1n1 (211) for all C = ({a1,b1},...,{a,,,b,,}) E M“): with inner normal (0:, 1) and q E At\{aiabi}i Where u—lp 1 (11 I 81 — b1 01,1(b1) — w((a1) a tnl It follows that the function values of V“) := [02’ for Z > 0 also satisfy (2.11). There _ an — bu . _ w1.(bn) - wj,(a,,) ] exists to > 0 such that _ , (lo) (‘0) - _ for all C = ({81,b1},...,{&n,bn}) E Mo)’ and q E A1\{a.',bi}. Let #0 be the maximum of the right-hand side of (2.12). Then (VUO), no) is a feasible solution of LP1. So LP1 has an optimal solution with the value of )2 between 1 and #0. Cl Remark 2 The pair (V(‘°), ,uo) constructed in the proof can serve as a starting point of standard simplex algorithms for solving LP1. The number of variables in each double inequality of LP1 is no greater than 2n+ 2 which is usually much smaller than the number of variables in LP1. This sparsity of the linear programming problem LP1 is exploited in our algorithm and results 29 in a remarkable speed-up. Some of the inequalities in the constraints of LP1 are exactly the same, and they can easily be detected by comparisons and deleted when the constraints are being generated. In the rest of this section, we will show that the constraints in LP1 can also be derived from circuits [GKZ, MiVe] of the support A = (A1, . . . ,A). For a mixed cell C = ({a1,b1}, . . . , {an,b,,}) E M“, with inner normal (a, 1) and q E A,-\{aj,bj}, we have (a: 31') + wj(aj) < (a: Q) + WM), or, (a, q — a,) + wJ-(q) — wJ-(aj) > 0. (2.13) We will call this inequality the normal inequality with respect to C and q. This inequality serves as the building block in our sandwich model LP1 in (2.10). Note that (a, 1) is also the normal of the n-dimensional subspace H of IR"+1 spanned by the vectors (h1 — a1,w1(b1) — w1(a1)),---,(b,, — a..,e.,(h,,) — e,(a,,)). Let (q - a,-, s) be the projection of the vector (q — aj, wj(q) — wJ-(aj)) on the subspace H along the direction of its last coordinate. Then ((a, 1), (q — a,-, s)) = 0, or, (a,q-—aj) +3: 0 and (2.13) becomes “60!) - “0(a) — 3 > 0. So, the left-hand side of (2.13) measures the distance between the points (q — aj,w,-(q) — wj(aj)) and (q - a,-, s) as shown in Figure 2.1. On the other hand, the Cayley embedding of A,- into IR2"“1 is X.- = {(a,e,-_1)|a e 21,-}, 2': 1,...,n, 30 (a, 1) /7 H Figure 2.1: An illustration of normal inequality (2.13) here co = 0 E IR"‘1 and e,- = (0,...,1,0,...,0) is the ith unit vector in IRn‘l, i=1,...,n—1.LetA=UA,.DefineLTJ : A—HRby i=1 $(a,e,-_.1) == (1),-(a), V a E A,-, i = 1, . . . ,n. Then the lifting £72 induces a regular subdivision of A, denoted by S5. Proposition 4 (The Cayley 'D'ick [GKZ, St94, VGC]) S“, is a fine mixed sub- division of A = (A1, . . ., A") if and only if S”; is a triangulation of conv(A). Fur- thermore, C = (C1, . . .,C,,) E S“, if and only ifUC, E S5. i=1 By the Cayley embedding, a1,b1,...,a,,,b,, and q are embedded in IR“-1 as follows: (31,80); (blieO)i "'1 (anten—l)i (haven-1): (qiej—l) Since these points are afinely dependent (not necessarily a circuit), there exist A1,/\’1,...,A,,,/\;,E IR such that n 20.- +;\£) = 1. i=1 ,, (2.14) (qiej—l) = Z (Ai(aiiei—l) + A2(br.e.-_1))- 31 From (2.14), as in Theorem 4.1 of [MiVe], we have A,- + A; = 1, (2.15) /\.-+)1£=0 foriyéj. It follows that (qiej—l) = Z (Ai(aiiei—l) + A2(br.er—1)) i=1 : 2(Ai(aitei—1)+ A:(aty ei—l) + A:(bi, ei_1) '_ A:(a“ ei—l)) i=1 = (31»ej—1)+ 2 A20).- - a.» 0) i=1 and so, = ZAflb, —n,-). (2.16) i=1 Now, U C,- E S; implies i=1 a(qrej—l) > Z (Aia(airei-l) + A£a(brrer-1))- (2-17) i=1 By (2.15) and the definition of £5, (2.17) can be written as “11(9) — wJ-(aj) > Z A;(w,-(b,-) — £0430): i=1 or, 0,.(q) — e,(a,-) —Z x.( (w,(b —w,-( (a,)) > o. (2.18) i=1 We will call this inequality the circuit inequality with respect to C and q. Since (q -- aj, s) is in the subspace H and thus can be written as a unique linear combination of (b,- — a,,w,~(b,-) — w,(a,-)), i = 1,. . . ,n, (2.16) leads to s = 280.0.) — w.). i=1 So, the left-hand side of (2.18) also represents the distance between the point (q — aj,w,-(q) — wJ-(aj)) and (q — a,-,s). Therefore, the normal inequality (2.13) is the same as the circuit inequality (2.18). 32 + A b c e b+e c+e c+f d f fll 22 £1 + ‘22 {a,b}+{d,e} {a,b}+{d.e} {arc}+{d,f} {arc}+{d.f} uuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuu {b.c}++w2(d) = (flag) +w2(e)' 34 Hence, as) > <0.?» — 03.?) + e10) = <26) — <25) — Xmas — 13> — A5056 — 5) + wr) + A3020) - 52(3)) + wr /\’1(w1(c) — w1(b)) + A’2(w2(e) — w2(d)). (2.20) Equation (2.19) along with (2.20) implies that (f -— d, w2(f) — w2(d)) is “above” the subspace H spanned by (c -— b, w1(c) — w1(b)) and (e — d, w2(e) — w2(d)). Obviously, the right-hand side of (2.20) is the projection of (f — d, w2(f) — w2(d)) onto H, which equals 3 in (2.13). Ultimately, the circuit inequality is equivalent to the normal inequality. El Example 4 In the previous example, we have two mixed cells with mixed volume 2. As depicted in Figure 2.2, there is a mixed cell whose volume equals the mixed volume. Let 7r : A—-> {A1,A2} be the projection onto original supports. Based on a mixed cell C = ({b,c}, {d,e}) previously found and by Cayley embedding, there exists a circuit Z := C U {a} = {5,15,53,63 (see Figure 2.4) with two associated triangulations T+ == {Z\{5}. Z\{'E}. 2061}. T- == {Z\{i3}. Z\{'&}} in R3 such that «: Table 3.1: Sizes of the Linear Programming problems. Here, n is the number of variables of the polynomial system and #Mw is the number of mixed cells in the mixed-cell configuration M”. The data in Table 3.1 are generated by the program with one random lifting function to for each polynomial system. The fourth and fifth columns give the size of the linear programming problem in (2.8). The last two columns are the size of the linear programming problem in (2.10) after all repeated constraints are deleted. For cyclic-n polynomial systems, about 1/3 of the constraints are deleted, which results in a considerable speed-up. 39 Avg highest power of t Avg CPU time Polynomial System Before After Finding Balancing balancing balancing mixed cells method Cohn—2 [PoSSo] 1391 85 0.21 0.19 Cassou—Nogués [Li97: 251 11 0.05 0.03 Planar 4-bar [MoWa] 429 8 0.17 0.08 Cyclic-6 :EmCa: 425 31 0.46 0.17 Cyclic-7 :EmCa: 3152 139 7.1 1.9 Cyclic-8 :EmCa: 10281 398 81 16.6 Table 3.2: Height of Powers and CPU Time in Seconds. The averages are obtained from ten different random liftings. For the data in Table 3.2, we run the algorithm with ten different real random liftings for each polynomial system. We first scale the powers of t in the polyhedral homotopies before balancing such that the lowest power of t in the homotopies is one, and the average of the highest powers of t in the polyhedral homotopies for the ten random liftings are listed in the second column. The third column lists the average of the highest powers of t in the polyhedral homotopies for the ten liftings obtained from the optimal solutions of the corresponding linear programming problems (2.10). The fourth column gives the average time elapsed for finding all mixed cells. The last column is the average time elapsed for finding the optimal lifting functions V’, including the constructing and solving of the linear programming problems (2.10). Rom these results, we see that the highest powers of t in the polyhedral homotopies are considerablly reduced. The overall reduced powers of t in the polyhedral homo- topies greatly limit the chance of running into a “valley” which may cause the failure of curve-tracing. 40 BIBLIOGRAPHY 41 BIBLIOGRAPHY [AlGe93] E.L. Allgower and K. Georg, Continuation and path following, Acta Nu- merica, 1993, 1-64. [Bern] D.N. Bernshtein, The number of roots of a system of equations, Functional Analysis and Appl. 9(1975), 183-185. [CaRo] J. Canny and J. M. Rojas (1991), “An optimal condition for determining the exact number of roots of a polynomial system”, In Proceedings of the 1991 International Symposium on Symbolic and Algebraic Computation, ACM, 96-101. [ChMPYo] S. N. Chow, J. Mallet-Paret, and J. A. Yorke (1978), “Finding zeros of maps: homotopy methods that are constructive with probability one”, Math. Comput, 32, 887-899. [EmCa] I.Z. Emiris and J .F. Canny, Efi‘icient incremental algorithms for the sparse resultant and the mixed volume, J. Symbolic Computation 20(1995), 117-149. [GKZ] I.M. Gel’fand, M.M. Kapranov, and A.V. Zelevinsky, Discriminants, Resul- tants and Multidimensional Determinants, Birkhéuser, Boston, 1994. [Hu96] B. Huber (1996), Solving sparse polynomial systems, Ph.D. dissertation, Cor- nell University. [HuSt95] B. Huber and B. Sturmfels, A polyhedral method for solving sparse polyno- mial systems, Math. Comp. 64(1995), 1541-1555. [Kh78] A. G. Khovanskii ( 1978), “Newton polyhedra and the genus of complete in- tersections”, Functional Anal. Appl., 12(1), 38-46. Translated from Funktsional. Anal. i Prilozhen., 12(1), 51—61. [Ku76] A. G. Kushnirenko (1976), “Newton Polytopes and the Bézout Theorem”, Functional Anal. Appl., 10(3), 233-235. Translated from Funktsional. Anal. i Prilozhen., 10(3), 82-83. 42 [LiWa96] T. Y. Li and X. Wang (1996), “The BKK root count in 43"”, Math. Camp, 65, no. 216, 1477-1484. [Li97] T.Y. Li, Numerical salutions of multivariate polynomial systems by homotopy continuation methods, Acta Numerica 6(1997), 399-436. [MiVe] T. Michiels and J. Verschelde, Enumerating regular mixed-cell configurations, to appear in Discrete Comput. Geom. [MoSo] A. P. Morgan and A. J. Sommese (1987), “A homotopy for solving general polynomial systems that respect m-homogeneous structures”, Appl. Math. Com- put., 24, 101-113. [MoWa] A.P. Morgan and CW. Wampler, Solving a planar four-bar design problem using continuation, ASME J. of Mechanical Design 112(1990), 544-550. [PoSSo] B. Mourrain, The handbook of polynomial systems, available at http: Hm . inria . fr/saf ir/POL/ index . html. [R094] J. M. Rojas (1994), “A convex geometric approach to counting the roots of a polynomial system”, Theoret. Comput. Sci, 133, 105-140. [RoWa] J. M. Rojas and X. Wang (1996), “Counting affine roots of polynomial sys- tems via pointed Newton polytopes”, J. of Complexity, 12, no. 2, 116-133. [Shaf] I. R. Shafarevich (1977), Basic Algebraic Geometry, Springer-Verlag (New York). [St94] B. Sturmfels, 0n the Newton polytope of the resultant. J. of Algebraic Combi- natorics, 3(1994), 207-236. [St96] B. Sturmfels, Gro'bner Bases and Convex Polytopes, volume 8 of University Lecture Series, AMS, Providence, R.I., 1996. [VGC] J. Verschelde, K. Gatermann, and R. Cools, Mixed-volume computation by dynamic lifting applied to polynomial system solving, Discrete Comput. Geom. 16(1996), 69-112. [VVC] J. Verschelde, P. Verlinden, and R. Cools, Homotopies exploiting Newton poly- topes for solving sparse polynomial systems, SIAM J. Numer. Anal. 31(1994), 915-930. 43 IIIIIIIIIIIIIIIIIIIII III[[II]l|][[]]][I]|]1][Il]][[II