0‘10. .91 uh. . 3:51.. . 4‘Hx.v a: . . 2 . v93. Lul LOI. .0!- . . .. Hutt- o| . .1 o) 4 u.) Incl .1. .. huh... (rtvvtu. 1l|”-|.||c ill}. a aw. “.5 y r .Vnkh t a I. Inuyllt... Hus. 3109.13. ”art... .I A . V! a . V: ‘Jlufi‘ t bi ‘ . l 39 f? ”1 A: ‘«‘ ,3 . 11' Nate. . ..I- f. t.. b ': ’1. THEme Ilii'lliliiiiiiii]IIiNTT'i'lliiiilffliil 3 1293 01682 63 This is to certify that the dissertation entitled Polyhedrai Homotopy and Its Applications to Poiynomiai System Solving presented by Hwee Hoon Chung has been accepted towards fulfillment of the requirements for Ph.D . degree in ApijeLMthemati CS fi/fib Lg D Major professor Date Juiy 1, 1998 MSU is an Affirmative Action/Equal Opportunity Institution 042771 LIBRARY MICMQan State Universlty ‘ PLACE IN RETURN BOX to remove this checkout from your record. TO AVOID FINES return on or before date due. r MTE DUE DATE DUE DATE DUE 1198 MM“ POLYHEDRAL HOMOTOPY AND ITS APPLICATIONS TO POLYNOMIAL SYSTEM SOLVING By Hwee Hoon Chung A DISSERTATION Submitted to Michigan State University in partial fulfillment of the requirements for the degree of DOCTOR OF PHILOSOPHY Department of Mathematics 1998 ABSTRACT POLYHEDRAL HOMOTOPY AND ITS APPLICATIONS TO POLYNOMIAL SYSTEM SOLVING By Hwee Hoon Chung In this dissertation, we use the polyhedral homotopy to solve polynomial systems. Polyhedral homotopy is based on Bernshtein’s Theory, which states that for a poly- nomial system with generic coefficients, the number of isolated zeros in the algebraic torus (0‘)", counting multiplicities, is equal to the mixed volume of its supports. In the past, the construction of the start system of the homotopy continuation method is always based on the total degree of the original system. For polyhedral homotopy, cells of the right type provide a binomial start system which can be used to solve a polynomial system with the same monomials as the given polynomial system but with randomly chosen coefficients. This system is then used as the start system to solve the original polynomial system. This homotopy is particularly efficient for solving systems with no special structure. An important merit of this work is its practical application in solving algebraic systems in robot kinematics, chemical reactions, engineering, economic modelling, neural network, computer vision and many others. Our solver finds all isolated solutions to satisfactory accuracy and speed; further- more, its generality should establish itself as the method of choice for systems of moderate size. To my family iv ACKNOWLEDGMENTS I am most indebted to my thesis advisor, Professor Tien Yien Li, for his constant encouragement and support during my graduate school years. I would also like to thank him for his introduction to the Polyhedral Homotopy, the essentials of com- binatorial convexity and geometry through his excellent graduate level courses and special topic courses. His knowledge of these subjects and insightful ideas greatly contributed and motivated this work. Last, but not least, I wish to express my gratitude to Professor Michael Frazier, Professor Jay Kurtz, Professor William Sledd and Professor Zhengfang Zhou, for serving on my thesis committee. TABLE OF CONTENTS LIST OF TABLES LIST OF FIGURES 1 Introduction 2 Polyhedral Homotopy 2.1 Notations ................................. 2.2 Algebraic deformations .......................... 2.2.1 The nonlinear homotopy ..................... 2.2.2 The linear homotopy ....................... 3 Algorithms 3.1 Vertex-set algorithm ........................... 3.2 Edge-set algorithm ............................ 3.3 Algorithm for finding cells of type (1, . . . , 1) . ............. 3.4 Finding zeros of R(y, 0) .......................... 3.5 Numerical curve tracing ......................... 4 Minimal Bézout number 4.1 Notations and definitions ......................... 4.2 Bézout number calculations ....................... 4.2.1 Row expansion algorithm ..................... 4.3 Multi-homogenizations .......................... 4.4 Efficiency measures ............................ 5 Numerical experiments 5.1 Problem statements ............................ vi 6 6 10 11 16 19 20 21 23 24 28 31 32 33 34 34 36 38 39 5.1.1 5.1.2 5.1.3 5.1.4 5.1.5 5.1.6 5.1.7 5.1.8 5.1.9 5.1.10 5.1.11 5.1.12 5.1.13 5.1.14 5.1.15 5.1.16 5.1.17 5.1.18 5.1.19 5.1.20 5.1.21 5.1.22 5.1.23 5.1.24 5.1.25 5.1.26 5.1.27 5.1.28 5.1.29 5.1.30 5.1.31 5.1.32 5.1.33 5.1.34 Robot manipulator PUMA .................... Robot manipulator ROMIN ................... Neural network — adaptive Lotka-Volterra System ....... Symmetrized four-bar mechanism ................ The nine-point problem ..................... Chemical equilibrium ....................... Lumped-parameter chemically reacting system ......... Heart-dipole ............................ Conformal analysis of cyclic molecules ............. Camera motion from point matches ............... Electrical network ......................... Vibrating systems ......................... 6R inverse position problem ................... 6R2 inverse position problem .................. An interpolating quadrature formula over a grid ........ Optimizing the Wood function .................. An application in electrochemistry ............... Benchmark i1 from the interval arithmetics benchmarks . . . . Optimal multi-dimensional integration formula ......... The system of A. H. Wright ................... The Reimer5 System ....................... Butcher’s problem ........................ Construction of Virasoro algebras ................ The cyclic n-roots problem .................... Combustion chemistry ...................... Economic modelling ....................... An application from neurophysiology .............. The system of E. R. Speer .................... Solotarev system .............. . ........... Trinks system ........................... A small system from constructive Galois theory: 591 ..... n-dimensional reaction-diffusion problem ............ 4-dimensional Lorentz attractor ................. A bifurcation problem ...................... vii 39 4o 41 43 44 45 47 47 48 5o 51 52 53 54 55 56 57 58 59 59 60 61 61 62 64 65 66 67 68 68 69 69 70 71 5.1.35 Benchmark D1 from the interval arithmetics benchmarks . . . 5.1.36 Caprasse’s system ......................... 5.1.37 Arnborg? system ......................... 5.1.38 Rose system ............................ 5.1.39 Moeller4 System ......................... 5.1.40 KatsuraN System ......................... 5.1.41 Cohn—2 system .......................... 5.1.42 Cassou-Nogues .......................... 5.1.43 A “dessin d’enfant” Isystem ................... 5.1.44 A “dessin d’enfant” II system .................. 5.1.45 Sendra system .......................... 5.1.46 Parallel robot (left-arm robot) .................. 5.1.47 Parallel robot with 24 real roots ................ 5.1.48 3 Torus system .......................... 5.1.49 Emulsion chemistry ........................ 5.1.50 Commodities market ....................... 5.1.51 Raksanyi system ......................... 5.1.52 Runge-Kunga ........................... 5.1.53 Solubility of silver chloride in water ............... 5.1.54 Enumerative geometry(Hypersurface schubert conditions) . . . 5.2 Summary ................................. 5.3 Conclusions ................................ BIBLIOGRAPHY Bibliography viii 71 72 73 73 74 74 75 76 76 77 78 79 80 82 82 83 84 84 85 86 88 88 91 91 LIST OF TABLES 5.1 Products of Propane Combustion .................... 46 5.2 Definitons of constants .......................... 46 5.3 Equilibrium Constants .......................... 46 5.4 Coordinates of the two frames ...................... 51 5.5 Results for the cyclic n-roots problem .................. 63 5.6 Results for the Economic modelling problem .............. 66 5.7 Coefficients for the butler’s problem ................... 86 5.8 Characteristics of systems that arise in the Schubert Calculus . . . . 87 5.9 Characteristics of the polynomial systems I ............... 89 5.10 Characteristics of the polynomial systems II .............. 90 ix 3.1 5.1 5.2 5.3 5.4 LIST OF FIGURES The prediction-correction process .................... 29 The basic notation ............................ 39 The ROMIN manipulator ........................ 41 Four—bar linkage at the jth position ................... 43 Four-bar ABCD with coupler triangle CPOD at the initial precision point P0 (left); Displacement of the four-bar to a new precision point P, (right) ................................. 44 The cyclic molecule ............................ 48 Single point seen by two camera positions ............... 50 CHAPTER 1 Introduction Let P(x) = (p1(a:), . . . ,pn(:1:)) = O with a: = (121, ...,a:,,) be a system of n polyno- mial equations in n unknowns. We want to find all isolated solutions of the system p1(x1,...,:r,,) = 0 pn(:z:1,...,a:,,) = 0. In order to approximate all isolated solutions of P(:z:) = 0, we look for a homotopy H : C" x [0,1] —> C" that starts with a trivial (i.e., easily solved) set of polynomial equations q1(x1,--.,xn) = 0 qn(:c1,...,a:n) = 0. Let Q(a:) denote (q1(:1:), . . . ,q,,(:z:)). We then follow the curves in the real variable t which make up the solution set of (1.1) H(:r:,t) = (1 — t)Q(:1:) + tP(:1:) = 0. Note that H(.’L‘,0) = Q(:z:) and H(:1:, 1) = P(a:). If Q(:I:) = 0 is chosen appropriately, then the following three pr0perties should hold: (1) Triviality: The solutions of Q(r) = O are known. (2) Smoothness: The solution set of H(1:,t) : 0 for 0 S t < 1 consists of a finite number of smooth paths, each parameterized by t in [0,1). (3) Accessibility: Every isolated solution of H(a:, 1) = P(:1:) = 0 can be reached by some path originating from t = 0. It follows that this path starts at a solution of H(:z:, 0) = 62(5) = 0. If the three properties hold, the solution paths can be followed from the initial points at t = 0 to all solutions of the original problem P(m) = 0 at t = 1 using standard numerical techniques [1, 2]. Drexler [9], Garcia and Zangwill [15] independently and almost simultaneously started to solve polynomial systems by the Homotopy Continuation Method. A few years later, their homotopies were superseded by that constructed by T. Y. Li [25]. It was shown (via the use of generalized Sard’s Theorem and implicit function theorem) that with the following choice of 62(23): (11(33) 2 anvil—bi (1.2) where d1, ...,d,, are the degrees of p1(x), ...,pn(:r) respectively and a,, b,- are random complex numbers, that the three properties hold. Rewrite the homotopy (1.1) as (1.3) H(:r(t),t) : 0. Differentiating (1.3) with respect to t, we have do: Hx— H = 0 dt+ ‘ and da: 1.4 —— = —H‘1H where Hz, Ht are partial derivatives of H with respect to :1: and t respectively. The curves 32(t) are the integral solutions of the initial value problems of the ordinary differential equation (1.4) with (6(0) 2 11:0. The total number of curves of H’1(O) produced by the choice of Q(:c) in (1.2) is equal to d = all - - -d,,, the total degree of the system P(a:). The curves emanating from t = 1 must merge with one of those that start from t = 0. Thus, by following all the curves of H “1(0), we obtain all the isolated zeros of P(:I:), the polynomial system that we want to solve. Polynomial systems arise in diverse areas such as robot kinematics, chemical re- actions, engineering, economic modelling, neural network, computer vision and many others. Very often, we encounter deficient polynomial systems with the actual root count being less than the total degree d 2 d1 « - -d,, of the system. In fact, a great majority of the systems in application have only a small fraction of the total degree number of solutions. The following examples illustrate the point. Example 1.0.1 Consider the generalized eigenvalue problem: Ax : Ax, where A 6 CM". We wish to compute the eigenvalues A and eigenvectors a: = (3:1, . . . ,xn). This reduces to solving a system of n + 1 equations in n + 1 variables (A, 11:1, . . . , :6"): EJ— aijacj — Ax,- = 0; Z,- x, = 1 for z' = 1, . . . , 11. There are at most n isolated solutions to this system, with total degree 2". Homotopy method, using Q(:1:) in (1.2) as the start system, requires the tracing of 2" curves but at most n of them will converge to the target solutions when t —> 1. Example 1.0.2 The Cassou-Nogues System 15b4col2 + 611403 + 21b4c2d — 144b2c — 802628 — 2852cde - 648b2d + 3602(126 + 9b4d3 - 120 = 0 3054c3d — 32cde2 — 720112661 — 24b2c3e — 4326262 + 5766c — 576de + 1652cd2e + 16d262 + 160262 + 9546’ + 3964862 + 18b4cd3 - 432b2d2 + 24b2d3e — 16bzc2de — 240a + 5184 = 0 216526d — 162b2d2 -— 815%2 + 1008ce — 1008de + 15b262de — 15b263e — socale2 + 40d2e2 + 400282 + 5184 = 0 46% — 352d2 - 4b202 + 22ce — 22de + 261 = 0 The total degree of this system is 7 x 8 x 6 x 4 = 1344. This means that if we were to use the system Q(:1:) in (1.2) as the start system, we need to trace 1344 curves. However, this system only has 16 isolated solutions. Thus sending 1344 curves out in search for the 16 solutions represents wasted computations. The existence of extraneous paths, i.e., those paths that diverge to infinity as t —> 1, represents wasted computations and substantially limits the power of the method in most occasions. The choice of Q(:z:) in (1.2) to solve the system P($) = 0 requires an amount of computational effort proportional to d = all - - -d,, and roughly, proportional to the size of the system. We would like to derive methods for solving deficient systems for which the computational effort is instead proportional to the actual number of solutions. In this dissertation, we propose to use the polyhedral homotopy, where the choice of the start system Q(x) is based on the Bernshtein’s theory [3] and the number of homotopy curves that needed to be traced is greatly reduced in the case of deficient systems. This homotopy is particularly efficient for solving polynomial systems with no special structures. CHAPTER 2 Polyhedral Homotopy 2.1 Notations For a system of polynomials P(.’L‘) = (p1(:r),...,p,,(;r)) with x = (3:1,...,:z:,,), write p,(:r) = 2 6,3056“, t=1,...,n, 0644' where a = (a1,...,a,,) E Z", cm 6 C = C\{0} and at“ = :r‘1"---;rf,". Here A, a finite subset of Z", is called the support of p,(1:) and its convex hull, denoted by Q,- = conv(A), is called the Newton polytope of p,(a:). We call A = (A1, . . . , An) the support of P (at) The Minkowskz' sum of polytopes Q1, . . . , Q" is defined by Ql+'°'+Qn={al+"’+anlaleglaH-aanEQn}- The n-dimensional Euclidean volume of the polytope A1Q1 + - - - + An Q" with non- negative variables A1, . . . , An is a homogeneous polynomial in A1, . . . , A" of degree n [48]. The mixed volume of .A = (A1, . . . ,An), denoted by M(A1, . . . ,An), is defined to be the coefficient of A1 . - - An in this polynomial. Equivalently, using the principle of inclusion and exclusion, the mixed volume can be formulated as (2.1) J\/l(.»<11,.;€12,...,.Afl)=(—1)"“12vol(Q,-)+(—1)"‘2 Zvougi + QJ.) + . .. + vol(Q1+---+ Q"), The polyhedral homotOpy is based on the following theorem: Theorem 2.1.1 (Bernshtein) The number of isolated zeros in (0‘)", counting mul- tiplicities, of a polynomial system P(:1:) = (p1(a:), . ..,pn(a:)) is bounded above by the mixed volume M(A1, . . .,.An). For a generic choice of coefl‘icients, the system P(:r) = 0 has exactly M(A1, . . . ,An) isolated zeros in (0‘)". The root count in the above theorem was discovered by Bernshtein [3], Khovanskii [20] and Kushnirenko [21] and is sometimes referred to as the BKK bound. While this bound is, in general, significantly sharper than the variant Bézout numbers, its apparent limitation is that it only counts the zeros of P(a:) in the algebraic torus (0‘)". Root count in C" via mixed volumes was first attempted in [47] and an upper bound was derived by introducing the notion of a shadowed set. Later, a significantly much tighter bound was given in the following theorem: Theorem 2.1.2 [29] The number of isolated zeros in C", counting multiplicities, of a polynomial system P(:r) = (p1(:r), . . . ,pn(a:)) with supports A1, . . . ,An is bounded above by the mixed volume M(A1 U {0}, . . . ,An U {0}). Let A = (A1, . . . , A.) be a sequence of finite subsets of Z" whose union affinely spans R". By a cell of A we mean a tuple C = (Cm, . . . , C(")) of subsets C“) C A, for i = 1,. . .,n. For a cell C = (0(1),. . .,C(")), define t)’pe(C) : (dim(conv(C(1))), . . . , dim(conv(C(")))), COIMO) = conv(C“>) + . - . + conv(C(")), and vol(C) = vol(conv(C)). A face of C is a subcell F = (F‘1),...,F(")) of C where F“) C C“) and some linear functional (1 6 (R")" attains its minimum over C“) at F“), for 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(i)) for i = 1,. . . , n. Definition 2.1.3 A fine mixed subdivision ofA = (A1, . . . ,An) is a collection S = {C1, ..., Cm} of cells such that (a) dim(conv(C,-)) = n for all i = 1, . . . ,m, (b) conv(C,-) flconv(Cj) is a proper common face of both conv(C,-) and conv(Cj), whenever the intersection is nonempty for i 75 j, (c) U221 conv(C,-) = conv(.A). For i = 1,. ..,m, we write C,=(C,(1),...,C,-(")), and (d) dim(conv(C,-(1))) + - - - + dim(conv(C,-("))) = n, (e) (#(Cl‘l) — 1) + - - - + (#(c§'”) - 1) = n. A fine mixed subdivision of A = (A1, ..., An) can be found by the following process: Choose a real-valued function w,- : A,- —> R for each i = 1, . ..,n. We call the n—tuple w = (w1,...,w,,) a lifting function on A and w, lifts A,- to its graph A,- = {(a,w,-(a)) : a 6 A,} C Rn“. This notation is extended in the obvious way: A = (A1, . . .,An), Q,- = conv(A,-), Q = Q1+...+ Q", etc. Let 8,, = {C1, . . . , Cm} be the set of cells of A which satisfy for 1 S j S m, (a) dim(conv(Cj)) = n, (b) conv(Cj) is a facet, i.e., an n—dimensional face, of Q = conv(A) whose inner normal oz 6 (R"+1)* has positive last coordinate. In other words, conv(CJ-) is a facet in the lower hull of Q. If the lifting function (1) is chosen generically, then 8,, is a fine mixed subdivision of A = (A1, . . .,An) induced by w [13, 22]. Let S = {C1,...,Cm} be a fine mixed subdivision of A = (A1,...,A,,), then the cell Cj of type (1,...,1) is a sequence of subsets (C]l),...,CJ(-")) where each C1“) = {a,0,a,:1} is a 2-element subset of A,- for 1 S i g n. Let V(Cj) be the n x n— matrix whose rows are ail — am, 1 g i g n. It can be shown that V01(Cj) = ldethlell- The following is a special case of Theorem 2.4 of [16]. Theorem 2.1.4 Let S = {C1,...,Cm} be a fine mired subdivision of A = (A1,...,A,,). Then M(A1, . . . , An) 2 :VOKCi) = Z ] d€t(V(C;))], 10/ where the summation is taken over all cells C,- of type (1, . . . , 1) in S. 2.2 Algebraic deformations In order to find all isolated zeros of a given polynomial system P(a:) :2 (191(2), ...,pn(:r)) in C”, we apply the following procedure: According to Theorem 2.1.2, if all p,’s have constant terms, then the mixed volume is in fact, an upper bound for the number of isolated zeros of P(.r) in C"; otherwise we augment the monomial x0 to those p,’s that do not have constant terms. We assign generic coefficients to all the monomials in P(a:). Denote the new system by Q(a:) = (q1(:r), . . . , qn (113)) and let A’ = ( ’1,...,A;,) be its support, so (1,-(2:) = Z Emirar, i: 1,...,n, a’EA’i where a' = (a’1,. . . , a;,) and 2:“, == 33]“1 - - afi’n. Consider the linear homotopy H(:c, t) = (1 —- t)Q(a:) + tP(a:) = 0. We wish to obtain zeros of P(:r) in C" at t = 1 by following the solution curves of H (II), t) = 0 emanating from the zeros of Q(a:) in C" at t = 0. By the following lemma, the zeros of Q(a:) in C" are isolated, nonsingular and are contained in (0)". Lemma 2.2.1 [29] Given a polynomial system P(a:) = (p1(:r),...,p,,(;t:)) in the variables a: = (2:1,...,a:,,), there exist an open dense subset V of C" such that if 11 €=(el,...,e,,) EV, then tee Vfor alltyéO ian, and inyC" isasolution of q1:p1($la°-',$n)+€1 : 0 qn :pn($la--°axn)+€n : 0, then 3(qi.---.qn) _ .., ranka(xl’...,$n)(y)—n and yE(C), where C“ = (C\{0}. In Section 2.2.1, we will employ the polydedral homotopy to find these isolated zeros of Q(a:) in (0‘)". We will see in Section 2.2.2 that every isolated zero of P(a‘) in C", at t = 1, can be reached by a solution curve of H (as, t) = 0 emanating from an isolated zero of 62(13) in (0‘)", at t = 0, obtained in Section 2.2.1. 2.2.1 The nonlinear homotopy We solve Q(a:) = (q1(a:), . . .,qn(;r)) = 0 by lifting its support A’ = ( '1, . . . ,A;,) by a generically chosen lifting function a) = ((121, . . . ,wn) where w,- : A: -—> R for i = 1, . . . ,n. Consider the polynomial system C(x, t) 2: ((1‘1 (1:, t), . . . , (inks, t)) in the n + 1 vari— 12 ables 3:1,. . .,xmt where (2.2) q,(x,t)= Z 5,,arxa't“t(°l), i=1,...,n. a’EAfi For i = 1,.. ,,n we write A’-= (all), .. .,ak(),)_1,0} and 221k,- = N, N E Z. Let b 2 (b1, . . . , b,,) where b,- represents the constant term of q,-(:r) for i 2 1,. . .,n, and = = “ b ...c n ’ n b Nbeallth C (Cl) aCN) (CLagn’ Cl 0:181) 1) la 9 n a] )3 ’cn,a£(3‘)_1’ n) e C 6 corresponding coefficients of Q(:r, t). Q(:r,t) provides a homotopy with t as the parameter and Q(a:, 1) = Q(:z:). The lifting function w 2: (w1,...,w,,) induces a fine mixed subdivision S“, of A’ = ( ’1, . . . , Ag). By projecting the facets in the lower hull of Q down, we obtain cells of type (1, . . . , 1) in the fine mixed subdivision 5“,. By Theorem 2.1.4, the mixed volume M( ’1, ..., Ag) is equal to the sum of the volumes of these cells. Proposition 2.2.2 For almost every choice of constant terms of Q(£L‘), 0 is a regular value of Q(:r,t) on (0‘)" x (0,1]. PROOF: Consider Q(b, 2:, t) : C" x (C‘ )" x (0, 1] —> (C‘ )" where b here is also regarded as a variable of Q. The Jacobian matrix of Q with respect to b (the constant terms of Q(:c)), denoted by DbQ, is of rank n in (0‘)" for t E (0, 1]. This implies that 0 is a regular value of Q on C" x (0‘)" x (0, 1] . It follows from generalized Sard’s Theorem that for almost every choice of constant terms b, 0 is a regular value of Q(b, -, -) on (0‘)" x (0,1]. [:1 As a consequence of Proposition 2.2.2, for t 6 (0,1], all isolated zeros of Q(:z:, t) are nonsingular. 13 The system Q(:r:) is said to be in general position if its coefficients c satisfy C(c) aé 0. for C(31) = (91(y).--.,gm(y)), where {91(y).-~.gm(y)} is a set of polynomals determined by the monomials of Q(:1:). Proposition 2.2.3 For allt 6 (0,1], the system Q(:c, t) is in general position. PROOF: Let C(y) = (g1(y), . .., gm(y)) be the polynomial system determined by the monomials of Q(1:) in the definition of Q(:c) being in general position, and Z = {y E C” | C (y) = 0}. The Lebesgue measure of Z is zero and C” \Z is open and dense. Since the coefficients of Q(.’L‘) are randomly chosen, c ¢ Z and thus the system Q(:r,1) = Q(:r) is in general position. Forj = 1,...,N, let *7,- be the power oft associated with the term in Q(:1:, t) = (41(z,t), . ..,(jn(ac,t)) with cj as coefficient. Write 7 2 (71, . . .,yN). For each fixed t 75 0, the support of Q(:I:,t) is the same as that of Q(a:). Since C(c) 75 0, there exists in such that g,-0(c) 94 0, which implies g,-O(ct7) $5 0 where ct7 represents (clt71,. . .,cNt'm). If y E Z", then g,0(ct7) is a nontrivial polynomial in t. Thus, there are only finitely many t such that g,0(ct7) = 0. This implies that C(ctl) has only finitely many zeros. If ’y E Q” , then factor out the reciprocal of the least common multiple of the denominator of the 7,38 from the polynomials in C(ct"). This results in a set of nontrivial polynomials in t and we again conclude that C(ctl), considered as a system of polynomials in t, can only have finitely many zeros. Let {t1, . . . ,t,;} be the set of values oft in (C such that C(ct") = 0. Write t, = rsew’ (1 g s g 6). For t = t3, C(ct") becomes '71 i710 ’YN i7v0 _ gl(c1r3 e ‘,...,chs e ‘ ) — 0 14 ’71 i719 7N i7N0 _ gm(c1rse ‘,...,ch8 e 3) — 0. Thus as long as 0 ¢ 6,, V 1 g s S 6, then G(c(e“’t)7) = C((c(e‘9)7)t7) 75 0, \7’ t E (0, 1]. Hence, with the coefficients of Q(a:) being randomly chosen, the system Q(a:, t) is in general position for all t E (0, 1]. D By Proposition 2.2.3 and Theorem 2.1.1, for each fixed t 6 (0,1], Q(a:, t) has M( ’1,. . .,A;,) number of isolated zeros in (0‘)". Thus there are M( ’1,...,A;,) number of solution curves of Q(:r,t) : 0 in (0')" x (0,1]. These curves can only diverge to infinity when t —+ 0. Let 5,, = {C1, . . . ,Cm} and Cj : (03(1), ...,CJW) be a cell of type (1, . . . , 1) in 5,0. For i = 1, ...,n, let Cy) = {a§0,a§1} C A[-. Since Sw is a fine mixed subdivision, the vectors a’11 —— a’lo, . . . ,alu — 6;, are linearly independent. Thus I I an — “10 vol(Cj)) = det I I [ anl — a’nO .l and conv(Cj) is a facet of Q’ = (Q’l, . . . , Qil) whose inner normal 6! E (R"+1)* has positive last coordinate. Let a = (a, 1) = (a1,...,oz,,, 1) be the inner normal of conv(CJ-) = conv({a’10,a'11},...,{a;,0,a;,1}) where 612, = (a;,,w,~(a§,)) for i = 1,...,n and l = 0,1. Let a:(t) represent the general solution curves of Q(:r,t) :2 0. With :z:(t) = (161(t),...,:r:,,(t)), let 551“) = tall/1m 15 $71“) = tan yn(t)i or, simply, x(t) = t°y(t). Substituting this into (2.2) yields, for i = 1, ..., n, (Mat) = Z 5.,arya't<0’“')tWi(a’) a’EA; : Z a" a’ya't<(asl)r(a, vwi(a’))) a'EAfi (23) 2 Z: Ei,a’yalt<é’dl>, a’EAfi Let 6,- = minareA;(d, 61’). Since conv(Cj) is a facet of Q’ = ( "1,. . . , Q;) with inner normal 0?, conv(CJ(-i)) = conv({a;0,a;1}) is a face of Q; and 6r 2 (a, 1) also serves as an inner normal of conv(C,(-i)) for each i = 1, ..., n. It follows that ((31,620) = ((1,621) = fl,- and (6,6’) > 6,- for a’ E A: \ Cf). Hence, factoring out tfii in (2.3), we have (Mt/at) = ”15151031010 + 54,51,310“ + Z 6,,arya't<é’°’)‘fi‘), i = 1, . . .,n. a’EAfi\C§’) Consider the homotopy R(y, t) = (r1(y, t), . . . , r,,(y, t)) = 0 where (2.4) r,(y,t) = emgoyaio + gang/“11 + Z 6,,alya't<év5’>-5', 2': 1...,.n a’EA’,\C,(-i) (2.5) (j,(y,t) =tfi‘r,(y,t), 2:1,...,n. Since (d,d’) > B,- for a’ E A;- \ Cf), i = 1,. . ..n, R(y,0) = 0 is the binomial system 16 with generic coefficients: ‘ “i0 ‘ all 0 01,630?! + 01,631?! — (2.6) I I — a — a Cn,a'noy 710 I 671.0212] "I — 0 From (2.5), the zeros of R(y,t) coincides with those of Q(y,t) for t 75 0 and since .r(t) .—. t°y(t), R(y, 1) = Q(z, 1) = Q(at), and zeros of R(y,t) at t = 1 are precisely the zeros of Q(x). The system (2.6) has det 3 (= vol(C,—)) solutions in (0‘)". Thus by following the solution curves (y(t),t) of R(y,t) = 0 starting from the solutions of R(y, 0) = 0 in (2.6), we can obtain the vol(CJ-) number of solutions of Q(r) = 0 in (0‘)” at t = 1. According to Theorem 2.1.4, we can obtain all M( ’1,...,A;,) number of isolated zeros of Q(at) in (0‘)" if we repeat the same procedure for each cell of type (1,. . . ,1) in Sw. 2.2.2 The linear homotopy Consider the linear homotopy (2.7) H(:I:,t) = (1 —- t)Q(a:) + tP(.7;) = 0. 17 We wish to obtain zeros of P(x) = (p1(x), . . . , pn(x)) in C" at t = 1 by following the solution curves of H (x, t) = 0 emanating from the zeros of Q(x) = (q1 (x), . . . , qn(x)) in C" , which by Lemma 2.2.1, are contained in (O )”, at t = 0. Recall that the system Q(x) is constructed from P(x), with generic coefficients assigned to all monomials in P(x), and have the monomial x0 augmented to those p,’s that do not have constant terms. Thus, the linear homotopy (2.7) is essentially a special case of the Cheater’s homotopy [27]. Theorem 2.2.4 [27] (The Cheater’s homotopy) Let c = (Cl, . . . ,cm) E C"1 and d be the total degree of P(x) = (p1(x), . . . ,pn(x)) with x = (x1, . . . ,xn). There exists an open, dense, full-measure subset U of Cm"m such that for (b1, . .,b;,c‘{,. .., 0:") E U, the following holds: (a) The set X“ of solutions x = (x1, . . .,xn) of (11(131w-w33n)=p1(CI.-.-.c;.xl,...,xn)+b‘f=0 qn(.’131,...,113n) :pn(C:,...,C:n,.’L'1,...,(13n)+1);:0 consists of do isolated points, for some do 3 d. (b) The smoothness and accessibility properties hold for the homotopy H(x,t) = P((I—t)c'1‘+tc1,...,(1—t)c:n +tcm,x1,...,xn)+(1——t)b* where b“ = (b'f, . . . , b',‘,). It follows that every solution of P(x) = O is reached by a path beginning at a point of X“. 18 To apply Theorem 2.2.4 to our situation, let m = $21 k(i) — n, b; = b,, 1 S i g n and (of, . . . ,c;,) be the coefficients of Q(x) excluding the constant terms. By construction, the coefficients (b'f,...,b;“,,c’{, . . .,c,‘,,) of Q(x) are in U. By part (b) of Theorem 2.2.4, every zero of P(x) can be reached at t = 1, by a solution curve of H (x, t) = 0 emanating from a zero of Q(x) at t = 0. Thus, by following all the solution curves of H (x,t) = 0 starting from the isolated zeros of Q(x) in (0‘)" at t = 0, we can obtain all the isolated zeros of P(x) in C" at t = 1. CHAPTER 3 Algorithms In chapter 2, we have seen that by following the homotopy paths of H(x,t) = (1 - t)Q($) + tP(SE) = 0. starting from the zeros of Q(x) = ((11 (x), . . . , qn(x)) in C" at t = 0, which by Lemma 2.2.1 are contained in (0‘)", we may obtain the zeros of P(x) = (p1(x), . . . ,p,,(x)), the polynomial system that we want to solve, in C", at t = 1. To do so, we must first find the zeros of Q(x) in (0‘)". The method outlined in chapter 2 uses a generic lifting w 2 (£01,. . . ,wn), and then projects the lower hull(i.e. union of facets whose inner normal (1 has positive last coordinate) of the lifted Newton polytope Q’ = ( -,1, . . . , 6;) of the polynomial system Q(x, t), defined by (2.2), down to obtain cells of type (1, . . . , 1) in the induced fine mixed subdivision Sm. In this chapter, we first of all discuss the details of the implementation of the procedure to obtain cells of type (1, . . . , 1) in the induced fine mixed subdivision SW, and secondly, solve the binomial system that corresponds to each such cell, and thirdly, give an outline of the homotopy 19 20 curve tracing procedure. 3.1 Vertex-set algorithm From the formula given by (2.1), the non-vertex points of the Newton polytope Q; = conv(A§), 1 S i g n, do not contribute to the mixed volume M(A’1,. . . , Ag) of the system Q(x). To make our method more efficient, we intend to exclude those non- vertex points in the supports from further considerations in the first place. Deciding whether a point is a vertex of Q; reduces to a linear programming problem: 'Let A; = {a[i),.. . ,a£'(),)}, 1 S i g n and 2?:1160') = N. To test if a?) (1 S l g k(i)) is a vertex of Q2, we solve the following problem: minimize ,u ] 25S) 1. #lA- am +ua,)=a]‘) 2:3" WA +u=1 vnzo (3.1) subject to i #20. If (3.1) has an optimal solution with u = 0, then ali) is not a vertex of Q, or a)” ¢ vert(Q§), where vert(Q;) denotes the vertex set of Q. We can obtain vert(Q;) by repetitive applications of (3.1) as described in the following algorithm. Algorithm VERTEX_SET Input: A’-— — (am, .. ”ahi()i)}’ 1 S i g n 81 Seti=1. 21 52 Set vert(Q;) = {a]i), . . -,a]:(),)}- S3 Let j range from 1 to k(i). If a?) 9! vert(Q;), then vertQ; = vertQ§\{a§-i)}. S4 Seti=i+1. Ifign,gotoS2. 3.2 Edge-set algorithm To find cells of type (1, . . . , 1) in the fine mixed subdivision 5,, of A’ = ( ’1,...,A;,) induced by the lifting 62, let Cj «2 (03(1),...,C§n)) be such a cell. Then for each i, conv(C?) is an edge (one-dimensional face) in the. lower hull of the lifted polytope Q; of (j,(x, t) (1 g i g n). For a random lifting w = ((411,. . . ,wn), we begin by constructing edge sets to contain edges that lie in the lower hull of Q2 (1 g i g n). After applying Algorithm VERTEX_SET, each polytope Q; (1 S i S n) can be [7, . ii) are the vertices of Q;- represented as conv({v “,ng ), where for 1 _<_ l g m,, v and m,- is the cardinality of the vertex set of 9;. As an illustration, for the polytope ’1, to test if the edge connecting 6]” and i219) lies in the lower hull of Q’l, we have the following constraints: 65% = 65% (3.2) D]1)C¥ S USPO, 21 — 3, ,ml where 61 = (a1, . . . ,ozn, 1) and a1, . . . , an are the unknowns. We use the equation in (3.2) to solve for one of the afs. Upon substituting the value of that a,- into the rest of the inequalities in (3.2), we obtain inequalities of the 22 form (3-3) Ad |/\ 9- where the number of variables(i.e., the number of components of a) is now one less than before. The solvability of the problem (3.2) is then equivalent to the feasibility of (3.3) which can be tested by solving the following linear programming problem: minimize 6 (3.4) subject to Ad — 66 g b, e > 0, where e = (1,...,1). If 60 = min 6 is equal to zero, then (3.3) is feasible. Thus the edge connecting 6]” and 6%” lies in the lower hull of lifted polytope Q’l. We repeat the above procedure for all other possible forming of edges among vertices in Q’1 and subsequently those in Newton polytopes Q]c (2 S k S n). Algorithm EDGE_SET Input: vert(Q§) = {v]i), . . .,vféli}, 1 S i g n 51 Set i = 1. 82 Let 81 range from 1 to m,- —1 and 32 from 31 +1 to m,. If 31 < 32, then for each edge connecting 23g? and 6]? (vertices from Q), conduct the feasibility test on the corresponding problem of the form (3.3). If the problem is feasible, then store the pair (22g), vggl) in edge set E,. S3 Seti=i+1. Ifign,thengotoSZ. 23 3.3 Algorithm for finding cells of type (1, . . . ,1) We construct cells of type (1, . . . , 1) by starting with an edge e1 from Q’l and adding one edge ek from Q]c (2 g k g n) at a time. As each edge is added, the k- tuples (el, . . . ,ek) is tested on whether é1+- . ~+é,c lies in the lower hull of Q’1+ - -+ Q1, (3.2) is modified to have [6 equations and more inequalities: 23(1) (llé jiia : U112 -(2) - _ -(2) . 0.12101 ‘7 t))-22a .(k) . -(k) - 'U- CY : 'U- a 31:1 31:2 (3.5) 4 .1. .1. . . v(- )0: < villa, 13 r13 m1, T1¢J111J12 Jli — v a 0, where e = (1,...,1). If 60 = min 6 is equal to zero, then (3.6) is feasible. Thus 61 + + 6;, lies in the lower hull of Q’1 + - ° '+ Q],. We repeat the above procedure for all other possible edge combinations from Q’1 + - - - + Q],. Only those edges that pass the feasibility test are eligible to be augmented. Algorithm LOWER_HULL Input: edge sets E1, . . . , E, from Algorithm EDGE_SET 81 Set k = 1 and set the current k-tuples to contain edges in E1. Set k = k + 1. 82 V e), E E,c and each (k — 1)-tuple (e1, . . .,ek_1) of edges stored, if e), is found such that 229;] e} + e“), lies in the lower hull of :3 Q; + Q],, then add that edge 6,, to the current (It — 1)-tuple and store as a k-tuple. S3 If k = n, then each n-tuple of edges stored corresponds to a type (1, . . . , 1) cell. S4 Setk=k+1. Ifkgn,thengot082. 3.4 Finding zeros of R(y, 0) From Algorithm LOWER_HULL, we obtain a set of n-tuples of edges, each mem- ber corresponding to a type (1, . . . , 1) cell, along with its inner normal (1. For each 25 such cell Cj and its inner normal a, recall that by making the change of variables x(t) = t"y(t) and factoring out the minimal power of t, we obtain the homotopy R(y, t) given by (2.4). When t = 0, R(y, 0) = 0 is a binomial system given by (2.6): — a’ — a’ _ 01,a',oy 1° + 01,611?! “ — 0 — a’ — a’ _ Cn,a’noy n0 + Cn,a’nly "1 " 0 To solve this system in (0‘)", we rewrite it as Un For abbreviation, we write yv = (yv1,...,yv") and b = (b1,...,bn), then (3.8) becomes (39) y" = b. 26 With this notation, it can be verified that for an n x n integer matrix U, the following holds: (yU)V ___ y(VU). If V is a lower triangular matrix, namely, U11 0 O 021 ”022 0 V : vnl vn2 ' ' ° vnn J where vij’s are all integers and v,,~ ¢ 0 for all i = 1, ..., n, then since det V # 0, (3.9) becomes Eli)” = 1)1 ytll'ziyg'zz : b2 (3.10) 1)} v 2 ‘U _ yln y2n . . .ynnn _ b". By forward substitution, (3.10) has |v11| x x |v,,,,[ = |detV| = vol(C,-) solutions. In general, we may lower triangularize V by multiplying on the right by an integer matrix U with Idet U | = 1. This matrix U can be found by the following procedure: The greatest common divisor d of two integers a and b is given by dzgcd(a,b)=ka+lb, IC,lEZ 27 where the integers k and l are obtained by the Euclidean algorithm. In matrix notation, this can be formulated as a d U = b 0 where k l U : _ Q 9. d d and det(U) = 1. In the multivariate case, let U (a, b) be the identity matrix except for the entries (U(a, b))ii : k? (U(a, b))ij : l, a WWMM=—3(W%Wn=g A product of a series of matrices of the form U (a, b) can be chosen to upper trian- gularize a matrix from the left. To lower triangularize V, let U be an integer matrix with |det U] =2 1 such that UTVT is upper triangular. Thus VU is lower triangular. Now, let 2” = y and substitute it into (3.9), we have (3.11) yv = (2U)V = em] = b. Since VU is lower triangular, z = (2:1, ..., 2") in (3.11) can be solved and the number of solutions equals |det(VU)| = |det(V)| - |det(U)] = |det(V)|. Consequently, we have as many solutions of y = (y1,...,y,,) as in (3.9). 28 3.5 Numerical curve tracing The central part of the solver is the tracing of the solution curves of the nonlinear homotopy R(y, t) = 0 given by (2.4), and the linear homotopy H (x, t) = 0 given by (2.7). The curve tracing process of both the nonlinear and linear homotopy involves the following predictor—corrector method. Algorithm TRACE_PATH input: starting point (x,,t,) SI 82 S3 S4 (Evaluate) From (x,, t.) on the solution curve (x(t), t) of H (x, t) = 0, evaluate the tangent vector (%(t,),1), where H,(x,,t,)‘f,—f(t,) + Ht(x.,,t,.) = 0. (Predictor) Along the tangent vector (%§(t,),1) with stepsize 6, predict (mete) = (x..t.) + 6(%§-(t.).1)- (Corrector) From the predicted point (x0, to), use Newton’s method to find a sequence (x,, to), i = 0, 1, . . . that converge to the point (x*, to) on the solution curve, as a step forward from (x..., t.). If the correction is unsucccessful (i.e., the sequence does not converge), then cut the stepsize 6 by half and return to $2 for a finer prediction. (Update) If to = 1, stop and output x“ as the target solution; otherwise, replace (x.,t,) with (x*, to), adjust the stepsize if necessary, and go to S1 for further forward tracing. 29 Correction Prediction Figure 3.1. The prediction-correction process Remark 3.5.1 From Hx(x, 13% + H, = 0, we have Hx(x,t)%% = —H,. Here, the matrix H,,(x,t) is of full rank. We solve for the tangent vector fi—f by the use of Gaussian elimination on the matrix Hx(x,t). Remark 3.5.2 The algorithm in fixed-t correction is Newton’s iterations: 1", = IL'J'_1— H,($j_1,to)—1H(£L‘j_1,to), j: 1, 2, 3, . . . Upon rearranging, we have H’(x,-_1,t0)(x,-_1 — x,) = H(x,--1, to), j = 1, 2, 3,. . .. The Gaussian elimination method is used to solve for xJ-_1 — xj. For the first part of the curve tracing process with the homotopy R(y, t), discussed in Section 2.2.1, the solutions of the binomial system (2.6) serve as starting points at 30 t = 0. The total number of curves to trace is equal to the sum of volumes of cells of type (1, . . . , 1) which equals the mixed volume M( ’1, . . . ,A;). By Theorem 2.1.1 and Proposition 2.2.3, we obtain all the M( ’1,. . . , Ag) number of isolated zeros of Q(x) in (0‘)" at t = 1, at the end of the execution of Algorithm TRACE_PATH for the homotopy R(y, t) = 0 given by (2.4). The second part of the curve tracing process with the homotopy H (x, t) discussed in Section 2.2.2 takes all the isolated zeros of Q(x) in (0‘)" as starting points at t = 0. The total number of curves to trace is equal to M( ’1, . . . ,A;). We obtain all the isolated zeros of P(x) in C" at t = 1, upon execution of Algorithm TRACE_PATH for the homotopy H (x, t) = 0 given by (2.7). CHAPTER 4 Minimal Bézout number Polynomial systems that arise in applications are very often deficient in the num- ber of roots, i.e., the actual root count is less than the total degree of the system. The choice of the start system is important for solving polynomial systems by the homo- topy continuation method because it ultimately determines the number of homotopy paths to trace in the process. In the past, the classical way of constructing the start system is based on variant Bézout numbers of the given system. The natural approach is to find among all possible homogenizations of the given system by grouping the variables in different ways the one that corresponds to the minimal Bézout number. A smaller Bézout number translates into less homotopy paths that need to be traced. Many papers on the topic have addressed reductions in the number of solution curves to trace in the homotopy continuation method [8, 24, 38, 39]. This chapter describes the procedure for finding the minimal Bézout number over all possible homogenizations of a given polynomial system. We wish to make a com- parision of this traditional approach with the use of the polyhedral homotopy where 31 32 the total number of curves that need to be traced in the continuation process is equal to the mixed volume of the support of the given system. The computational results of which are presented in the next chapter. 4.1 Notations and definitions The complex n-space C" can be naturally embedded in the complex projective space I?" = {(x0, . . . , x,,) E C"+1\(0,...,0)}/ ~ where the equivalence relation ~ is given by x ~ y if x 2 cy for nonzero c E C. Similarly, the space C’“ x - . . x Ck": can be naturally embedded in ll”’°l x - - - x P“. A point (yl, . . . , ym) in (C’cl x - - - x Ck"1 with y,- = (y]j), . . . ,yg)), j = 1,...,m, corresponds toapoint (z1,...,zm) in 11”"1 x- - -> 0) times the Bézout number of the corresponding minor. The Bézout number of each minor is then computed recursively by the same row expansion procedure. Let K’ be the vector K 2 [k1, . . .,km] with k,- replaced by k,- — 1. With the following recurrence relation: b(D,K,i) = Z (1,-,- b(D’, K’,i+ 1), j=l, ICj¢0 the Bézout number is given by B = b(D, K, 1). If the degree matrix D is sparse, we may skip over computations where d,,- = 0 and avoid expanding the recursion below that branch. We expand along the row with the most zero elements, by exchanging rows if necessary. 4.3 Multi-homogenizations The number of possible multi-homogenizations of an n-variable system is essen- 35 tially the same as the number of ways to partition n distinct objects into m iden- tical boxes, m : 1, . ..,n. Denote these numbers as p(n,m),m = 1,...,n. Then p(n, 1) = 1, since there is only one way to place all n objects into one box. Also, p(n,n) = 1 corresponds to putting 1 object in each of the 71 boxes. We have the following relation: p(n,m) =m*p(n—1,m)+p(n—1,m—1) since for each of the p(n — 1, m) partitionings of n — 1 items, we may add the nth item into any one of the m boxes; also, for each of the p(n — 1, m — 1) partitionings of n - 1 things into m — 1 boxes, we can put the nth item in the mth box by itself. Values of p(n,m) are listed in the following table, along with the total number of partitions ”P(n) for n objects: ’P(n) = "m=, p(n,m). The numbers p(n, m) are known as Stirling numbers of the second kind [50]. Each of the ’P(n) partitions yields a distinct multi-homogenization of the n-variable system. n p(n.1) P(n.2) p(n.3) p(n.4) p(n.5) p(n.6) p(n,?) p(n.8) p(n»9) p(n.10) 7P(n) 1 1 1 2 1 1 2 3 1 3 1 5 4 1 7 6 1 15 5 1 15 25 10 1 52 6 1 31 90 65 15 1 203 7 1 63 301 350 140 21 1 877 8 1 127 966 1701 1050 266 28 1 4140 9 1 255 3025 7770 6951 2646 462 36 1 21147 10 1 511 9330 34105 42525 22827 5880 750 45 1 115975 11 678570 12 4213597 13 27644437 36 Example 4.3.1 Consider the following system which arises from a test for numerical bifurcation: 5x? — 6x]x§ + .212; + 2x1x3 = 0 —2x?x2 + 2xfx3 + 2x2x3 = 0 x¥+x§—0.265625 = 0 There are ”P(3) = 5 ways to multi-homogenize this system. For each partition of the variables, we form the corresponding degree matrix D and apply the row expansion algorithm: {331,172,333} {$1,$2},{$3} {$1,$3},{$2} {$1},{$2,$3} {$1},{$2},{$3} K = [3] K = [2,1] K: [2,1] K: [1,2] K: [1,1,1] ’9] -91 [94- 94- —941- D=7 0:710:63 0:63 0:631 _2] _20‘ _22, 22] _220‘ 82126 8:32 8:210 8:126 8244 Thus, the minimal Bézout number is 32, which corresponds to the partition {$11 $2}, {$3}: 4.4 Efficiency measures For each partitioning of the variables, we form the corresponding degree matrix. We do not actually form the homogenized polynomials, but rather, we scan through 37 the terms for each group of variables, find the term with the largest degree with respect to that group. Since the degrees are all nonnegative, the Bézout number is the sum of nonnegative degree products. As we test homogenizations in search of minimal Bézout numbers, we may abort the calculation if the running subtotal exceeds the current minimal Bézout number. When applying the row expansion algorithm, it is helpful to skip over any degree that is zero. This not only avoids unnecessary computation, but it also assures that any subterm we compute at any level of the tree of partitionings has a string of strictly positive degrees above it. When any of the subterms at the leaves of the tree exceeds the current minimum, we are safe in aborting the Bézout number calculations for the corresponding partitions. CHAPTER 5 Numerical experiments The techniques discussed so far find their natural application in polynomial sys- tems arising in a variety of fields and modelling geometric and kinematic constraints. As mentioned in the previous chapter, for those systems, the traditional approach is to find among all possible homogenizations of the given system the one that cor- responds to the minimal Bézout number. A smaller Bézout number translates into proportionately less computer time when we intend to find all isolated solutions of the given polynomial system using the homotopy continuation method. In this chapter, we make a comparision of this traditional approach with the use of the polyhedral homotopy where the total number of curves that need to be traced in the continuation process is equal to the mixed volume of the support of the given system. We present the numerical results of applying our algorithm to an extensive list of polynomial systems that arise in applications. 38 39 5. 1 Problem statements 5.1.1 Robot manipulator PUMA This is the inverse position problem of a PUMA robot. To find the relative joint Zi+l (Joint i+ 1) Link i Figure 5.1. The basic notation displacements given the hand position and orientation of the arm of the robot [37] (a,, d,- and 07,- are constants while 0,- is a variable), we have the following system: z§+x§—1 = 0 x§+xZ—1 = 0 40 x2 + x2 -— 1 = 0 x3 + 23% — 1 = 0 0.004731x1x3 — 03578332223 — 0.1238x1 — 0001637232 — 0.9338x4 + x7 — 0.3571 = 0 0.2238x1x3 + 0.7623x2x3 + 0.2638151 — 0.07745x2 — 0.6734x4 — 0.6022 2 0 xsxg + 0.3578231 + 0.004731x2 = 0 —0.7623x1 + 0.2238332 + 0.3461 2 0. Here x,- (i = 1,. . .,8) represent the sine and cosine functions of the robot’s joint angles 6,. The number of variables of this system is 8 with total degree 27 = 128. The optimal Bézout number is 16 with the partition {x1, x2}, {x3, x4, x7, x8}, {2:5, x6}. The mixed volume is 16 and there are 16 isolated zeros. 5.1.2 Robot manipulator ROMIN This is the inverse position problem of the robot manipulator Romin [14]. Let l2, l3 represent the length of the two arms of the robot, and 61, 62, 03 represent the joint angles placing the robot at a given position P = (a, b, c). Denote s, = sin 6,- and c, = cos 0,, i = 1,2,3. We obtain the following system (once [2 and I3 are fixed): —sl(l2c2 + l3C3) = a c1(12c2 + l3c3) = b 1282 + [383 =5 C s?+c? = 1, i=1,2,3. l P (a,b,c) Figure 5.2. The ROMIN manipulator The number of variables of this system is 6 with total degree 25 = 32. The Optimal Bézout number is 16, with the partition {31, c1}, {62, c3, 82, 33}. The mixed volume is 4. For 12 = 718mm, l3 2 600mm and the point (500, 500,0), the number of isolated zeros is 4. 5.1.3 Neural network — adaptive Lotka-Volterra System A neural network can be thought of as a network of interconnectred cells in which activity levels at each cell are inhibited or excited by the activity of the other cells. The Lotka-Volterra model(the oldest predator-prey model), with interaction coefficients dependent on time, (allowing the weights of the connections between cells to vary) is one such network. The model to be analyzed consists of n interconnected cells. The rate of change of activity level at the ith cell is the nonconstant Lotka-Volterra 42 equations [46]: Xi“) = X,(t)[1— 0X40) + iéiinj(t)Xj(t)la 1 S i S n. i=1 An interior critical point of the Lotka-Volterra system is any positive vector (:61, ..., xn) satisfying n 1—cx,~+Zd,-,-x,x§=0,1§i5n F1 where the connection matrix A; = (6,,-) is given by 0 ifi==j Af=t1 “ignirj lsnjsn \ where p is a given integer between 0 and n. We solve the following system in order to find the interior critical points of the Lotka-Volterra system for n = p = 4: 1:11;; + 21:83 + x1233 — cxl +1 2 0 x223? + 162233 + x223 — cxg + 1 = 0 x3x]2 + x3x§ + x3x2 — cx3 + 1 = 0 x473? + x4x§ + x4x§ — cx4 + 1 = 0. The number of variables of this system is 4 with total degree 34 = 81. The optimal Bézout number is 81 with the partition {x1, x2, x3, 2:4}. The mixed volume is 73 and 43 for a generic choice of c, there are 73 isolated zeros. 5.1.4 Symmetrized four-bar mechanism This is the problem of synthesizing a four-bar with two given fixed pivots (0,0) and a = (1,0), to generate a path through five precision points d,- = (d,1,d,-2), j = 0, . . . ,4 [41]. The following system is set up to determine all sets of lengths r1, . . . ,r5 that allow the coupler point to pass through all the precision points: couplerpoint _, d ’1] \ (0.0) C Figure 5.3. Four-bar linkage at the jth position 2 2 2 2 2 2 2 anxlx3 + a12x1x3x4 + a13x1x3 + al4x1x4 + a15x1x4 2 2 2 +a16x1 + az7x1x2x3 + a18x1x2x3x4 + 0191315132133 + a110x1x2x4 2 2 +0111$11172$4 + (11121131333 + (11131715133134 + (111411311133 + 011511311134 2 2 2 2 2 2 +041611315L‘4 + amx2x3 + 0113£E2IE3$4 + (1119152133 + (1120132114 2 2 2 470121172334 + (1122332 + 0123372563 + (11245132333334 + (1125332173 44 2 2 2 _ _ +0125$2$4 + 012811221174 + (1123.733 + 0.1293134 — 0, l — 1, 4. The number of variables of this system is 4 with total degree 44 = 256. The optimal Bézout number is 96 with the partition {x1,x2}, {x3,x4}. The mixed volume is 80. For generic choice of coefficients, there are 36 isolated zeros. 5.1.5 The nine-point problem This is the problem of finding all four-bar linkages whose coupler curve passes through nine precision points [58]. Figure 5.4. Four-bar ABCD with coupler triangle CPOD at the initial precision point P0 (left); Displacement of the four-bar to a new precision point P, (right) The 8 variables are a, 6,4,2, b, b, 31,3; and there are a set of constants 6,, (i,- (j = 1, . . . ,8). After expunging the lower order terms, we have for j = 1, . . . , 8 the following 45 systems of equations: A A (9161):?)[039 —- (11005101 - i?) + 51(0 - 93)) +0153 - &$)(5j(b - 3?) + 57(1) - W] = 0- The number of variables of this system is 8 with total degree 78 = 5764801. The optimal Bézout number is 645120 with the partition {a,€1}, {b,b}, {2,2}, {31,9}. The mixed volume is 83977. There are 4326 isolated zeros [58]. 5.1.6 Chemical equilibrium This is the problem of combustion of propane(C3H8) in air(02 and N2) [33] to form the ten products listed in table 5.1 : 3111/2 + 91 — 33/5 = 0 2913/2 + 3129i + 211 + R7yzys + R892 + 1293/294 + 2131031; _ R95 = 0 2923/3 + 213593 + R693 + 1273/2313 — 895 = 0 293 + R93121914 — 4R95 = 0 91112 + 923/3 + 93 + 91 + R593 + R693 + 1279293 + R892 + 1299294 + R1093 - 1 = 0 where the variables are y1,y2,y3, y4, y5. The number of variables of this system is 5 with total degree 2 x 3 x 3 x 2 x 3 = 108. The optimal Bézout number is 56 with the partition {yl}, {y2, y4, y5}, {313}. The mixed volume is 16. With p = 40 and R = 10, there are 16 isolated zeros. 46 Table 5.1. Products of Propane Combustion Product Subscript Description C02 1 carbon dioxide H20 2 water N2 3 nitrogen C O 4 carbon monoxide H2 5 hydrogen H 6 hydrogen atom OH 7 hydroxyl radical O 8 oxygen atom N O 9 nitric oxide 02 10 oxygen Table 5.2. Definitons of constants Constant Definiton R5 K 5 Rs KGP—W R7 K 719—” 2 R8 K 819—1 R9 K919 ”2 R10 K1019—1 Table 5.3. Equilibrium Constants Constant Value K5 1.930 x 10-1 K6 2.597 X 10_3 K7 3.448 x 10‘3 K8 1.799 x 10‘5 K9 2.155 x 10‘4 K10 3.846 x 10‘5 47 5.1.7 Lumped-parameter chemically reacting system The following system arises as a result of the isothermal catalytic reaction sequence between two adsorbed species [5, 28]: -a1:r1(1— x3 — :174) + (123:3 — (2:1 — a6) = 0 —a3x2(1 — 3:3 — 2:4) + max; —(:132 — a7) = 0 a1$1(1 — x3 — 12:4) — (121:3 — a5$3$4 = 0 a3$2(1 — 3:3 — 2:4) — (145174 — (1511:3154 = 0. The number of variables of this system is 4 with total degree 24 = 16. The optimal Bézout number is 8 with the partition {$1}, {332}, {3:3}, {2:4}. The mixed volume is 7 and there are 4 isolated zeros. 5.1 .8 Heart-dipole A system of eight nonlinear equations in eight unknowns is derived for the determi- nation of the magnitudes, directions, and locations of two independent dipoles in a two-dimensional conducting region from boundary potential measurements [45]. It has biomedical significance in electrocardiographic applications: 331 + 3:2 — 0.6325 = 0 $3 + $4 + 1.34534 2 0 211225 + 322:6 — x3327 — $4.733 + 0.8365348 = 0 $1227 + $21138 + $31115 + 11741136 — 1.7345334 = 0 48 212% — 3312:; — 2133235227 + 1:223 — x2222; — 2242:6133 — 1.352352 = 0 232% — $31103 + 2331335137 + $423 — $4.233 + 2221:5113 + 0.843453 = 0 3 2 3 2 3 2 3 2 _ $1135 - 3x1z5x7 + $35137 — 351231371125 + $2ch — 3322:5228 + $4.718 — 32:43:ng + 0.9563453 — 0 1:32;; — 351232533; — 12:11.“; + 3xlx7$§ + $41172 - 315411761133 - $2133 + 3932338533 — 12342523 = 0- T he number of variables of this system is 8 with total degree 22 x 32 x 42 = 576. The Optimal Bézout number is 193 with the partition {1:1, 2:2, 2:3, 11:4}, {235, 336, $7,158}. The mixed volume is 121 and there are 4 isolated zeros. 5.1.9 Conformal analysis of cyclic molecules This problem arises in computational biology. The molecule has a cyclic backbone of Figure 5.5. The cyclic molecule 49 6 atoms, typically of carbon. The bond lengths and angles provide the constraints while the six dihedral angles are allowed to vary. In kinematic terms, atoms and bonds are analogous to links and joints of a serial mechanism in which each pair of consecutive axes intersects at a link. In Figure 5.5, backbone atoms are regarded as points p1, ...,p6 E R3 ; the unknown dihedrals are the angles w1,...,w6 about axes (p6,p1) and (1),-4,19,) for z' = 2, ...,6. The following system is set up to compute all conformations of the cyclic molecule [10]: f1 = 511 + 51213 + 31315: + fl14t§t§ + fl15t2t3 = 0 f2 = [321 + [322% + [323% + fl24t§ti + fizststi = 0 f3 = fl31 + 332152124" 6331.3 + 634t¥t§ + 335t1t2 = 0 where [3,5 is the (2', j)-th entry of the matrix " '1 —9—1—138 —9—1—138 —9—1—138 The number of variables of this system is 3 with total degree 43 = 64. The optimal Bézout number is 16 with the partition {2:1}, {3:2}, {1:3}. The mixed volume is 16 and there are 16 isolated zeros. 50 5.1.10 Camera motion from point matches This is the problem of computing the displacement of a camera between two positions in a static environment [10], given the coordinates of certain points in the two views, under perspective projection on calibrated cameras. Using quaternions formulation Figure 5.6. Single point seen by two camera positions and scaling the coordinates of the given frames(dividing all the components by 1000), the following system is obtained: —d1q1 - £12612 - 61343 +1 = 0 —3.6d1q1 + 4.1d1q2 + 2.0d — 1q3 + 0.1d1 + 4.1d2q1 + 1.8d2q2 + 3.7d — 2q — 3 — 0.2012 +2.0d3qi +3.7d3q2 -— 4.0d3q3 + 0.3d3 + 0.1q1 — 0.2q2 + 0.3q3 + 5.8 = 0 0.3464d — 1q1 + 0.1732d1q2 — 5.999648d1q3 — 0.1732d1 + 0.17323”1 — 5.999648d2q2 —0.1732d2q3 + 0.3464(12 — 5.999648d3q1 - 0.1732d3q2 — 0.3464d3Q3 — 0.1732d3 —0.1732q1 + 0.3464q2 — 0.1732q3 + 5.999648 2 0 51 Table 5.4. Coordinates of the two frames point first frame second frame 1 (1000,2000,1000) (1100,1900,900) (1414,-1414,1414) (1314,-1514,1314) (-1732,0,1732) (—1832,100,1632) (2000,1000,3000) (-1100,-900,1900) (—1000,-1000,2000) (2100,1100,2900) WAGON —5701.3d1q1 — 2.9d1qz + 3796.7d1q3 — 1902.7d1 -- 2.9d2q1 — 5698.7d2q2 +1897.3d2q3 + 3803.3d2 + 3796.7d3q1 + 1897.3d3q2 + 5703.1d3q3 + 0.7d3 —1902.7q1 + 3803.3q2 + 0.7q3 + 5696.6 = 0 —6.8d1q1 — 3.2d1qQ + 1.3d1q3 + 5.1d1 — 3.2d2q1 — 4.8d2q2 — 0.7d2q3 -— 7.1d2 +1.3d3q1 — 0.7d3q2 + 9.0d3q3 — £13 + 5.1q1 — 7.1q2 — Q3 + 2.6 = 0 -—2.140796d1q1 — 3.998792d1q2 + 3.715992d1q3 — 3.998792d3q2 — 2.140796d3q3 +0.2828d3 — 0.2828q1 + 0.2828(13 + 5.856788 = 0. The number of variables of this system is 6 with total degree 26 = 64. The optimal Bézout number is 20 with the partition {d1, d2, d3}, {q1, (12, q3}. The mixed volume is 20 and there are 20 isolated zeros. 5.1.11 Electrical network The following are the steady-state equations for the load flow in an electrical network [26]: 333(611171 + 012332 + (313) — 014 = 0 52 $4(621$1+C22$2+C23)—C24 = 0 $1(Cs1$1+$32$2+033)—C34 = 0 $2(C41$1+$42$2+C43)—C44 = 0 {1—3z' —4—2i —3+82' 1+z' \ 4+2 2—32' —4—32' —3+5z' C=(c,-,-)— 1+3i —4+2z' —3—8z' l—z' \4—2' 2+32‘ —4+3z‘ —3—5z‘) The number of variables of this system is 4 with total degree 24 = 16. The optimal Bézout number is 6 with the partition {3:1, 3:2}, {3:3, 2:4}. The mixed volume is 6 and there are 6 isolated zeros. 5.1.12 Vibrating systems The following represent equations of motion for the vibrating system formulated by means of the Lagrangian method [26, 23]: P(A).r = 0 $1+$2+$3+$4+$5+l = 0 where P0.) = A2)? + A1). + A0 53 and [—10 2 —1 1 3‘ r1 2 1 2 1‘ _ 10 2 —1 2 -2- 2 —11 2 —2 1 2 1 2 1 3 2 9 3 —1 —2 A2: —1 2 —12 —1 1 A1: 1 2 o —2 —2 .Ao= —1 3 10 2 —1 1 —2 —1 —10 2 2 1 —2 2 3 2 —1 2 12 1 1 3 1 1 2 ’11. _1 3 —2 3 3_ _—2 —2 1 1 10‘ The number of variables of this system is 6 with total degree 35 = 243. The optimal Bézout number is 10 with the partition {231, $2, 233, 2:4, 2:5}, {A}. The mixed volume is 10 and 10 real eigenvalues along with its corresponding eigenvectors are found. 5.1.13 6R inverse position problem This is the inverse kinematics of the 6R manipulator problem in 8 equations in 8 unknowns [40, 53]: xi,_, + 2331—1 = 0, l: 1, ...,4 anxlxg + (1122:1214 + (1135132333 + 014$2$4+ 0151351137 + 01611351138 + (117176137 + 018$6$8+ 0191131 + 0110372 + 0111173 + 0112174 + 01135554“ (11141125 + 0.1151177 + (1.1161133 + (1117 = 0, (=1, ..., 4. In the equations, 2,-(2' = 1, ..., 8) represents the sine and cosine functions of the robot’s joint angles. The number of variables of this system is 8 with total degree 28 = 256. The optimal Bézout number is 96 with the partition {$1,152, $5,236}, {23,24,277, 2:8}. The mixed volume is 64. With the coefficients in [53], there are 32 isolated zeros. 54 5.1.14 6R2 inverse position problem The following is the inverse kinematics of the 6R manipulator problem in 11 equations in 11 unknowns [57]: c¥+z§1+z§2-l = 0 z§I+z§2+z§3—l = 0 231+222+z§3—1 = 0 zgl+z§2+z§3—1 = 0 01233 — C2 + 221231 + 222232 = 0 -Cs + 231241 + 232242 + 233243 = 0 —C4 + 241251 + Z42252 + 243253 = 0 —Cl + Z51Z61 + 252262 + 253263 = 0 —61€2232 + (12221 + 613231 + 014241 + (15251 - 61222 + 62222233 + 83232243 -€3Z33Z42 + 84242253 — 64243252 + e5252263 - 65253262 - P61 = 0 C162231 + 612222 + 613232 + (14242 + 615252 + 81221 — 62221233 — 63231243 +63233Z41 — 64241253 + 84243251 - 65251263 + 85253361 - P62 = 0 01612 + (13233 + (14243 + (15353 + 62221232 - 62222231 + 63231242 —€3Z32Z41 + 64241252 — 84242251 + 65251262 - 65252361 '- P63 = 0. The number of variables of this system is 11 with total degree 211 = 1024. The optimal Bézout number is 320 with the partition {221,223,Z41,Z42,Z43}, {231, 232, 233, 251, Z52, 253}. The mixed volume is 288 and there are 16 isolated zeros. 55 5.1.15 An interpolating quadrature formula over a grid The following system occurred in the context of wavelet functions [52]. To introduce wavelets, we introduce the notion of multi-resolution analysis: A multi-resolution analysis of L2(R) is defined as a sequence of closed subspaces V} C L2(R), j E N, with the following properties: 1- Vj C Vj+1, 2. 21(2) 6 V]- 41) v(2:r) E Vj+1, 3. v(:1:) 6 V0 4:) 11(2:+1) E Vb, 4. Uffiioolg is dense in L2(R) and 0,5ng = {0}, 5. A scaling function cp 6 V0, with a non-vanishing integral, exists so that the collection {90(27 — l)|l E Z} is a Riesz basis of V0. We assume that the scaling function (p has compact support [0,L] and satisfies a refinement equation WC) = 2 2 111.9092: - k) k with L + 1 non-zero coefficients hk. To construct an n-point interpolating quadrature formula (with degree of precision 77.) with points 22,, = g + 7' for integrating a function defined on a grid, the polynomial system F(w) = 0, with the jth equation given as n—l k .7 f(w)=Zwk<§+T) —Mj=0, j=0,1,...,n k:0 56 has to be solved. Here the constants M, are the pth moments of the scaling function (,0. The unknowns are 0) = (1.00, ...,wn._1) where 02,-, 0 _<_ i S n — 1, are the weights of the quadrature formula and T is the range of the shift. For n = 4, the system becomes w0+w1+w2+w3— 1 = 0 1 3 0207' + 0117 + (1227' + 0237 + ital + 012 + 5023 — 0.63397459621556 = 0 1 02072 + 02172 + c0272 + 02372 + wl'r + 20127 + 30137 + 1021 + 012 + 9 51.03 —0.40192378864668 = 0 3 9 3 (1)073 —+— 02173 + 01273 + 02373 + §w172 + 301272 + §w372 + 4wlT + 27 1 27 3WQT + 74—12137' + 3601 + £02 + "8—(423 —' 0.131091535679036 = 0 3 01074 + 01174 + 02274 + 02374 + 201173 + 402273 + 602373 + 501172 + 2 27 2 1 27 1 6w27' + 311137 + 50117 + 40127 + 31.037 + 1—6021 + 81 022 + E023 + 0.30219332850656 = 0. The number of variables of this system is 5 with total degree 5 x 4 x 3 x 2 x 1 = 120. The optimal Bézout number is 10 with the partition {7'}, {020, 021, (02,013}. The mixed volume is 5 and there are 5 isolated zeros. 5.1.16 Optimizing the Wood function The following system is derived from optimizing the Wood function [35]: 2002:;3 — 2002:1222 + 2:. — 1 = 0 —100x¥+ 110.12:2 + 9.91:4 — 20 = 0 57 180:1:3— 1802:3234 + $3 — 1 = 0 —90:1:§ + 9.92:2 + 100.132.. — 20 = 0. The number of variables of this system is 4 with total degree 32 x 22 == 36. The optimal Bézout number is 25 with the partition {2:1}, {2:2, 2:4}, {2:3}. The mixed volume is 9 and there are 9 isolated zeros. 5.1.17 An application in electrochemistry The following system is derived from an application in the field of electrochemistry [60]: 6 5 4 2 3 2 _ 0 (21202 + c2272 + 63272 + c4$1$3 + 652:2 + c6272 + 0722 + c3 — 5 4 2 2 3 2 _ 0 c9552 + c1022 + 6111131582 + 612331233 + c1322 + 61411211172 + c1522 + c1622 + 617 — 2 6133131 '1' (319.2133 '1' C20$2 ‘1' C21 = 0. The number of variables of this system is 4 with total degree 60. The optimal Bézout number is 52 with the partition {2:1, 2:2}, {2:3}. The mixed volume is 18 and there are 15 isolated zeros. 58 5.1.18 Benchmark i1 from the interval arithmetics bench- marks The following system is derived from the standard benchmarks in interval arithmetic papers [17, 34]: 2:1 — 0.25428722 —- 0.1832475723423339 = 0 11:2 — 0.37842197 — 0.1627544923111101‘6 : 0 2:3 — 0.2716257? — 0.1695507121223310 = 0 2:4 — 0.19807914 — 0.1558531633723126 : 0 2:5 — 0.44166728 — 0.19950920237226503 = 0 2:6 — 0.14654113 — 0.189227932335055010 = 0 $7 — 0.42937161 — 0.2118048423225333 = 0 :58 — 0.07056438 — 0.1708120823127376 2 0 2:9 — 0.34504906 — 0.1931274023102524 2 0 11:10 — 0.42651102 — 0.2146654423450323] 2 0. The number of variables of this system is 10 with total degree 310 = 59049. The optimal Bézout number is 452 with the partition {2:1}, {2:2}, {:03}, {2:4}, {3:5, 2:7}, {2:6}, {2:8}, {2:9}, {11:10}. The mixed volume is 66 and there are 50 isolated zeros. 59 5.1.19 Optimal multi-dimensional integration formula The following system arises in the derivation of optimal multi-dimensional integration formula [36, 18]: $1+$3+$5+2$7—1 Z 0 131.732 '1‘ $31134 + 2115156 ‘1” 251371118 ‘1' 2137.739 — '3' = 0 2 231233 + $327: + 22:5:rg + 223723 + 2:177:53 — g = 0 2 271:1); + $3273 + 22:52:: + 2:37.223 + 227233 — 7 = 0 2 2:123 + 2:327: + 2.13523: + 22:71:; + 2273:; — 9 = 0 2 1 235.26 + 2237233239 — 5 = 0 1 $5513; ‘1' 2137138133 — 53 = 0 1 $5272 + 2372:8233 + 237273.29 — B = 0 3 3 1 5175.226 + 1372:8359 + 2372:8279 — 2T 2 0. The number of variables of this system is 9 with total degree 1 x 2 x 3 x 4 x 5 x 3 X 5 x 4 x 5 = 36000. The optimal Bézout number is 8852 with the partition {2:1, 2:3, 2:5, 2:7}, {2:2, 2:4, 2:6, 2:8, 2:9}. The mixed volume is 136 and there are 16 isolated ZGI‘OS. 5.1.20 The system of A. H. Wright The following system is presented in [61]: 60 xf—xl+$2+$3+x4+25—10 = 0 273+271—272+273+:r4+:c5—10 = 0 $§+$1+$2-$3+x4+235—10 = 0 $i+$1+$2+$3—IL‘4+$5—10 = 0 x§+$1+zg+233+$4—2:5—10 = 0. The number of variables of this system is 5 with total degree 25 = 32. The optimal Bézout number is 32 with the partition {2171,22, $3,221,235}. The mixed volume is 32 and there are 32 isolated zeros. 5.1.21 The Reimer5 System The following system is available at the PoSSo test suite: 2x2—2y2+222—2t2+2u2—1 = 0 2233—2y3+2z3—2t3+2u3—1 = 0 2x4—2y4+2z4—2t4+2u4—1 = 0 2x5—2y5+2z5—2t5+2u5—1 = 0 22:6—2y6+226—2t6+2u6—1 = 0. The number of variables of this system is 5 with total degree 2 x 3 x 4 x 5 = 720. The optimal Bézout number is 720 with the partition {27, y, z, t, u}. The mixed volume is 720 and there are 144 isolated zeros. 61 5.1.22 Butcher’s problem The following system is available at the PoSSo test suite: 1 1 233235 + 232236 + 23427 — 2:17, — 52:7 — 5 = 0 2332:; + 2722:: — 2:423; + 2:? + 2:? — E234 + 5237 = 0 2 3 2 1 2 $1223.25 — 274237 + 2:7 — 524237 + 2:7 —— 62:4 + 3237 = 0 1 1 2:327g + 272233 + 2342:? — 23‘; —- 52:? + $427 — 523$ - Z5137 — 4 = 0 3 4 2 3 3 2 3 1 2312632526 + 23427 — 237 + 5234237 — 52:7 + 52:42.7 — 12:7 — §$7 — g = 0 2 7 1 1 (1315133172 + (1:423; — (I); ‘1‘ 11745133— 5517; + §$4$7 — 613$ — 155137 — 1—2' 1: 0 3 1 13 7 1 —2:42:'?, + 23$ — 2:423; + 52; —— 323427 + T2173 + 51:07 + 51 = 0. The number of variables of this system is 7 with total degree 2 x 3 X 3 x 4 x 4 x 4 x 4 = 4608. The optimal Bézout number is 1361 with the partition {2:1}, {222,223,221}, {275,236}, {2:7}. The mixed volume is 24 and there are 5 isolated ZCI‘OS. 5.1.23 Construction of Virasoro algebras The following system can be found in [51]: 822% + 821(232 + $3) — 823223 + 22:1(x4 + 235 + 2:6 + 237) — 2234227 — 2235236 — 2:1 = 0 82:3 + 8232(2:1 + 233) — 8231533 + 22:2(224 + $5 + 236 + $7) — 22:42.15 — 222527 —- $2 = 0 822% + 82:3(271 + 232) — 821212 + 22:3(214 + $5 + $6 + $7) — 22:42:53 — 2226237 — 273 = 0 8212+ 2231(254 — $7) + 2$2(:r4 — 2:6) + 2(233 + 32:3)(274 — $5) + 22:4(4235 + 276 + 237) — $4 = 0 821% + 2221(205 — 2:6) + 2222(205 — $7) + 2(223 + 32:8)(2:5 — x4) + 235(424 + $5 + 227) — 275 = 0 62 82:2 + 22:1(2:5 — 2:5) + 22:2(26 — 234) + 2(23 + 32:3)(225 — 227) + 22:4(427 + 2:4 + $5) —- 2:6 = 0 817% + 2321(1127 — $4) + 2232(JI7 — $5) + 2(233 + 3$3)($7 — 1176) + 234(4136 + $4 + $5) — $7 = 0 810% + 6(24 + :05 + 235 + 2:7)133 — 6224205 — 6235277 — 2:8 = 0. The number of variables of this system is 8 with total degree 28 = 256. The optimal Bézout number is 256 with the partition {2:1,22,23,24,m5,2:6,$7,$8}. The mixed volume is 200 and there are 200 isolated zeros. 5.1.24 The cyclic n-roots problem The following system [4, 11] arises from the problem of finding all bi-equimodular vectors 2: E C", i.e., all 2: with coordinates of constant absolute value such that the Fourier transform of 2: is a vector with coordinates of constant absolute value. This is equivalent to the problem of finding all solutions (20, 21, ..., zn_1) of An(the alternating group) with all |2j|=12 (The relation between 2: and z is z,- = 2:j+1/2:j) 20+Zl +...+Zn_1 = 0 zoz1+ 2:122 + + zn_lzn_1+ 2.1-120 = 0 202122 + 212223 + + zn_lzozl = 0 2021...zn_2 + + zn_1zo...zn_3 = 0 2021...Zn_1 = 1. Table 5.5. Results for the cyclic n-roots problem 63 n totdeg mdeg M(Q) N(Q) 5 120 120 70 70 6 720 720 156 156 7 5040 5040 924 924 For n = 7, we have the following system: 20+21+22+23+24+25+25 =0 2021 + 2122 + 2223 + 2324 + z4z5 + zsze + 26.20 = 0 202122 "‘1' 212223 '1' 222324 '1' 232425 '1' 242526 ‘1' 252520 ‘1' 252021 = 0 20212223 + 21222324 + 22232425 + 2324.25.25 + 24252620 + z5zsz021 + zgz02122 = 0 2021222324 + 2122232425 + 2223242526 + 23.24.252620 + 2425252021 + 2525202122 + 2520212223 2 0 202122232125 + z122z3z4z5zs + 222324254320 + 232425262021 + 242526.202le + 252620212223 '1' 262021222324 = 0 20212223242526 — 1 = 0. The number of variables of this system is 7 with total degree 7! = 5040. The Optimal Bézout number is 5040 with the partition {20, 21, 22, 23, 24, 25, Zsl- The mixed volume is 924 and there are 924 isolated zeros. For other values of n, the results are summarized in Table 5.5. Here totdeg denotes the total degree of the system, mdeg the optimal multi-homogeneous Bézout number, M(Q) its mixed volume and N(Q) the total number of isolated zeros. 64 5.1.25 Combustion chemistry The following is a combustion chemistry problem [42, 43]: $2 +2236 +$9+2$10 “-10-5 = 0 II o $3 + 2:8 — 3.10—5 $1+233 + 2235 + 22:8 + 2:9 +2310 — 5.10"5 = 0 $4 + 22:7 —10-5 = 0 051404371041:5 — z? = 0 0.1006932.10"62:6 — x3 = 0 0.781627310-l5x7 — 2:3 = 0 0149623310451:8 — 2,23 = 0 061944111042:9 — 213:2 = 0 0.2089296.10-14x10—a.~1x§ = 0. Due to the range of the coefficients, the scaling routine as described in [42] is applied. The scaled system: 1.0181548330166910—1222 + 9.8961010050642210—1236 + 1.34637048100730m9 + 3.4697031721043213“) — 2.12454115933396 = 0 5.7673979535713510—123 + 7.8994975430157710—123 — 2.19492968782850 = 0 7.1962195493698810-129 + 9.2726133519085.10—12:10 + 8.95128807036246.10—12:3 + 2.4520825054171428 + 8.73159766974099.10”2501 + 1.3772225917620225 — 5.67773314994310 = 0 65 2.50030218520604.10—3x4+1.9998791368743810z7 -—1.99987913687440.10 = 0 —1.377222591762032:¥ +7.26099038733160.10‘12:5 = 0 —9.89610100506425.10-1x§+1.01049898287039x6 = 0 —1.99987913687438.10x§+5.00030217607503.10-2x7 = 0 —1.93702197268146232:1+5.162564O4988361.10‘128 = 0 -—9.68877757611935.10‘12:221+1.03212194948595229 = 0 —3.21732159608141z§z1+3.10817545009477.10-1x10 = 0. The number of variables of this system is 10 with total degree 25 x3 = 96. The optimal Bézout number is 44 with the partition {2:1, 24, 2:7}, {2:2, 23, 2:5, 2:6}, {2:8, 2:9, 210}. The mixed volume is 16 and there are 16 finite solutions. 5.1.26 Economic modelling The following system arises in the field of economic modelling [42]: (2:1 + 21232 + 2:223 + 232:4 + 2:425 + 2:526 + 2:61:37)“ — 1 = 0 (2:2 + 212:3 + 2:224 + 233235 + 242:6 + 235:1:7)2:3 — 2 = 0 ($3 + 2:124 + 222:5 + 2:32:6- + 2:4237)2:3 — 3 = 0 (23.; + 212:5 + 22236 + 232:7)238 — 4 = 0 (2:5 + 27126 + (522:7)238 — 5 = 0 (£136 + $1$7)$8 — 6 = O $71138—7 = 0 $1+$2+$3+$4+$5+$5+$7 = 0. Table 5.6. Results for the Economic modelling problem 66 n totdeg mdeg M(Q) N (Q) 5 54 20 8 8 6 162 48 16 16 7 486 112 32 32 8 1458 256 64 64 The number of variables of this system is 8 with total degree 36 x 2 x 1 = 1458. The optimal Bézout number is 256 with the partition {21, :62, 2:3, 2:4, 2:5, 2:6}, {2:7, 2:8}. The mixed volume is 64 and there are 64 isolated zeros. For other values of n, the results are summarized in Table 5.6. Here totdeg denotes the total degree of the system, mdeg the optimal multi-homogeneous Bézout number, M(Q) its mixed volume and N(Q) the total number of isolated zeros. 5.1.27 An application from neurophysiology The following system is obtained from the newsgroup sci.math.num-analysis and sci.math.symbolic: 2% + 2:3 — 1 = 0 2:3 + 203 — 1 = 0 $5333 '1' $6333 — C] = 0 2752:]‘ + 2352:; — 02 = 0 2 2 _ 0 11355831111 ‘1' $6$4£E2 — C3 —— {11511333}? + 11361134133 — C4 = 0. 67 The number of variables of this system is 6 with total degree 22 x 44 = 1024. The optimal Bézout number = 216 with the partition {2:1, 1:2, 52:3, 2:4}, {3:5, 2:6}. The mixed volume is 20 and there are 8 isolated zeros. 5.1.28 The system of E. R. Speer The following system is given in [54]: 4,6(71 + 201— 8x1)(a2 — (13) — {13211331134 + 1132 + $4 ——- 0 4,8(71 + 201— 82:2)(a2 - a3) — $1133.12; "i" 1131+ $3 = 0 46(n + 2a1— 83:3)(a2 — a3) — 2312:2234 + 172 + $4 = 0 4,3(71 + 201— 81:4)(02 — (13)— 113123213 + $1 + CL'3 = 0 where a1 2 121+ $2 + $3 + 334, a2 = zlzgx3x4, a3 = 231132 + $2333 + $3124 + $4231 and fl and n are parameters to the system. The number of variables of this system is 4 with total degree 54 = 625. The optimal Bézout number is 384 with the partition {2:1}, {2:2}, {2:3}, {3:4}. The mixed volume is 96. With 46 = 0.657958984375000 -— 0.187652587890625z', n = 0.937683105468750 — 0.288299560546875i, there are 43 isolated zeros. 68 5. 1.29 Solotarev system The following system is available at the Frisco test suite: 3$¥—2z1—$3 = 0 3 2 2 2 — 0 arl—arl—xlz3+$3— :134— — 3:13—2:13 — — 0 arg—zj—xgx3—z3+2 = 0. The number of variables of this system is 4 with total degree 2 x 3 x 2 x 3 = 36. The optimal Bézout number is 10 with the partition {1:1, 2:3}, {x2}, {2:4}. The mixed volume is 6 and there are 6 isolated zeros. 5.1.30 Trinks system This system arises in Number Theory and is available at the Frisco test suite: 45272 + 355135 — 165336 — 36 = 0 35272 + 25x3 + 401.2; — 271:5 = 0 25.732235 — 165223 + 153:;1 — 183:3 + 303:4 = 0 15332333 + 2051:4235 — 92:1 = 0 —11:z:(33 + :10le + 2333134 2 0 —11:1:5:r5 + 333% + 99101 = 0. The number of variables of this system is 6 with total degree 23 x 3 = 24. The optimal Bézout number is 24 with the partition {11:1, 3:2, 1:3, 134, $5,176}. The mixed volume is 69 10 and there are 10 isolated zeros. 5.1.31 A small system from constructive Galois theory: 391 This system is obtained from the Frisco test suite: —:1:1:z:2 — 21:312.; = 0 9:131 + 4:125 = 0 —41:4:c6 — 2331237 ~— 3332273 2 O —7:1:5 + 9338 — 8:137 = 0 —42:3:1:7 — 5.7;ng — 6:174 — 3231 = 0 —5:1:3 — 6323237 — 72:2 + 9235 = 0 9333 + 63:8 — 5:135 = 0 91135—71133'l'8 = 0. The number of variables of this system is 8 with total degree 24 : 16. The optimal Bézout number is 10 with the partition {$1,x2,$3,:1:4,x5}, {m6,x7,x8}. The mixed volume is 10 and there are 10 isolated zeros. 5.1.32 n-dimensional reaction-diffusion problem For a general 11, the following system has 2" solutions: 330 Z$n+l : 0 xk_1—— 233;, + $k+1+ axk(1—— 17k) = 0, k = 1,2, ...,n. 70 For n = 3, the system becomes: —2:I:1 + 1132 + 0835634534310 — 11:1) 2 0 3:1 — 23:2 + 333 + 0.835634534x2(1 — 11:2) 2 0 51:2 — 2333 + 0.835634534x3(1 — 2:3) = 0. with total degree 23 :2 8. The Optimal Bézout number is 8 with the partition {2:1, 2:2, 233}. The mixed volume is 7 and there are 7 isolated zeros. 5.1.33 4-dimensional Lorentz attractor The equilibrium points of a chaotic attractor in 4-dimension [31] is given by: :rl(:r2—-a:3)—a:4+c = 0 x2(x3—$4)—$1+c = 0 x3(x4—x1)—x2+c = 0 274(131 —:I:2)—:1:3+c = 0 where c is a given constant. The number of variables of this system is 4 with total degree 24 = 16. The optimal Bézout number is 14 with the partition {2:1, 1:2}, {21:3, 11:4}. The mixed volume is 12 and there are 11 isolated zeros. 71 5.1.34 A bifurcation problem The following system arises from a test for numerical bifurcation [19]: 5:13? — 623?:133 + 3313:; + 21:1:r3 = 0 —2:c[5z2 + 223121;; + 2z2z3 = 0 x§+x§—0.265625 = 0. The number of variables of this system is 3 with total degree 9 x 7 x 2 = 126. The optimal Bézout number is 32 with the partition {51:1, .102}, {$3}. The mixed volume is 16 and there are 16 isolated zeros. 5.1.35 Benchmark D1 from the interval arithmetics bench- marks This system is derived from the standard benchmarks in interval arithmetics papers [17, 34] and is available at the Frisco Test Suite: x¥+x§—1 = 0 $§+$§—1 = 0 x§+$§—1 = 0 $$+$§—1 = 0 x§+x§0—1 = 0 z¥1+xf2—1 = 0 35133 + 21125 + 1137 — 3.9701 2 0 72 3221234 + 22.1% + 231238 -— 1.7172 = 0 3332174 + 231321136 + (1321133 — 4.0616 2 0 233239 + 225239 + 237279 — 1.9791 = 0 {1722341139 + 11321135339 + $2IE8IL'9 + $111310 — 1.9115 = 0 —£L‘3.’E10£E11 — 1151171051311 — $7113101E11 'i' $411312 + (176.7312 '1' 115811312 — 0.4077 2 O. The number of variables of this system is 12 with total degree 212 = 4068. The optimal Bézout number is 320 with the partition {$1,272},{23,24,35,2:6,$7,2:8}, {2:9, 2:10}, {2:11, 2512}. The mixed volume is 192 and there are 48 isolated zeros. 5.1.36 Caprasse’s system The following system is available at the Frisco test suite: 233233 + 22:12:22.2; — 22:1 — 223 = 0 2272233234 + 2312:: — 2:1 — 2273 = 0 —2:‘?2:3 + 4231233273 + 427%232234 + 2233234 + 42:? — 10233 + 423-1233 — 10232224 + 2 = 0 —2:12:§ + 4232273234 + 4271233232 + 2232232 + 42:1203 + 42:; — 102:3 + 2 = 0. The number of variables of this system is 4 with total degree 32 x 42 = 144. The optimal Bézout number is 62 with the partition {2:1, 2:2}, {2:3, 2:4}. The mixed volume is 48 and there are 48 isolated zeros. 73 5.1 .37 Arnborg7 system The following system is obtained from the Frisco test suite: 2:2yz + 2:sz + 253/22 + 23yz + 23y + 2:2 + yz = 0 xzyzz + 2331222 + $2yz + xyz + yz + 2: + z = 0 223/222 + 2:2sz + :mfz + xyz + $2: + z + 1 = 0. The number of variables of this system is 3 with total degree 4 x 5 x 6 = 120. The optimal Bézout number is 48 with the partition {23,y, z}. The mixed volume is 20 and there are 20 isolated zeros. 5.1.38 Rose system The following represents a general economic equilibrium model and is available at the PoSSo test suite: 20 y4— -,—7—2:2 = 0 7 7 50 35 49 2 4 4 4 2 _ _ _ __ _ _ _ __ = 0 ‘T Z +10“ +482 27$ 27$ 216 3 . 3 7 7 3 3263222 + 2:"y3 + $x5y2z + g$4y3 - @6443”? — if? 60933 6332 7732 2133 +1000$ y + 2001’ y z 125‘" W 50:” Z 49 2 3 147 2 2 23863 2 2 +1250” y + 2000‘” y z 60000:” W _ 31:211., _ 27391 “3+ 4137 x ,2 _ 10782: 2,2 _ 5887 m3 400 800000 J 800000 y 9375 y 200000 _ 1029 3 24353 ”2 343 Z, _ 0 160000y 1920000’ 128000 _ ' 74 The number of variables of this system is 3 with total degree 4 x 6 x 9 = 216. The optimal Bézout number is 144 with the partition {2:}, {y, z}. The mixed volume is 136 and there are 136 isolated zeros. 5.1.39 Moeller4 System The following system is available at the PoSSo test suite: y+u+v—1 = 0 z+t+2u—3 = 0 y+t+2v~1 = 0 w—y—z—t-u—v = 0 1569 3 2 — t = 0 312503” +37 “ 15625y The number of variables of this system is 6 with total degree 4 x 2 = 8. The optimal Bézout number is 8 with the partition {22, y, z,t,u, v}. The mixed volume is 7 and there are 7 isolated solutions. 5.1.40 KatsuraN System This is a problem of magnetism in physics and is available at the PoSSo test suite: 2fi+2f+2£+2fi+2fl+m?—v==0 xy+yz+2zt+2tu+2uv—u = 0 2zz+2yt+2zu+u2+2tv—t = 0 75 2$t+2yu+2tu+2zv—z = 0 t2+2rrv+2yv+2zv—y = 0 2x+2y+2z+2t+2u+v—1 = 0. The number of variables of this system is 6 with total degree 25 = 32. The Optimal Bézout number is 32 with the partition {2:, y, z,t,u}. The mixed volume is 32 and there are 32 isolated zeros. 5.1.41 Cohn—2 system The following system is available at the PoSSo test suite: 233312 + 42:23;2 — 2:2yz2 + 2882:23/2 + 2072:2312 + 1152223122 + 1562:3122 + $23 — 34562323; + 207365;,2 + 190082:yz + 82944sz + 432x232 — 49766423111 + 6220822 + 29859842: = 0 3,313 + 4313::2 — 3,2th + 4y2t3 — 48y2t2 — 5yzt2 +108yzt+ 22t+144zt— 1728z = 0 —2:222t + 42:22t2 + 23152 + 2:3t2 + 2:32 +156$2zt+ 207:1:z2t + 11522:zt2 + 28822t2 + 4322322 + 190082:zt -— 3456221: + 829442.12 + 20736th + 6220822 —- 497664zt + 29859842 = 0 y3t3 —- $3,212 + 431%2 + 4y2t3 — 5:1:y2t — 48y2t2 + 2:231 + 108m + 144mg — 17282: = 0. The number of variables of this system 4 with total degree 5 x 6 x 5 x 6 = 900. The optimal Bézout number is 450 with the partition {23, y, z}, {t}. The mixed volume is 124 and there are 18 isolated zeros. 76 5.1.42 Cassou-Nogues The following system is available at the Frisco test suite: 5b4cd2 + 6114c3 + 21b4c2d —— 144520 — 8b2cze — 28b2cde — 648b2d + 3602d2e + 95%? — 120 = 0 30040361 — 32cde2 — 72062121 — 24122038 — 432627;2 + 57606 — 5764.2 + 16026d26 + 16.12.22 + 168.22 + 9647;“ + 39643112 + 18b4cd3 — 4325242 + 24b2d3e — 16b2c2de — 240a + 5184 = 0 21652ch — 162b2d2 — 815%2 + 100806 — 1008de + 1552851.: — 15b263e — 8054.22 + 4042.:2 + 40c2e2 + 5184 = 0 4b2cd - 352112 — 45%2 + 2206 — 22de + 261 = 0. The number of variables of this system is 4 with total degree 7 x 8 x 6 x 4 = 1344. The optimal Bézout number is 368 with the partition {5}, {c, d, e}. The mixed volume is 24 and there are 16 isolated zeros. 5.1.43 A “dessin d’enfant” I system The following system is available at the Frisco test suite: 6033010020 '1' 10022010031 + 8032010021 — 1620¥0021 + 16021030 + 14031020 ‘1' 48010030 = 0 15033010021 — 1620?0022 — 312010020 + 24010030 “1" 27031021 + 24032020 + 18022010032 + 30022030 "1' 84031010 2 0 77 —240210 + 420233 — 64222 + 112232 = 0 180033010 — 284222210 — 1625‘:0 + 60222032 + 50232210 + 70230 + 55233221 + 260231 — 112220 = 0 66033210 + 336232 + 90231 + 78222233 — 1056210 — 90221 = 0 136233 — 136 = 0 4222210230 + 2232210220 + 6220230 — 162a¥0220 + 3231221210 2 0 28222210233 + 192230 + 128232210 + 362310.20 — 300010021 + 40032021 — 6480?0 + 44022031 = 0 where the variables are am, 020, (121, (122, 030, am, (132, 233. The number of variables of this system is 8 with total degree 34 x 22 = 324. The optimal Bézout number is 108 with the partition {233, am, 020, 222, 231, 232, 221}, {0.30}. The mixed volume is 46 and there are 46 isolated zeros. 5.1.44 A “dessin d’enfant” II system The following system is available at the Frisco test suite: 16220232 + 182210.31 + 20222230 = 0 —80223 + 180234 + 855a35 = 0 7021031 + 8021030 = 0 210235 — 210 = 0 40220234 + 442-21233 + 48222232 + 52223231 + 280230 2 0 27020033 + 30021032 ‘1' 33022031 + 36023030 2 0 78 55020035 + 60021034 + 65022033 ‘1’ 70023032 + 80030 + 375031 = 0 78021035 ‘1‘ 84022034 + 90023033 — 170020 + 102031 '1' 480032 = 0 136223235 — 114222 + 152233 + 720234 = 0 105022035 + 112023034 — 144021 + 126032 ‘1‘ 595033 2 0 where the variables are: 020, 021, 022, 023, 030, 031, 032, 033, 034, 035. The number of variables of this system is 10 with total degree 28 = 256. The optimal Bézout number is 126 with the partition {220,232,a21,231}, {222, 230, 0.23, 234, 0.35, 233}. The mixed volume is 42 and there are 42 isolated zeros. 5.1.45 Sendra system The following system is available at the Frisco test suite: —270z4y3 — 3145;,4 — 6892:1113 + 1428 = 0 362:7 + 417sz — 422453,? — 2702:4373 + 1428253114 — 147552315 + 5102:y6 — 200:1:4 — 17455;; —9662:4y2 + 5294:3313 + 269462;,4 + 4943/5 — 2671/6 + 52954;; + 130352313 — 3142:y4 + 262y5 +362:4 — 788132y2 — 689.2113 + 1773/4 = 0. The number of variables of this system is 2 with total degree 72 = 49. The optimal Bézout number is 49 with the partition {2:, y}. The mixed volume is 46 and there are 46 isolated zeros. 79 5.1.46 Parallel robot (left-arm robot) The following system is available at the Frisco test suite. The problem is to find all the possible positions of the upper platform, given the length of the arms(between the ground and the platform) of the parallel robot. Using quaternions, with the given matrix X of base points and the matrix Y of points of the platform F r - 01/2 3/23/21/32 01010—1 X: 0 —1/2 —1/21/21/2 0 ,Y= 0 0 —1 11 0 0—1—1—1—10 L010111 and the length lg = [1, 1, 0.8, 2, 2, 2], the following system is obtained: u2+v2+w2—1=0 —12b — 42 + 4c+ 4ab+ 4ac+ 4bc+ a2 + 5b62 + 13c2 + 810 + 2n + 9 + 82011 + 82610 + 8bav + 8bcv + 21122 — 6ub2 — 6uc2 + 21222 + 21)!)2 + 2’UC2 + 811202 + 8bu + 801) — 8av — 8511) + 21) = 0 8.86 — 6b + 22 + 4abu + 6 — 62b — 606 + 606 + 2.8622 + 4.86b2 + 6.8662 + 410 — 3n + 4bcw + 4211) — 4011 + 4acu + 41361) — 31122 — 3ub2 — 311C2 — va2 + Bub2 — U62 + 41062 + 4bu — 4m: + 31) = 0 —2b + 22 + 2c + 22b —10ac — 2116 + 3.522 — 2.51:2 + 1.502 + 410 — 5n + 7.5 + 42011 — 42610 + 4bcv - 511.22 — ub2 — uc2 — vaz—vb2—vc2+4wc2+4bu—4cv—4av+4bw—v=0 —4a — 4abu — 13333333336 + 1333333333211 — 4bc — 163888888922 + 0.36111111b2 — 163888888902 + 210 — 066666666711 — 4bcw — 40.11) + 80 0.361111111 + 2wb2 + 4011 -— 0.666666667ua2 — 0.666666667ub2 — 0.666666667uc2 + 1122 — 3002 + 1102 + 2m? — 35 = 0 —8b+4abu+8c—82b—Sac+8b2+862+2w— 2u+4bcw+ 42w — 2111b2 — 221222 — 4011 + 42611. + 42610 + 4bav + 4bcv — 21122 — 6ub2 — 6uc2 — 21222 + 21152 — 2vc2 + 211262 + 4511 + 4cv—4av—4bw+21:=0 where the variables are 11,12, 10, a, b,c. The number of variables of this system is 6 with total degree 2 x 35 = 486. The optimal Bézout number is 160 with the partition {11,11,112}, {0,0,0}. The mixed volume is 160 and there are 40 isolated zeros. 5.1.47 Parallel robot with 24 real roots The following system can be found in [44] and is obtained from the Frisco test suite: 625002;? + 625003;? + 625002? — 74529 = 0 625253 + 625y§ + 6252.3 — 12505:2 — 2624 = 0 1250053 +12500y§ + 12500z§ + 2500453 —- 44975313 — 10982 = 0 40000045132 + 400000371312 + 4000002122 — 400000.52 + 178837 = 0 1000000151,,4:3 + 1000009193 + 10000072124, + 1000004:3 — 1799000313 — 805427 = 0 20000005253 + 2000000312113 + 20000002223 — 20000004» + 20000053 - 3598000y3 - 1403 = 0 113800000000000.531,2,2l — 11380000000000022 31321 — 113800000000000 * 2:3y122 + 11380000000000021 y3z2 + 1138000000000002:2 * 81 3113/3 — 1138000000000004131243 -— 206888400000000232y1 + 2068884000000005533/1 + 20688840000000021312 - 206888400000000 4 431,2 - 206888400000000221y3 + 20688840000000022y3 — 20142600000000 4 $221 + 20142600000002-321 — 61907200000000y221 + 61907200000000 4 3,3,2. + 20140000000004142 — 20142600000002322 + 61907200000000 4 3,122 — 61907200000000y322 — 20142600000004-143 + 2014260000000 4 $223 — 61907200000000y123 + 61907200000000y223 - 36290716800000 4 2: 1 + 38025201600000222 + 29254884960000023 + 11809567440000y1 + 14759782200003,2 — 825269402280000y3 — 121298268960000021 — 15160047480000022 + 82585995120000023 — 19295432410527 = 0 —7776000000002:3 y2z1 + 777600000000$2y3z1 + 777600000000 4 431,122 — 777600000000213/322 — 77760000000042.4133 + 777600000000213/223 — 140901120000022y1 +140901120000043 4 y. + 1409011200000$1y2 -— 14090112000002.3112 — 1409011200000 4 2:1y3 + 14090112000004;le3 — 1065120000002221 + 1065312000000 4 4:321 — 8055936000003/221 + 805593600000y321 + 1065312000000 4 4,22 — 10653120000002322 + 805593600000y1 22 — 805593600000 4 3,342 — 10653120000002123 + 10653120000002223 — 805593600000 4 9123 + 80559360000017; :43 + 23585027200231 + 39841751040022 + 1586269152004;3 — 3116684240001“ -— 2680903680003/2 + 72704002800 4 93 + 41222130240041 + 35458375680022 + 30708543840023 + 282499646407 = 0 320022 + 1271 = 0. 82 Note that the coefficients need to be scaled. The number of variables of this system is 9 with total degree 26 x 32 = 576. The optimal Bézout number is 80 with the partition {201,311,21}, {202,312,22}, {2:3,y3,z3}. The mixed volume is 80 and there are 40 isolated zeros. 5.1.48 3 Torus system The following system is available at the Frisco test suite: 2:4 + 22:2y2 + 22:2z2 + y4 + 231222 + 24 — 22:3 — 2223/2 — 24:22 + :52 + 133333333333,2 + 1333333333342 2 0 2:4 + 22‘2y2 + 22:22:2 + y4 + 2y222 + 24 — 22:3 — 22:22 — 22:3;2 — 22:82 — 2yzz — 223 + 2960784314222 + 5.921568627er + 3921568627312 + 296078431422 — 39215686272: — 3.9215686272: + 1.960784314 = 0 2:4 + 22:2y2 + 226222 + y4 + 231222 + Z4 —— 22:23 — 23122 — 223 + 5263157895222+5.263157895y2+2.2 = 0. The number of variables of this system is 3 with total degree 43 = 64. The optimal Bézout number is 64 with the partition {2:, y, z}. The mixed volume is 64 and there are 16 isolated zeros. 5 . 1 .49 Emulsion chemistry The variables of the following system are 11,72,713, 74: T1(7‘2+T3+7‘4) = A 83 7‘2(T1+7‘3+T4) = B T3(T1+T2+T4) = T4(T1 +7'2 +T3) = D. The number of variables of this system is 4 with total degree 24 = 16. The optimal Bézout number is 16 with the partition {13, 73,13, 72,}. The mixed volume is 8 and there are 8 isolated zeros. 5.1.50 Commodities market The variables of the following system are 3, t, u, v, w, x, y, z: u+s—2A = 0 v+t—ZB = 0 v—u—t-l-s = 0 vz—ty—ucv+sw = 0 vz+ty+uas+sw—206 == 0 —vz—ty+ux+sw—2cd = 0 —su(z+y)+st(z+at)+uv(y+w) —tv(x+w) —2p0(u—t)(v—s) = 0 u(z—w)+t(w—z)+s(y—$)+v(a:—y)—ro(u—t)(v—s) = O. The number of variables of this system is 8 with total degree 24 x 3 = 48. The optimal Bézout number is 7 with the partition {3, t, u, v}, {u}, z, y, z}. The mixed volume 5 7. There are 6 isolated zeros. 1n. 84 5. 1.51 Raksanyi system The following system arises from Systems theory with rational function coefficients and is available at the Frisco test suite: t+(v—a.) = 0 x+y+z+t—(u+w+a) = 0 xz+$t+yz+zt—(uw—ua—wa) = 0 :rzt—uwa = 0 where the variables are .23, y, z, t. The number of variables of this system is 4 with total degree 3 x 2 = 6. The optimal Bézout number is 3 with the partition {3, y}, {z}, {t}. The mixed volume is 3 and there are 3 isolated zeros. 5. 1.52 Runge-Kunga This system arises in an application of the Runge—Kutta space. The problem is to construct a modified version of an explicit 3 stage Runge-Kutta method with order 4 W b1+b2+b3—(a—,B)=O 1 l b262+b3C3—(§+§,B+,B2—afi)=0 b2c3+b3c§— (cg—+732) — $73432 —a3) :0 5303262 - (04% + $6 + 62) — 36 — 62 — H3) = 0 1 l 5 3 b263+b363‘(1+1fl+ §fl2+§fi3+fi4—a(fi+fl3)) =0 85 1 3 7 3 1 1 b30303262 - (g + g3 + 152 + 533 + ,6“ — a(§fi + 5,62 + ’83)) = 0 1 1 7 3 2 2_ _2 _3 4_ _ 2 3 : b3a32c2 (12+12fi+6fl+2B +fi 0(3/3+fl +fi)) 0 i l 22 Es _ 1 2 3_ 24+24fl+12fl +26 +734 0(33+fi +3)_0 where the variables are ()1, b2, b3, c2, c3, a32, a, 6. The number of variables of this system is 8 with total degree 44 x 32 x 2 = 4608. The optimal Bézout number is 1361 with the partition {b1}, {b2, b3, (1}, {[3}, {c2, C3}, {032}. The mixed volume is 24 and there are 5 isolated zeros. 5.1.53 Solubility of silver chloride in water The problem is to find the concentrations of all species in a saturated silver chloride solution [32]. After reduction, the following system is generated: 4 3 3 01231 + (1211:1125 + (131:1 + 0411)] + 05 = 0 311171153 + ,6ng + 33 = 0. The number of variables of this system is 2 with total degree 4 x 3 = 12. The optimal Bézout number is 9 with the partition {:51},{:1:3}. The mixed volume is 9. With the given coefficients, there are 9 isolated zeros. 86 Table 5.7. Coefficients for the butler’s problem coefficients a1 1.069D-04 02 21304 03 1.000 a4 -1.8D-10 a5 -1.283D-24 61 2D16 ,82 1D14 [1‘3 -1.000 5.1.54 Enumerative geometry(Hypersurface schubert condi- tions) This system is available at the Frisco test suite. The problem is to find those p—plane which intersect m * p given m—planes in 0"” which osculate the rational normal curve. For m = 2,19 = 3, F(81)= =F(86)=0 where 31, . . . , 36 are six distinct real numbers, and 1 0 a b c s 1 e f F(s)=det 32 23 1 0 OOQQ 33 3s2 01 34433001 87 Table 5.8. Characteristics of systems that arise in the Schubert Calculus m p totdeg mdeg M(Q) N(Q) 2 2 16 6 4 2 2 3 64 20 17 5 2 4 256 70 66 14 2 5 1024 252 247 42 The first two columns of the matrix give the 2-planes in R5 which osculate the rational normal curve. The last three columns are local coordinates on the Grassmanian of 3-planes in R5. The system F(s) = 0 is given by: 1 — 23,6 — 3sff — 43,39 + sfa. + 2s§b + 3sgc + sfaf — sfeb + 23fag — 2sf’ec+3?bg — sfcf = 0, i=1,...,6 where the variables are a, b, c, d, e, f. The number of variables of this system is 6 with total degree 26 = 64. The optimal Bézout number is 20 with the partition {(1, b, c}, {(1, e, f}. The mixed volume is 17 and there are 5 isolated zeros. Table 5.8 summarizes the results for different values of m and p. Here totdeg denotes the total degree of the system, mdeg its optimal Bézout number M(Q) its mixed volume and N (Q) the total number of isolated zeros. 88 5.2 Summary Table 5.9 and Table 5.10 summarize the various characteristics of the 54 polyno- mial systems presented: For each system, n denotes the number of variables, totdeg the total degree, mdeg the optimal multi-homogeneous Bézout number, M (Q) the mixed volume and N (Q), the total number of isolated zeros. 5.3 Conclusions Our solver finds all isolated zeros of the above polynomial systems to satisfactory accuracy and speed. As an observation, these systems are characterized by substan- tially low mixed volume M(Q), compared to totdeg, their total degree. By Theorem 2.1.2, the mixed volume M(Q) of a given polynomial system is an upper bound on N(Q), the total number of isolated zeros in C". A great majority of the polynomial systems presented here actually have M(Q) number of isolated zeros. Of both theo- retical as well as practical interest is the fact that the numbers M(Q) are either less than or equal to the optimal multi-homogeneous Bézout number, mdeg. We would like to work towards a possible theoretical explanation in the future. For those sys- tems with a discrepancy between M(Q) and N (Q), we wish to study and explore the structure of the systems. We hope to derive a method that respect these structures and requires computational efforts proportional to the actual number of isolated zeros of these systems. Overall, the generality of the current solver should establish itself as the method of choice for systems of moderate size. 89 Table 5.9. Characteristics of the polynomial systems I no. name description 77. totdeg mdeg M (Q) N (Q) 1 puma robot manipulator PUMA 8 128 16 16 16 2 romin robot manipulator ROMIN 6 32 16 4 4 3 LV Lotka—Volterra System 4 81 81 73 73 4 sym4 symmetrized four-bar 4 256 96 80 36 5 ninept nine-point problem 8 78 645120 83977 4326 6 chemeqm chemical equilibrium 5 108 56 16 16 7 lumped lumped-parameter 4 16 8 7 4 8 heart heart-dipole 8 576 193 121 4 9 cycmol cyclic molecules 3 64 16 16 16 10 camera camera motion 6 64 20 20 20 11 elect electrical network 4 16 6 6 6 12 vib vibrating systems 6 243 10 10 10 13 6R 6R inverse position 8 256 96 64 32 14 6R2 6R inverse position 11 1024 320 288 16 15 quad quadrature formula 5 120 10 10 5 16 wood the wood function 4 36 25 9 9 17 ec electrochemistry problem 4 60 52 18 15 18 i1 benchmark i1 10 59049 452 66 50 19 mdi integration formula 9 36000 8852 136 16 20 AHW The system of A. H. Wright 5 32 32 32 32 21 R5 The system called Reimer5 5 720 720 720 144 22 butcher Butcher’s problem 7 4608 1361 24 5 23 viralg Virasoro algebras 8 256 256 200 200 24 cycn the cyclic n-roots problem 7 5040 5040 924 924 25 comb combustion chemistry 10 96 44 16 16 26 econ economic modelling 8 1458 256 64 64 27 neu neurophysiology 6 1024 216 20 8 90 Table 5.10. Characteristics of the polynomial systems II no. name description 12 totdeg mdeg M (Q) N (Q) 28 speer the system of E. R. Speer 4 625 384 96 43 29 sol solotarev 4 36 10 6 6 30 trinks number theory 6 24 24 10 10 31 galois 391 from Galois theory 8 16 10 10 10 32 rediff3 reaction-diffusion problem 3 8 8 7 7 33 lorentz lorentz attractor 4 16 14 12 11 34 bif a bifurcation problem 3 126 32 16 16 35 D1 benchmark D1 12 4068 320 192 48 36 capr caprasse’s system 4 144 62 48 48 37 am arnborg7 3 120 48 20 20 38 rose economic equilibrium model 3 216 144 136 136 39 moe Moeller4 6 8 8 7 7 40 kat Katsura 6 32 32 32 32 41 cohn2 cohn2 4 900 450 124 18 42 CN Cassou—Noggues 4 1344 368 24 16 43 dessinI dessin d’enfant I 8 324 108 46 46 44 dessinII dessin d’enfant II 10 256 126 42 42 45 sendra sendra 2 49 49 46 46 46 rbpl parallel robot(left-arm) 6 486 160 160 40 47 rbpl24 parallel robot 9 576 80 80 40 48 3torus torus 3 64 64 64 16 49 emulchem emulsion chemistry 4 16 16 8 8 50 commod commodities market 8 48 7 7 6 51 raksanyi systems theory 4 6 3 3 3 52 RK runge-kutta 8 4608 1361 24 5 53 butler solubility 2 12 9 9 9 54 schubert Schubert conditions 10 1024 252 247 42 BIBLIOGRAPHY [1] [2] [3] [4] [6] [7] [8] BIBLIOGRAPHY E. L. Allgower and K. Georg, Numerical Continuation Methods, Springer serives in Comp. Math., vol 13 (1990). E. L. Allgower and K. Georg, Continuation and path following, Acta Numerica, 1(64) (1993). D. N. Bernshtein, The number of roots of a system of equations, Functional Anal. App., 9(3) (1975), 183-185. Translated from Funktsional Anal. i Pm’lozhen, 9(3) (1975) 1-4. G. Bjork and R. Froberg, A faster way to count the solutions of inhomogenenous systems of algebraic equations, with applications to cyclic n-roots, J. Symbolic Comp. 12(3) (1991) 329-336. V. Balakotaiah, D. Luss and B. L. Keyfitz, Steady state multiplicity analysis of lumped-parameter described by a set of algebraic equations, Chem. Engrg. Comm., 36 (1985) 121-147. J. C. Butcher, An application of the Runge—Kutta space, BIT, 24, (1984), 425- 440. J. Canny and J. M. Rojas, An optimal condition for determining the exact num- ber of roots of a polynomial system, Proc. of the 1991 Int. Symp. on Symb. and Alg. Comp, ACM, 96—101. S. N. Chow, J. Mallet-Paret and J. Yorke, A homotopy method for locating all zeros of a system of polynomials, Functional differential equations and approxi- mations of fixed points, Lecture Notes in Math. 730 (1979) 77-88. 91 92 [9] F. J. Drexler, A homotopy method for the calculation of zeros of zero-dimensioal polynomial ideas, Continuation Methods, Academic, New York (1978) 69-93 [10] I. Z. Emiris, Sparse Elimination and Applications in Kinematics, PhD thesis, Dept. of electrical engrg. and comp. sci., University of California, Berkeley, 1984. [11] I. Z. Emiris and J. F. Canny, Efficient incremental algorithm for the sparse resultant and the mixed volume, J. Sym. Comp., 20(2), 117—149, August 1995. [12] O. D. Faugeras and S. Maybank, Motion from point matches: multiplicity of solutions, Int. J. Comp. Vision, 4 (1990) 225-246. [13] I. M. Gel’fand, M. M. Kapranov, A. V. Zelevinskii, Discriminants, resultants and multidimensional determinants (1994). [14] M. J. Gonzalez—Lopez and T. Recio, The ROMIN inverse geometric model and the dynamic evaluation method, Computer Algebra in Industry, (1993) 117-142. [15] C. B. Garcia and W. I. Zangwill, Finding all solutions to polynomial systems and other systems of equations, Math. Programming, 16 (1979) 159-176. [16] B. Huber and B. Sturmfels, A Polyhedral Method for solving sparse polynomial systems, Math. Comp., 64(212) (1995) 1541-1555. [17] H. Hong and V. Stahl, Safe starting region by fixed points and tightening, Com- puting, 53(3—4), 322-335, 1995. [18] Sandie T. Jones, Locating safe starting region for iterative methods, a heuristic algorithm, Proc. of the Int. Symp. on Int. Math. , May 27-31, 1980, 377-386. [19] R. B. Kearfott, Some tests of generalized bisection, ACM Trans. on Math. Soft, 13(13) (1987) 197-220. ' [20] A. G. Khovanskii, Newton polyhedra and the genus of complete intersections, Functional Anal. Appl, 12(1), 38-46. Translated from Funktsional Anal. i P1ilozhen., 12(1), 51-61. [21] A. G. Kushnirenko, Newton Polytopes and the Bézout Theorem, Functional Anal. Appl, 10(3), 233-235. Translated from Funktsional Anal. i Prilozhen., 10(3), 82—83. 93 [22] C. W. Lee, Regular triangulations of convex polytopes, Applied Geometry and Descrete Mathematics, vol. 4 of DIMA CS Series (1991) 443-456. [23] Lancaster, Lambda-matrices and vibrating systems, (1967) 116-142. [24] T. Y. Li, On Chow, Mallet-Paret, and Yorke Homotopy for solving systems of polynomials, Bull. Inst. of Math., Academica Sinica, 11 (1983), 433-437. [25] T. Y. Li and T. Sauer, Regularity results for solving systems of polynomials by homotopy method, Num. Math, 50(1987) 283-289. [26] T. Y. Li, T. Sauer and J. A. Yorke, Numerical solution of a class of deficient polynomial systems, SIAM J. Num. Anal, 24(2) (1987) 435-451. [27] T. Y. Li, T. Sauer and J. A. Yorke, The cheater’s homotopy: an efficient pro- cedure for solving systems of polynomial equations, SIAM J. Num. Anal, 26 (1989), 1241-1251. [28] T. Y. Li and X. Wang, Solving deficient polynomial systems with homotopies which keep the subschemes at infinity invariant, Math. Comp., 56(194) (1991) 693-710. [29] T. Y. Li and Xiaoshen Wang, The BKK root count in C", Math. Comp., 65 (1996), 1477-1484. [30] T. Y. Li, Numerical solution of multivariate polynomial systems by homotopy continuation methods, ACTA Numerica, (1997) 399-436. [31] E. Lorenz, The local structure of a chaotic attractor in four dimensions, Physica, 13D, (1984) 90-104. [32] K. Meintjes, A methodology for solving chemical equilibrium systems, Appl. Math. Comp., 22 (1987) 333-361. [33] K. Meintjes and A. P. Morgan, Chemical equilibrium systems as numerical test problems, ACM Trans. Math. Softw, 16(2) (1990) 143-151. [34] R. E. Moore and S. T. Jones, Safe starting region for iterative methods, SIAM J. Num. Anal, 416 (1977) 1051-1065. 94 [35] J. J. Moré, B. S. Garbow and K. E. Hillstrom, Testing unconstrained optimiza- tion software, ACM Trans. Math. Soft. 7(1) (1981) 17-41. [36] Ramon E. Moore, Methods and applications of interval analysis, Chapter 6, p.64, SIAM Philadelphia, 1979. [37] A. Morgan adn V. Shapiro, Box-bisection for solving second-degree systems and the problem of clustering, ACM Trans. Math. Soft, 13(2) (1987) 152-167. [38] A. Morgan and A. Sommese, A homotopy for solving general polynomial systems that respects m—homogeneous structures, Appl. Math. Comp. 24 (1987) 101-113. [39] A. Morgan and A. Sommese, Coefficient-parameter polynomial continuation, Appl. Math. Comp. 29 (1989) 123-160. [40] A. Morgan and A. Sommese, Computing all solutions to polynomial system using homotopy continuation, Appl. Math. Comp. 24(2) (1987) 115-138. [41] A. P. Morgan and C. W. Wampler, Solving a planar four-bar design problem using continuation, ASME J. of Mech. Design, 112 (1990) 544-550. [42] A. Morgan, Solving polynomial systems using continuation for engineering and scientific problems, (1987). [43] A. P. Morgan, Polynomial continuation and its relationship to the symbolic re- duction of polynomial systems, Workshop on the integration of numerical and symbolic computing methods, Saratoga Springs, New York, 1991, Academic Press. [44] B. Mourrain, The 40 generic positions of a parallel robot, [SSA C ’93, ACM Press, 173-182, Kiev(Ukraine), July 1993. [45] C. V. Nelsen and B. C. Hodgkin, Determination of magnitudes, directions, and locations of two independent dipoles in a circular conducting region from bound- ary potential measurememts, IEEE Trans. Biomed. Engrg., BME—28(12) (1981) 817-823. [46] V. W. Noonburg, A neural network modeled by an adaptive Lotka-Volterra sys- tem, SIAM J. Appl. Math, 49(6) (1989) 1779-1792. 95 [47] J. M. Rojas, A convex geometric approach to counting the roots of a polynomial system, Theo. Comp. Sci., 133 105-140. [48] Schneider, Convex bodies: The Brunn-Minkowski Theorey, Cambridge, 1993. [49] I. R. Shafarevich, Basic Algebraic Geometry, Springer-Verlag, (1977) [50] S. M. Selby, Ed., CRC Standard Mathematical Tables, The Chemical Rubber Company, Cleveland, Ohio (1977). [51] S. Schrans and W. Troost, Generalized Virasoro constructions for SU(3), Nuclear Phys. B, 345(2—3) (1990) 584-606. [52] W. Sweldens, The construction and application of wavelets in numerical analysis, PhD thesis, K. U. Leuven (Belgium), 1984. [53] L. W. Tsai and A. P. Morgan, Solving the kinematics of the most general six- and five-degree-of-freedom manipulators by continuation methods, ASME J. of Mech., Transmission, and Automation in Design 107 (1985) 189-200. [54] J. Verschelde, Homotopy continuation methods for solving polynomial systems, Ph.D. thesis, Dept. of Comp. Sci., K. U. Leuven (Belgium), 1996. [55] C. W. Wampler, Bézout number calculations for multi-homogeneous polynomial systems, Appl. Math. Comp., 51, (1992) 143-157. [56] C. W. Wampler, An efficient start system for multi-homogeneous polynomial continuation, Nam. Math, 66 (1994), 517-523. [57] C. W. Wampler and A. P. Morgan, Solving the 6R inverse position problem using a generic-case solution methodology, Mech. Mach. Theory, 26(1) (1991) 91-106. [58] C. W. Wampler, A. P. Morgan and A. J. Sommese, Complete solution of the nine-point path synthesis problem for four-bar linkages, ASME J. of Mechanical Design, 114(1) (1992) 153-159. [59] C. W. Wampler, A. P. Morgan and A. J. Sommese, Numerical continuation methods for solving polynomial systems arising in kinematics, J. Mech. Design, 112 (1990) 59—68. 96 [60] L. T. Watson, Globally convergent homotopy methods: a tutorial, Appl. Math. Comp., 31 (1989) 369-396. [61] A. H. Wright, Finding all solutions to a system of polynomial systems, Math. Comp., 44(169) (1985) 125-133. "l1111]]111111“