 

PLACE IN RETURN BOX to remove this checkout from your record.
TO AVOID FINES return on or before date due.
MAY BE RECALLED with earlier due date if requested.

 

DATE DUE DATE DUE DATE DUE

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

5/08 KIProj/AccaPreleIRCIDatoDuejndd

 

 

MIXED VOLUME AND TOTAL DEGREE

By

Ying Zhang

A DISSERTATION

Submitted to
Michigan State University
in partial fulﬁllment of the requirements
for the degree of

DOCTOR OF PHILOSOPHY

Department of Mathematics

2008

ABSTRACT

MIXED VOLUME AND TOTAL DEGREE
By

Ying Zhang

This thesis focuses on the study of solving several extensible benchmark polynomial
systems by homotopy continuation methods. By establishing the relationship between their
mixed volume and total degree, we ﬁnd that for most of those systems the difference between
their mixed volume and total degree is very minimal. Consequently, those systems should
be solved by the classical linear homotopy method rather than the polyhedral homotopy
method, although in general the polyhedral homotopy method is the typical choice for
solving sparse systems. Furthermore, by restricting to the classical linear homotopy on
solving those systems, we may take the special structure of the systems into account for
solving the systems efficiently. This precious aspect of the classical linear homotopy does

not seem to exist in the polyhedral homotopy method.

To my sons, Ray and Ryan.

iii

ACKNOWLEDGMENTS

This thesis could not be ﬁnished without the help and support of many people who are
gratefully acknowledged here.

First and foremost, I’m honored to express my deepest gratitude to my dedicated thesis
advisor, Professor Tien-Yien Li, with whose guidance I could have worked out this thesis.
He has offered me valuable ideas and suggestions with his profound knowledge in math-
ematics and rich research experience. His patience and kindness are greatly appreciated.
Besides, he is always willing to discuss with me anytime he is available. I have learned a
lot from him not only about doing research, but also his positive attitude to life. I’m very
much obliged to his efforts of helping me complete the dissertation.

I’m also extremely grateful to Professor Gang Bao for his support and help when I was
at Michigan State University. What’s more, I would like to thank the members of my thesis
committee, Professor Andrew Christlieb, Professor Di Liu, Professor Jianliang Qian, and
Professor Changyi Wang for the time they spent on serving on my committee.

Thanks are also due to my fellow graduate students Tianran Chen, Tsung-Lin Lee,
Rostam Sabeti, Chih-Hsiung Tsai, and Alice Wang for years of discussion and collaboration.
Special thanks go to Chih-Hsiung Tsai for his time and kindness on helping me with the
numerical results in this thesis.

My deepest appreciation goes to my wonderful husband, Peijun Li, and my mom for

their unselﬁsh love, enduring patience, continued support and encouragement.

iv

TABLE OF CONTENTS

LIST OF FIGURES
LIST OF TABLES
Introduction

1 The polyhedral homotopy
1.1 The Bernshtein theory .............................
1.2 The polyhedral homotopy ...........................

2 Katsura—n system
2.1 Katsura-n system ................................
2.2 Numerical results ................................

3 Reimer-n system
3.1 Reimer-n system ................................
3.2 Numerical results ................................

4 Noon-n system
4.1 Noon-n system .................................
4.2 A special start system for Noon-n system ..................
4.3 Numerical results ................................

5 Generalized eigenvalue problem
5.1 Generalized eigenvalue problem ........................
5.2 A special start system for generalized eigenvalue problem ..........

BIBLIOGRAPHY

vi

vii

10

17
17
25

28
28
32

34
34
39
47

50
50
59

63

LIST OF FIGURES

5.1 The convex hull of S for n = 3.

uuuuuuuuuuuuuuuuuuuuuuuu

vi

2.1

3.1

4.1
4.2

5.1

LIST OF TABLES

Comparison of the classical linear homotOpy with the typical start system
and the polyhedral homotopy in solving Katsura-n systems. ........

Comparison of the classical linear homotopy with the typical start system
and the polyhedral homotopy in solving Reimer-n systems ..........

Number of linear subsystems for different grouping of constant terms. . . .
Comparison of the polyhedral homotopy and the classical linear homotopy
with different start systems in solving Noon-n systems. ...........

The parallel speed-up for solving generalized eigenvalue problem A2: = A81:
and eigenvalue problem Ax = A3: with n = 100 and n = 200. .......

vii

27

33

42

49

Introduction

Polynomial systems arise very frequently in many ﬁelds of science and engineering [7], such
as formula construction, geometric intersection problems, inverse kinematics, power flow
problems with PQ-speciﬁed bases, computation of equilibrium states, etc. In 1977, Garcia
and Zangwill [10] and Drexler [9] independently presented theorems, which suggested that
homotopy continuation methods could be used to ﬁnd the full set of isolated zeros of a
polynomial system numerically. During the last three decades these methods have been
developed into a reliable and efficient numerical algorithm for approximating all isolated
zeros of polynomial systems.

Let P(:r) = 0 be a system of n polynomial equations with n unknowns. Denoting

P = (191, . . . ,pn) and 2: = (:51, . . . ,xn), we want to ﬁnd all isolated solutions of

p1(x11"‘,xn) : 0

 

\ pn($1,--.,xn)=0.

The classical homotopy continuation method [2, 3] for solving P(:r) = 0 is to deﬁne a

trivial system 62(3) 2 ((11 (11:), . . . , qn (13)) and then follow the solution curves in the real

variable t from t = 0 to t = 1, which make up the solution set of
H(;r, t) = (1 — t)rQ(:c) + tP(:r) = O with generic 7‘ E C \ {0}.

More precisely, all the isolated solutions of P(:z:) = 0 can be found if the system
Q(:r) = 0, known as the start system, is chosen properly to satisfy the following three

properties:
0 Property 0. The solutions of the start system Q(:z:) = O are known;

0 Property 1. The solution set of H (2:, t) = 0 for O S t S 1 consists of a ﬁnite number

of smooth paths, and each of them can be parameterized by t in [0,1);

0 Property 2. Every isolated solution of H(a:, 1) = P(a:) = O can be reached by some
path originating at t = 0, that is, the path starts from a solution of the start system

H(a:,0) = Q(:r) = O.

A typical choice of a start system Q(a:) = 0 satisfying Property 0—2 is

d
gl(zla' .. awn) = (1111311 _ b1

qn(:rl, . . . ,3”) = anxg” — bn

where d1, . . . ,dn are the degrees of polynomials p1(:r), . . . , pn(x), respectively, and
aj, bj, j = 1, . ..,n are random complex numbers [6, 18, 23, 29, 37, 38]. The solutions
of such a start system Q(:r) = 0 can be explicitly obtained and the total number of so-
lutions is d = d1 x x dn, which is known as the total degree or the Bézout number of
the original polynomial system P(:L') = 0 [33]. We may then ﬁnd all the isolated solutions

of P(:r) = 0 by following the total degree number of paths originating from solutions of

the start system Q(r) = 0. But, a great majority of the polynomial systems arising in
applications have fewer than, and in some cases only a small fraction of d = d1 x - - - x d,
isolated zeros. We call such a system deﬁcient. In this case, many of the d1 x x dn
paths will diverge to inﬁnity as t —> 1, and those paths become extraneous, causing highly
wasteful computation.

In the middle of 1990’s, a major computational breakthrough emerged in solving de-
ﬁcient polynomial systems efﬁciently by the homotopy continuation method. The new
method, called the polyhedral homotopy method [13], takes a great advantage of the combi-
natorial root count in the Bernshtein’s theory [4], which generally provides a much tighter
bound, called mixed volume, for the number of isolated zeros of a polynomial system in the
algebraic tori (0‘)" = (C\ {0})". When the polyhedral homotopy method is employed to
solve a polynomial system, the number of homotopy paths that need to be traced agrees
with twice of the mixed volume of the polynomial system. As an important consequence,
when the mixed volume of a polynomial system is far less than its total degree, then solving
the systems by the polyhedral homotopy method will greatly reduce the extraneous paths
and thereby considerably limit the wasteful computations.

However, in the core of the polyhedral homotopy continuation method, there is a some-
times costly computation, namely the mixed cell computation, which provides the critically
important start system that one can handle for the polyhedral homotOpy. Indeed, this
mixed cell computation can become very costly for large polynomial systems. Therefore,
before the polyhedral homotopy is used to solve the polynomial system at the expense of
the sometimes costly mixed cell computations, a prior knowledge on the comparison of
the total degree of the system and its mixed volume is highly desirable. If a substantial
difference between these two numbers of the system is absent, then, of course, the system

should be solved by the classical linear homotopy rather than the polyhedral homotOpy.

While it has been largely admitted for grant that for most of the sparse polynomial sys-
tems their mixed volume is far less than their total degree, in this thesis we analyze several
extensible benchmark polynomial systems in the opposite. By establishing the relationship
between their mixed volume and total degree, we ﬁnd that for most of those systems the
difference between their mixed volume and total degree is very minimal. Consequently,
those systems should be solved by the classical linear homotopy method. Furthermore, by
restricting to the classical linear homotopy on solving those systems, we may take the spe—
cial structure of the systems into account for solving the systems efﬁciently. This precious
aspect of the classical linear homotopy does not seem to exist in the polyhedral homotopy
method.

The thesis is organized as follows. In Chapter 1, the Bernshtein theorem is introduced
along with its application on the polyhedral homotopy continuation method for solving
polynomial systems, including mixed volume and mixed cell computations. In Chapter
2, 3 and 4, we study the extensible benchmark systems Katsura-n [35], Reimer—n [35]
and Noon-n [31] respectively. It is shown that for each of those systems the difference
between the mixed volume of the system and its total degree is very slim, if not zero.
Therefore the polyhedral homotopy continuation method, widely considered the state of
the art, is inappropriate for solving those systems. They should be solved by the classical
linear homotopy method. Birthermore, when the classical linear homotopy is used to solve
the Noon-n systems in Chapter 4, particularly illuminating is the marvelous speed-ups by
choosing proper start system to recognize the symmetry structure of the system.

In Chapter 5, we study the generalized eigenvalue problem An: = ABx, where A and
B are n x n matrices. When this problem is considered as a polynomial system, it contains
n equations in n + 1 variables. With an appended linear equation, the mixed volume of

the resulting system is shown to be n, that is far less than its total degree 2". Nonetheless,

from the obvious m—homogeneous structure of the system, proper start systems with n
isolated solutions are always available in the classical linear homotopy. In this situation, the
employment of the polyhedral homotopy method for solving this system is still unnecessary
so that the mixed cell computations can be avoided.

It is commonly known that very efﬁcient algorithms for matrix eigenvalue problems,
QR algorithm for Ax = Am and QZ algorithm for A2: = ABx, have been implemented
and asserted in the software package LAPACK [16]. However, as the size of the matrix
becomes larger, more computing resources are required. And a natural way to allocate
extra computing resources efﬁciently is to perform independent tasks simultaneously in
parallel. Since each isolated zero of a polynomial system is computed independently of all
the others in the homotopy continuation method, it provides a natural environment for
the parallelization. In this regard, solving very large algebraic eigenvalue problems by the

homotopy continuation method in parallel offers a great perspective in contrast to highly

serial QR or QZ algorithms.

CHAPTER 1

The polyhedral homotopy

1.1 The Bernshtel’n theory

Let P(:1:) = (p1(:r),...,pn(x)) E C[:I:] be a given polynomial system, where a: =

1

(3:1, ...,xn). Denoting :13“ = 23‘; ”.233,” with a = (a1, . . . ,an), write

pl (:13) = ZaESI diam“

191103) : ZaESn 4mm“

where 5'1, . . .,Sn are ﬁxed subsets of N" with cardinalities kj = #S,- and 030 E C“ =
C \ {O} for a E Sj,j = 1,. . . ,n. Here 53- is called the support of gay-(:13) and denoted by
supp(pj). Its convex hull 623- = conv(SJ-) in R" is called the Newton polytope of pj and
S = ($1,. . . ,Sn) is the support of P(2:), denoted by supp(P). For nonnegative variables
A1,...,/\n and the Newton polytopes Q_,- of p, for j 2 1,. ..,n, let A1Q1+-~+ AnQn

be the Minkowski sum of A1Q1, . . . , AnQn, i.e.,

A1Q1+'”+’\nQn={’\17'1+"'+/\n7‘n37‘jEerj=1I~wnl~

It can be shown that the n—dimensional volume, denoted Vol", of the polytope A1Q1 +
+ AnQn is a homogeneous polynomial of degree n in A1, . . . , An, and the coefﬁcient
of the term Al x - -- x An in this homogeneous polynomial is called the mixed volume of
the polytOpes Q1, . . . , Qn, denoted M(Q1, . . . , Q"), or the mixed volume of the supports
31,. . .,Sn, denoted M(Sl, . . .,Sn). Sometimes, it is called the mixed volume of P(rr)
when no ambiguities exist.

The system (1.1.1) can be embedded into the system P(c, 1:) = (p1(c, 2:), . . ., pn(c, 22)),

where

291(6) 113) = ZaESI cl,a$a

P(c,:r) = 5 (1.1.2)

19710333) = ZaESn 92.0930

and the coefficients on with a E 5-, j = 1,. . .,n, are taken to be a set of M = k1 +
H ° + kn variables. Namely, the system P(z) in (1.1.1) is considered as a system in (1.1.2)

corresponding to a set of speciﬁed values of coefﬁcients c* = (c; a) or P(az) = P(c“, :13).

Lemma 1.1.1. [12] For polynomial systems P(c, :13) in (1.1.2), there exists a polynomial
system C(c) 2 (91(0),. ..,gn(c)) in the variables c = (cjﬂ) for a E 33- and j = 1,. . .,n
such that for those coeﬂ‘icients E 2 (035,0) for which C(E) aé 0, the root count in (C*)" of
the corresponding polynomial systems in (1.1.2) is a ﬁxed number, and the root count in

(C*)" of any other polynomial systems in (1.1.2) is bounded above by this number.

Remark 1.1.1. Since the zeros of the polynomial system C(c) in Lemma 1.1.1 form
an algebraic set with dimension smaller than M, its complement is Open and dense with
full measure in CM. Therefore, with probability one, G(c*) aé 0 for randomly chosen

. ,,, _ M . . .
coeﬁ‘iczents c — (cia) E C . Hence, polynomial systems P(c*,a:) in (1.1.2) with C(c") 75

0 are said to be “ in general position”.

Theorem 1.1.1. (Bernshtei’n) [4] The number of isolated zeros in (C*)”, counting multi-
plicities, of a polynomial system P(x) = (p1(:r), . . . ,pn(x)) with support 5 = (5'1, . . . ,5”)
is bounded above by the mixed volume M(Sl, . . . , Sn). When P(z) is in general position,

it has exactly M(Sl, . . . , Sn) isolated zeros in (C*)”.

In [5], this root count was nicknamed as BKK bound after its inventors, Bernshtein
[4], Kushnirenko [15] and Khovanskii [14]. In general, it provides a much tighter bound
compared to variant Bézout bounds [30, 33]. An apparent limitation of the theorem is that
it only counts the isolated zeros of polynomial system in (C*)" rather than all the isolated
zeros in the affine space C”. For the purpose of ﬁnding all the isolated zeros of a polynomial
system in C", a generalized version of the assertion in the theorem which counts the roots
in C" is strongly desirable. This problem was ﬁrst attempted in [32] by introducing the
notion of the shadowed sets and a bound for the root count in C" was obtained. Later, a

signiﬁcantly much tighter bound was discovered in the following theorem.

Theorem 1.1.2. [27] The root count in C" of a polynomial system P(x) =
(p1(:r),...,pn(:r:)) with supports Sj = supp(pj), j = 1,...,n, is bounded above by the

mixed volume M(31 U {0}, . . . , Sn U {0}).

Corollary 1.1.1. For polynomial system P(z) 2 (pl (11:), . . . ,pn(:r)) in (1.1.1), assume all
pj(a:)s have constant term, then the number of isolated zeros of P(x) in C" is bounded
above by the mixed volume M(Sl, . . . ,5”) of its supports S = (5'1, . . . ,5”). When P(x)
is in general position, all zeros of P(z) in C" are isolated and its total number is exactly

equal to M(Sl,...,Sn).

For a polynomial p(:c) = p(a:1, . . . ,xn) of degree d, denote the associated homogeneous

polynomial by

31 (En

~ d
a o o, — x , u I I , a
17(170, 331: mn) 0p($0 $0

The solutions of p(x) = 0 at inﬁnity are those zeros of p in projective space

I?” = {(x0,...,xn) EC"+1\(O,...,0)}/~

with x0 = 0 where the equivalent relation ~ is given by x ~ y if x = cy for some nonzero
c E C. On the other hand, zeros of p(x) in C" can be identiﬁed with zeros of p in P"
with x0 = 1.

When the system P(x) = (p1(x),...,pn(x)) in (1.1.1) is viewed in P", namely we

consider P(x0,x1, . . . ,xn) = (131 (x0,x1, . . . ,xn), . . . ,pn(x0,x1, . . .,xn)), then

Theorem 1.1.3. (Bézout) If all the zeros of P(x0,x1,...,xn) in P" are isolated, then

the number of those isolated zeros, counting multiplicities, equals to its total degree.
Together with Corollary 1.1.1, we conclude with the following proposition.

Proposition 1.1.1. For polynomial system P(x) 2 (p1 (x), . . . ,pn(x)) in general position
in which all pj (x)s have constant term, assume the zeros of P(x) at inﬁnity are all isolated,

then

Total degree of P(x) = Mixed volume of P(x) + number of isolated zeros of P(x)

at inﬁnity.

1.2 The polyhedral homotopy

In light of Theorem 1.1.2 given in the above section, to ﬁnd all isolated zeros of polynomial
system P(x) = (p1(x), . . . ,pn(x)) in C” with support S = (51, . . . ,Sn), we ﬁrst add the
monomial x0(= 1) to those pis which do not have constant terms. Followed by choosing co-
efﬁcients of all monomials at random, a new polynomial system Q(x) = (q1 (x), . . . , qn(x))

with support 5" = (3;, . . . , 5;), where S;- = 53- U {0} for j = 1,. . . ,n, is obtained:
_ -. a
(11(113) — 2,65; C,a1$

_ ‘a
I 0n,a1 -
aESn

qn(1') = Z

We call such a system an augmented system of P(x). Since all those coefﬁcients 53-,“ for
a E S; and j = 1, . . . ,n are randomly chosen, this system may be regarded as a system in
general position. We want to solve this system in the ﬁrst place. Afterwards, this system
will be used as the start system to solve P(x) = 0 via linear homotopy.

Let t denote a new complex variable and consider the polynomial system Q(x,t) =

(ch (x,t), . . . ,cjn(x,t)) in the n + 1 variables (x,t), where

@103,” = Zaesi Elﬂmatwﬂa)

(1.2.1)

— xatwn(a)
aESQ Cn,a

61161.30 .: Z

I
and the images of each 112,- : S, —> R for j = 1, . . . , n are chosen generically. For a ﬁxed

10

to, system Q(x,t) = (d1(x,t), . . .,(jn(x,t)) can be written as

. _ w (a)
(Mate) = Z I(Cl. t 1 )9?“
0651 a 0
Q(x,t0) = 5 (1.2.2)

(an,at3m(a))$a-

Qn($,t0) : E E

a 3;,
Remark 1.2.1. [17] System (1.2.2) is in general position.

Now we regard Q(x, t) = 0 as a homotopy, known as the polyhedral homotopy, deﬁned
on (C"‘)" x [0, 1] with target system Q(x, 1) = Q(x). The zero set of this homotopy is made
up of k homotopy paths x(1)(t), . . . ,x(kl (t). Since each rjj(x, t) has nonzero constant term
for all j = 1, . . . , n, it follows from a standard application of generalized Sard’s Theorem [1]
that all those homotopy paths are smooth with no bifurcations. Therefore, both Property 1
and Property 2 hold for this homotopy. However, as for Property 0, at t = 0, Q(x, 0) E 0,
so those homotopy paths can not get started because the paths originating from t = 0 can
not be identiﬁed. We deal with this problem with the following design.

The function as = (w1,. . . ,wn) with wj : S;- —+ R,j = 1,. . . ,n, may be considered as a

generic lifting on the support S, = (5/1, . . . , 8;) of Q(x), which lifts S;- to its graph

Al

A I -
Sj = {a= (a,wj(a))|ae Sj}, J = 1,...,n.

Let 0”: = (a, 1) E IR"+1 satisfy the following condition:

I I I
Condition A: There exists a collection of pairs {a1,a1} C 31,. . . ,{an,an} C 5;, where

11

I
{a1 — all, . . .,an — an} is linearly independent and for j = 1,. . .,n

(£1330 (T): (j Hé)

. .. AI . I I
(a, a) >(aj,oz),a E Sj \ {aj,aj}.

Here (., .) stands for the usual inner product in the Euclidean space. For such d = (a, 1),

where a = (0:1, . . . ,0”), let
311 =t"°1$1
yn = t—anxn-
In short, we write y = t—ax with y = (y1,. . . ,yn) or x = yta. By this transformation

and a: (a1,...,an) E N”, we have

x“ = x‘l11 nag” =(y1t0‘1)al ---(ynt°‘n)an
_ “1 an a a +~~+anan _ a (a,a)
__ y] . . . yn t 1 1 _ y t .

Consequently, cjj(x,t), for j = 1,. ..,n, of Q(x,t) in (1.2.1) becomes

qj(yta,t) : Z 5j,a yat waa)t j(a zaez’ Cja yat a.wj(a)),(a,1)) = Z Ej,ayat<&,&>
I

I
S. .
a5 J 631- aES'.7

where ti = (a, wj(a)) and 0? = (0,1).
For j: 1,...,n, let

ﬁj = min (a, Oz)
was]-

12

and consider the homotopy Ha(y, t) = (h?(y,t), . . . ,hg(y, t)) = 0 on (C*)” x [0,1], where

fig-”(v.0 = Pita-(war) = Z air/“5W“?
I

aES.

J
= 2 523a?!” 2 Ej.a?/“'5<a’o')“(33'-
aes; was;

This homotopy retains most of the properties of the homotopy Q(x, t) = 0; in particular,

both Property 1 and Property 2 remain valid and

H001. 1) = Qty. 1) = Q(y) = Q(-’I=).

. . . . .. .. J .. A ..
Moreover, With Condition A, for each 3 = 1,. . . ,n, (aj,a) z (are!) = ﬂj and (a,a) > H]-

for a E S'; \ {aj,a;-}. Thus when t = 0
I

,5 0:5 aL1+5 ,“1:0
631 Lay 1,aly Laly

hie/.0) = 2a
H “(.11. 0) =
I
hay, 0) : ZaES; an,aya : Ema/”ya" + 5n agyan = 0

which is known as the binomial system.

Proposition 1.2.1. [12] The binomial system
I
51m?!“1 + 51 a! ya1 = 0.
’ l

I
allianyan + an (Id/”ya” = 0

9

13

has

a1 -01

ka := det

 

I

(.,-..)

 

 

 

nonsingular isolated solutions in (C*)".

Proposition 1.2.2. {12/ Different a = (01,1) 6 IR"+1 that satisfy Condition A will induce
diﬁerent homotopies H “(y, t) = 0. Those diﬂerent homot0pies will reach different sets of
isolated zeros of H 0(y, 1) = Q(y) = Q(x). Moreover, those diﬂerent sets of isolated zeros

of Q(x) are disjoint from each other.

Proposition 1.2.3. [12] The root count of Q(x) = 0 in (C*)" or the mixed volume of

the augmented system of P(x) is

/m_g)
:ka 2: det
G a

I

Kan—an)

 

 

 

 

A key step in solving system Q(x) = 0 by the polyhedral homotopy method described
above is the search of all those vectors d = (a, 1) E Rn“ as well as their associated
collections of pairs COr = ({a1,a’1},. . .,{an,a:,}) which we call mixed cells with inner
normal 0: that satisfy Condition A. This is one of the most time consuming parts of the
polyhedral homotopy method and well developed algorithms for ﬁnding those mixed cells
can be found in [11, 19, 20, 22].

After all isolated solutions of Q(x) = 0 are attained, the linear homotopy
H(x, t) = (1 — t)rQ(x) + tP(x) = 0 with generic r E C*

14

will be used to solve the target system P(x) = 0 because this homotopy now satisﬁes all
the three properties [24].
We now summarize the polyhedral homotOpy procedure for solving polynomial systems.
Given polynomial system P(x) 2 (p1 (x), . . . ,pn(x)) with support 5 = (51,

...,s.,), let s’=(s[,...,s,’,) with sg=sju{0} for j=1,...,n.

0 Step 0: Initialization.

Choose polynomial system Q(x) = (q1(x),...,qn(x)) with support S, =
I I , .
(51,...,S'n) and generically chosen coefficients cjﬂ, for a E S]. and J =

1,...,n. That is,

{bi-73) = Z cj,axa, j=1,...,n.
aeSI.

J
0 Step 1: Solve Q(x) =0.

0 Step 1.1: Choose a set of real valued functions wj : S;- -» R, j =

1,...,n, their images are generic numbers.

0 Step 1.2: Find all the cells C“ = ({a1,a’1},...,{an,a:,}),j = 1,...,n
I
of SI = ($1,...,S;,) induced by w = (w1,...,wn) with ti = (a, 1) E 1R"+1
.. ,J .. Al I I
being the inner normal of ({a1,a1},...,{an,an}) in S' = (Si,...,Sn).
0 Step 1.3: For each d = ((1,1) 6 Rn“ and its associated cell 0“

obtained in Step 1.2.

15

0 Step 1.3.1 Solve the binomial system

I
_ a
€1,01ya1+cla’y 1 = 0
’ 1

I
Omanya" + 5 I ya" = 0
n,an

in (C*)", let the solution set be X3.
0 Step 1.3.2: Let ﬁj = (511361) forj = 1,...,n. Follow homotopy

paths y(t) of the polyhedral homotopy

“dial—21
06$; Cl,ay

hi"(y.t) = E
H“(y,t) =

light, t) = Zae [1%,avatié’él’ﬁ”

S

starting from the solutions in X3. Collect all the solutions

of y(l) as a subset of isolated zeros of Q(x).

0 Step 2: Solve P(x) =0.

Follow the homotopy paths of the linear homotopy
H(x,t) = (1 -— t)rQ(x) + tP(x) = O with generic r 6 C"

starting from the solutions of Q(x) = 0 obtained in Step 1 to get all
the isolated solutions of P(x) =0 at t= 1.
I
Remark 1.2.2. To ﬁnd all isolated zeros of P(x) in C", k = M(S[, . . .,Sn) homotopy

paths need to be traced in both Step 1.3 and Step 2, making it 2k homotopy paths in total.

16

CHAPTER 2

Katsura—n system

In this Chapter, we consider the Katsura-n system [35]. For this polynomial system, we
shall prove that the mixed volume of its augmented system is equal to its total degree.
Therefore, for ﬁnding all the isolated zeros of this system in C", the polyhedral homotopy
method offers no advantages as regard to minimizing the number of homotopy paths one

needs to trace.

2. 1 Katsura-n system

Katsura—n system actually contains n + 1, rather than n, variables x1, . . . ,xn+1. It has

the following forms:

17

o if n is odd, the polynomials are

2xn+1+2xn+---+2x2+x1- l
2z§+1+2xﬁ+m+2x§+x§—z1
2127113714.] + 2$n_1$n + ' ' ° +2$1$2 — LE2

2xn_1xn+1 + 2xn_2xn + - - - + 2x1x3 + x3 —[ x3

 

[ 2x2xn+1+ 2x1xn + 2x2xn_1+~-+ x H — mu;

0 if n is even, the polynomials are

2xn+1+2xn+-~+2x2+x1—1
2xi+1+2x%+---+2x§+x¥—x1
2xnxn+1+2xn_1xn +---+2x1x2 — x2

2xn_1xn+1+ 2xn_2xn + - - - + 2x1x3 + x3 -— x3

 

2xx +2xx +2xx_ +---+2xx —x.
k 2n+l 1n 2n1 313:2 n

Appending constant terms to those polynomials without them and choosing all the

coefficients randomly yield the following augmented Katsura—n system

18

o if n is odd,

 

Ci,1$n+1+ 61,2331: + - ' ' + 61.11962 + Ci,n+1131+ 01,n+2

2 .2 2 2
02,133,,“ + 02,217; + ' ' ° + C2,n$2 + 02,n+11‘1 + C2,n+2$1 + C2,n+3
C3,lznxn+1 + C3,2$n—1$n + ' ‘ ' + C3,nxl-732 + C3,n+1$2 + C3,n+2

2
C4,1$n—1$n+1 + 04,213n—2In + - ' ' + aim—1331333 + C4,n$2 + C4,n+1933 + C4,n+2

O a a 2 .
Cn.1$233n+1 + Cn.21151313n + Cn.3$2$n—1 + + Cnrﬁbi‘axli'l + Cn’ﬂlléxn + Gnu-{1’

o if n is even,

 

l

Ci,1$n+1+ Ci,2$n + ' ' ' + Ci,n$2 + Ci,n+1$1+ Ci,n+2

c 2 + 2 + - - . + 2 + 2 + +
2,1$n+1 C2,2-Tn Can-732 C2,n+1-731 C2,n+2$1 C2,n+3

C3,1$n$n+1 + 03,2In—11‘n + ° ' ' + 63.121311? + 03,n+1$2 + C3,n+2

C4,1$n—117n+1 + €4,217n—21‘n + ' - - + C4,n—lxlx3 + C4,n$% + C4,n+1$3 + C4,n+2

C71,133237n+1 +Gn,2$1$n+cn,3$2$n—l+”'+c n+2xn$n+2 +0 n+4$n+c n+6-
"’T 2 T "~T ”'T

As elaborated in the previous chapter, for the purpose of ﬁnding all isolated zeros of

polynomial system P(x) in C", rather than in (C*)", the number of paths that need to
be traced in the polyhedral homotopy method is twice the mixed volume of the augmented
system of P(x). Therefore the major difference, in terms of the number of paths one needs
to trace, in employing the classical linear homotopy or the polyhedral homotopy for solving
P(x = 0 in C" lies in the comparison of the mixed volume of the augmented system of
P(x) and its total degree. The following proposition shows that for a Katsura—n system

these two numbers are actually the same.

19

Proposition 2.1.1. Mixed volume of augmented Katsura-n system is equal to its total

degree 2".

Proof. By Proposition 1.1.1, the mixed volume of an augmented polynomial system and
its total degree will be the same if the polynomial system has no zeros at inﬁnity. We will
therefore prove the assertion of the proposition by showing there is no zeros at inﬁnity for
the augmented Katsura—n system by induction on n.

First of all, when n = 1, the augmented Katsura—l system is reduced to

0111132 + 012301 + C13 (21 1)

czlxg + (3221:? + c23x1 + 624.

The zeros of this system at inﬁnity are the zeros of its associated homogeneous polynomial

C119132 + 612931 + 613130

621.13% + 6221:? + C23x1x0 + c24x3

in P2 with x0 = 0. However, solving system

01132 + 012131 = 0

621233 + 6221‘? = 0

will result in x1 = 0 and x2 = 0. Hence, system (2.1.1) has no zero at inﬁnity.

For n = 2, augmented Katsura-2 system becomes

011953 + 012132 + 013111 + C14
C21$§ + 622213 + 6231:? + 024:6] + 625 (2-1-2)

031932333 + 032161502 + 633332 + C34

20

and its associated homogeneous polynomial is

011333 + c125102 + 013931 + 0141130
2 2 2 2
62133 + 6221132 + 023.731 + C24$1$0 + 6251130

631302113 + C321511132 + 033502330 + 03435?)-

Hence, zeros at inﬁnity of system (2.1.2) is the nonzero solutions of system

61113 + 612332 + 613561 = 0
62133 + ngxg + C2333? = 0 (2-1-3)

0312:2133 + 6321:1132 = 0.

If x3 = 0, system (2.1.3) becomes

0125132 + 013221 = 0
022.73% + C2322? = 0

C32x1x2 = 0

and the only solution of which is x1 = 0 and x2 = 0.

When x3 aé 0, let x3 = 1 in system (2.1.3), we have

W1 (1‘) = 611 + 012502 + C13131 =
1792(23) = 621 + 622% + czar? = 0 (21.4)

10203013) = 031172 + C32$1$2 = 0-

It is clear that this system has no solutions because the isolated zeros of the ﬁrst two
equations pp1(x) = 0 and pp2(x) = 0 are all in (C*)2 and those generically chosen

coefﬁcients C31 and C32 in pp3(x) will not subject to the nonzero constraint that pp3(x) =

21

0 imposed.
So the proposition is true for n = 1 and n = 2.
Now suppose the augmented Katsura—(k — 1) system has no zeros at inﬁnity. We assume

I: is even. (The proof is the same for odd I: .) Then the augmented Katsura-(k — 1) system

takes the form

C1,1931: + €1,2Ik—1+'“+ Chic—11:2 + C1,1531 + Cl,k+1

2 + 2 + , , , + 2 2
62,193,, €2,2$k_1 Oak—11:2 + 02,1631 + 02,k+1931 + C2,k+2
C3,l$k—1$k + 03,2-Tk—217k—1 + ' ' ' + Care—11311132 + 03.16132 + 03,Ic+1

04,1xk—217k + 04,233k—317k—1 + ' ' ' + Cit—2171333 + Cit—135% + 04,1433 + C4,k+1

 

Ck,1$2$k + Ck,235133k—1 + Ck,3$2-’Ek—2 + ' ' ° + 0,, k+2 513%, + Ck k 4Ik—1 + 0,, k+6-
’ 2

This system has no zeros at inﬁnity, so the system

€1,193k + Cl,2$k-1+”'+ Chic—1372 + Cum
c2,1xi + c2,2xi_1 + ' - - + 62,k_1113% + c2,kx¥
03,133k—137k + 03,293Ic—217k—1 + ° ' ° + Cat—1331162

< (2.1.6)
€4,1xk—233k + C4,2$k—3-’L‘k—1 + ' ' ' + Oak—2371353 + Cue—113%

 

Ck,1$2xk + Ck,2$1$k—1 + Ck,3$2$k—2 + ' ' ° + Ck k+2$
[ .7—

Mark?

has no nontrivial zeros. For n = k, the zeros at inﬁnity of the augmented Katsura—k system

22

01,1$k+1+ 61.21% + ' ° ' + 01,1632 + Ci,k+11‘1 + Cl,k+2

2 2 _ , 2 2 +
02,113,,“ + 62,2931, + ' + 62,1602 + C2,k+1$1 + C2,k+2~771 C2,k+3
C3,1$k-’Bk+1 + C3,2$k—1$k + ' ' ' + €3,k$1$2 + €3,k+1$2 + C3,k+2

2
C4,1$k—1$k+1 + €4,2xk—213k + W + C4,k—1x1$3 + C4,k$2 + C4,k+1$3 + C4,k+2

2
ck,1x3xk+1 + Ckagxgxk + Ck,3$l$k—l + ' ' ‘ + Ck k 413k ‘1' Ck k+6 $k_1 + Ck k+8
3 2 ,

ck+l,lx2$k+1+ Ck+122$1$k + Ck+1,3132$k_1+ . . . +

 

C k+2$k$k+2 +6 k+4$k +6. k+6
t “11—2— 2 T k+1’T “11—2—
(2.1.7)
are nontrivial zeros of
I
C1.131%“ + 01.21% + ' ' ' + 01,k$2 + Ci,k+1$1
2 2 ... 2 + 2
C211$k+1 + C2’2xk + + €2,532 C2’k+1$1
63,1$k$k+1 + 03.212431: + ' ' ' + 03.163132
2
l €4,1xk—1$k+1 + 04212—2112 + ' ' ' + Cale—1931553 + 04,1652 (2-1-8)

 

Ck,1$3$k+1 + Ck,2$2$k + Ck,31‘1$k—1 + ' ' ° + Ck k+4 132;),
’ 2 2
Ck+1,1$21‘k+1 + Ck+1,2$1$k + Ck+1,31‘2$k—1+“'+ CH1 k+2$k$k+2~
\ ’ 2 2 2

23

For xk+1 = O, the above system becomes

01,227), + - - - + chxg + cl,k+1x1
2 2 2

C2,233)c + ' ' ' + 62,1652 + C2,k+1$1

03212—1331: + ' ' ° + C3,k$1$2

2
l 64,2113k—2Ik + ' ' ' + C4,k—1$1x3 + 641932

Ck,2~"3233k + Ck,3$lxk—l + ' ' ' + Ck k+4$
*T

Mas—N

 

2

Ck+1,2$1$k + Ck+1,3$2$k—1 + ' ' ' + C k+2$k$k+2
“er T

(2.1.9)

and the ﬁrst It polynomials of system (2.1.9) have the same form as the system in (2.1.6)

with randomly chosen coefﬁcients, which has no nontrivial zeros. Consequently, system

(2.1.9) itself can not have nontrivial zeros, i.e., system (2.1.7) has no zeros at inﬁnity when

93k+1= -

For xk+1 76 0, let xk+1 = 1 in system (2.1.8) and consider

,
1919105): c1.1+ 61,2331: + ° ' ' + 011332 + €1,k+1$1

2
1910203) = 02,1 + 62,2110}?c + ° ' ° + 02,1633 + 02,k+1$1
PP3(IL‘) = 03,131: + €3,2xk-1xk + ' ' ° + C3,k$1$2

( W405) = 04,1113k—1 + €4.213k—213k + ' ° ' + Oak—1551333 + 64.1652

 

' 2

ppk($) = Ck,1$3 + Ckgxglk + Ck,3$133k_1 + . . . + ck k+4xk
’T 2

[ Ppk+1($) = Ck+1,1:132 + Ck+l,2xl$k + Ck+1,332xk—1+ . . . +

24

ck+1,Tk+2x

k$k+2-
2T

(2.1.10)

First of all, no zeros x0 = (x?,xg, . . . ,xg) of the above system can have all x3 = x3 =

= x2 = 0. Otherwise it would lead to a contradiction to pp1(x0) = 0 together with

0

pp2(x0) = 0. So, without loss of generality, we suppose x3 75 0. Now consider x an

isolated solution of k equations

PP1($1,---,Ik)=0

pp2($1,...,$k) = 0

Ppk(171.---,Ik) =0

in k variables whose coefficients are randomly chosen but then ﬁxed (and therefore all the
solutions are isolated). However, when we substitute (23?, x3, . . . ,xg) into ppk+1(x) = 0,
it imposes a nonzero constraint for the coefﬁcients Ck+1,11 . . . ’Ck+1,k 2 of ppk+1(x) since
x3 95 0. This can’t occur since those coefﬁcients are arbitrarily chosen, they do not subject
to any particular constraints. Therefore system (2.1.10) has no zeros, i.e., system (2.1.7)

has no zeros at inﬁnity when xk+1 31$ 0. Thus the assertion of the proposition is valid for

n = k. This completes the proof. C]

2.2 Numerical results

As a comparison, we solve the Katsura—n system numerically by both the classical linear
homotopy and the polyhedral homotopy, and results are listed in Table 2.1. All the com-
putations here as well as in the following chapters were carried out on a Dell PC with a
Pentium 4 CPU of 2.2GHz, 1GB of memory, and results presented are restricted to the

systems that can be solved within 12 hours of CPU time. Recall that we use the typical

25

start system Q(x) = (q1 (x), . . . ,qn(x)) where

d
(11(13): 01151311" (71,

with randomly chosen complex numbers a1, . . . ,an, b1, . . . , bn in the classical linear homo-

topy

H(x,t) = (1 — t)Q(x) + tP(x) = 0.

The speed-up ratio is the ratio of the CPU time of solving the system by the polyhedral
homotopy to that by the classical linear homotopy with the typical start system. Appar-
ently the table shows the classical linear homotopy works much better for ﬁnding all the
solutions of Katsura—n systems [21]. For instance, when n = 16 , the polyhedral homotopy
takes more than 12 hours to ﬁnd all isolated zeros of the system whereas the classical linear

homotopy only takes 16 minutes and 25 seconds.

26

 

CPU time

 

System Total Degree Speed-up ratio
Linear Polyhedral

 

 

 

 

 

 

 

Katsura— 11 2,048 113 233 2.09
Katsura— 12 4,096 263 1m22s 3.15
Katsura—13 8,192 1m06s 5m32s 5.03
Katsura— 14 16,384 2m38s 22m14s 8.44
Katsura— 15 32,768 7m03s 1h50m26s 15.66
Katsura-16 65,536 16m253 - -
Katsura- 17 131 ,072 40m483 - -

 

Katsura-18 262,144 11135m47s - -

 

Katsura- 19 524,288 3h50m488 - -

 

Katsura-20 1,048,576 8h58mOOS - -

 

 

 

 

 

 

 

Table 2.1.. Comparison of the classical linear homotopy with the typical start system and
the polyhedral homotopy in solving Katsura-n systems.

27

CHAPTER 3

Reimer-n system

Reimer—n system [35] is a polynomial system whose mixed volume is equal to its total

degree.

3. 1 Reimer-n system

The general form of Reimer-n system is

22% — 21:3 + - - - + (—1)n+1223, — 1

2251* - 21:53 + - - - + (—1)"+12x§, — 1
(3.1.1)

221.",1+1 — 223+1+-~+(—1)"+12xg+1 — 1.

Since polynomials in the system all have constant term, its augmented system will

28

consist of the same monomials with generically chosen coefﬁcients:

C1133? + C1233 + ' ' ' + 617,321+ Cln+1

021:1)? + 022.73% + ' ' ° + €271.73?1 + C2n+1
(3.1.2)

n+1 n+1+.

Proposition 3.1.1. For Reimer-n system, mixed volume = total degree = 2 x 3 x x

(n+1) = (n+1)!.

Proof. While exactly the same argument that was used in the proof of Proposition 2.1.1
can also be applied here, we shall provide a different proof for this proposition due to the
special structure of the system.

For the Reimer-n system given in (3.1.1), the supports of polynomials in the system

are

S1={(2,0,...,0),(0,2,...,0),...,(0,0,...,2)}={2e1,2e2,...,2en}

$2 = {(3,0,...,0),(0,3,...,0),...,(0,0,...,3)} = {3e1,3e2,...,3e,,}

Sn:{(n+1,0,...,0),(0,n+1,...,0),...,(0,0,...,n+1)}

= {(Tl + Del? (n +1)62,. . . , (Tl +1)en}1

where for i = 1,. . . ,n, e,- = (0,. ..,0,1,0,.. . ,0) is the ith unit vector with its ith com-
ponent 1 and all other components zero.
Recall that for mixed cell {a1 — a’l, . . . ,an — a2} induced by the lifted support S =

. . I I
(51,...,Sn) with inner normal cl = (0,1) 6 Rn“, we have {a1,a1} C 31,. . . , {aman} C

29

Sn and by Proposition 1.2.3,

(.,..3\

Mixed volume of the system = Z det

a

 

 

 

 

(an-ah)

Now, for each i = 1,. ..,n, {a,-,a;} C S,- = {(i + 1)el, . . . , (i + 1)en} implies a,- - a; =

(i + 1)(e[ - 822) where e] aé e’é and they are both in {e1, . . . , en}. Let

K 01 — all \ { 2(6] — eé) \

 

 

 

 

(an—a2) \(n+1)(e?—e’2’)/
Then

(a_2g)

detA=2x-~x(n+1)det ; =2x---x(n+1)detB

Kai—2}

 

 

where

(1 1)
61—32

 

 

\ 85’ ‘ 6'2’ I
is a matrix with all arrays being either —1, 0, or 1. When det B 7A 0, then Idet B] 2 1 and
consequently [det A] 2 2 x - - - X (n + 1). Thus the mixed volume of the Reimer—n system,

:0 [detA], is greater than or equal to 2 x x (n +1).

On the other hand, the mixed volume of any system is less than or equal to its total

30

degree. Here the total degree of the Reimer-n system is 2 X - - - x (n+1). It follows that the
mixed volume of the Reimer—n system agrees with its total degree 2 x- - - x (n+ 1) = (n+1)!.

Cl

Corollary 3.1.1. For the Reimer—n system, there is one and only one mixed cell regardless

of what sort of liftings being applied to the support (51,. . . , Sn).

I I I
Proof. For mixed cell {a1 — a1, . . .,an — an} of Reimer-n system, where {a1,a1} C

31,. . . , {an,a:,} C Sn, by Proposition 1.2.3,

(m_g\

Mixed volume of Reimer-n system = Z det g = (n + 1)!.

a

 

 

 

 

\an-aizI

However, from the proof in Proposition 3.1.1, for any mixed cell {a1 — all, . . . ,an — a2}

(.,—.3)

det g 2 (n+1)!.

(1-2,)

 

 

 

 

I I _
Therefore, there can be at most one mixed cell {a1 — a1, . . . ,an — an} w1th

(m_g)
det 3 = (n + 1)!.

I

\an—anI

 

 

 

 

31

3.2 Numerical results

Listed in Table 3.1 is the numerical result for solving Reimer-n system by the classical

linear homotopy with the typical start system Q(x) = (q) (x), . . . ,qn(x)) where

d
(11(33) = 313311— b],

(171(3) 2 and/iii” " bn

with randomly chosen complex numbers a1, . . . ,an,b1, . . . ,bn and the polyhedral homo-
topy continuation method [21]. Apparently the speed-ups of the classical linear homotopy
with the typical start system over the polyhedral homotopy in solving these systems shown
in the table are not as dramatic as Table 2.1 shows for Katsura-n systems. A major reason
is, as indicated in Corollary 3.1.1, ﬁnding only one mixed cell may not be as costly when

the system is solved by the polyhedral homotopy method.

32

 

 

 

 

 

 

 

 

 

CPU time
System Total Degree Speed-up ratio
Linear Polyhedral
Reimer-4 120 0.085 0.13 1.25
Reimer-5 720 0.73 0.993 1.41
Reimer—6 5,040 9.23 12.8s 1.39
Reimer-7 40,320 1m588 2m498 1.43
Reimer-8 362,880 30m43s 36m433 1.20
Reimer—9 3,628,800 7h52m4OS 8h47m42s 1.12

 

 

 

 

 

 

 

Table 3.1. Comparison of the classical linear homotopy with the typical start system and
the polyhedral homotopy in solving Reimer-n systems.

33

CHAPTER 4

Noon-n system

4.1 Noon-n system

In this Chapter, we discuss the Noon-n system [31],

x1(x%+x§+-~+x,2,—1.l)+1

2 2 2
x2(x +x +---+x —1.1)+1
P(x): 1 3 n

xn(x§+x§ +---+:c§,_1 — 1.1) + 1.

Since polynomials in the system all have constant terms, generically choosing its coef-

ﬁcients yields the augmented system:

$1(612$§ + C13333 + ' - ' + 611133121 + C10) + d1

222(C2123‘19' + 62333 + ' ' ° + anx% + 020) + d2 (4 1 1)

272%le + 6,1217% + - - - + Can—1533-1 + cno) + dn-

Before relating total degree of the system to its mixed volume, we ﬁrst recall certain

34

properties concerning the multiplicity of an isolated zero of a polynomial system. Simply
denoting the polynomial ring C[x1, . . . ,xn] by ’P" and treating it as a vector space, we

use (’P")* to represent its dual space, consisting of all the linear functionals on ’P".

Deﬁnition 4.1.1. For a given polynomial ideal I C ’P" with quotient ring Pn/I, the
dual space DU] of the ideal I is the set of linear functionals in the dual space (’P"/I)*

with their domain extended to P". Namely, for l E (’Pn/I)* and p E ’P"

l(p):=l(r) where p€r+I.

An immediate consequence of this deﬁnition is,

Proposition 4.1.1. For an ideal I C ’P” and l E (’P")*,

.lED[1]4==>l(p)=0 VpEI.

Deﬁnition 4.1.2. A subset D of the dual space (”P”)* is closed iﬁ

leD=> l-qu quP"

where linear functional 1 - q E (P")* is deﬁned by

(I'Q)p==l(qp) for p67)".

Deﬁnition 4.1.3. For 3' = (j1,...,jn) 6 N8 with |j| := Zajou and for z E C”, the

35

diﬁerential functional 0j[z] E (Pn)* with evaluation at z is deﬁned by

a [ J() 1 ( 5'”
'Z I: _ , - .
J p Jl!"'3n! 8x11...6rl,”

 

p)(2) VP E 73”-

An ideal I C ’P” is called O-dimensional if all zeros of I are isolated.

Deﬁnition 4.1.4. A zero 20 of a 0-dimensional ideal I C ’P" is an m-fold zero of I
if there exists a closed set of m, but no more than m, linearly independent diﬁerentiation

functionals dl = 23' ajojpo] with evaluation at 20 in the dual space ’D[I] .

Deﬁnition 4.1.5. For a = 1,. . . ,n the anti-diﬁ'erentiation operators so is deﬁned by

6;. U[z ifj >0
Saajlzli= .7 e l o

0 lfja=0

where e0 is the 0th unit vector with its oth component 1 and all other components zero

and
so (2 "Yjaj [20]) Z: Z 73- 8083' [20].
j j

Theorem 4.1.1. [34/ In (’P")*, a subset D(zo) of differential functionals with evaluation

at 20 is closed iﬂ
dl E P(zo) => sodl E ’D(zo) for all a = 1,. . .,n.

We now establish the relation between the mixed volume and the total degree of the

Noon-n system.
Proposition 4.1.2. For the Noon-n system,

Mixed volume = Total degree —2n = 3" — 2n.

36

Proof. From Proposition 1.1.1, the above equality holds if the system in (4.1.1) has 2n

zeros at inﬁnity. Consider its associated homogeneous polynomial system

161(612233-1- 613133 + ' ' ° + 617123721 + 6101123) + (11.138

~ 32(c21x% + 0231133 + ' ' ' + 02,1113, + 02038) + (12178
P(cco,x1, . . . ,a‘n) 2 (4.1.2)

:cn(cn1a:¥+ 9.22% + - - - + cm._1a:3,_1+ 0.02:3) + dams.

The zeros at inﬁnity of system (4.1.1) are the nontrivial zeros of system (4.1.2) in I?" with

2:0 = 0, i.e., nontrivial zeros of the system

1:1(c12x3 + c13x§ + ' - - + clnwg)

332(c2lx? + c23x§ + - - - + anxﬁ)

:vn(cn122¥ + 0,1223% + - - - + Cnn—1$%_1)-

It is clear that (1,0,...,O),(0,1,0,...,0),...,(0,...,0,1) are n isolated zeros of this

system. For the multiplicity of each of those solutions, we add one more polynomial
61331 4'ng2 + ' ' ' +0n33n + Cn+l

to system (4.1.2), where c,-, i = 1,. ..,n + 1 are randomly chosen complex numbers, re-

37

sulting in a system of n + 1 equations in n + 1 variables

151(x0axla- ° ° axn) = 0

P(xo,:L‘1,...,.’En) :
ﬁn($0,$1,...,xn) =0

ﬁn+l($0?x1) ' ' ' 1x71) : 0

where

151(170,$1,- - - .Ivn) = 931(612333 + 013mg + - - - + clnxg, + c10x3)+ dlxg
(4.1.3)
M500. 2:1. . . . mm) = :vn(cn1rc¥ + 6..sz + - - - + Gnu-13331-1 + 07.0133) + dusts?)

15n+1(330.11.-~.$n) = C1301+62302 +°"+0n$n +Cn+l'

2 1

For $0 = 0, the solutions are 212(0,_E_”c_‘1tl 0 ...,0), 22 = (0,0,—-C3é1;i,0,...,0),
.., 2,, = (0,0, . . . ,0, —E"::—1). In projective space IF", these solutions are in the same
equivalence class as (0,1,0,.. .,0),(0,0,1,0,...,0),...,(0,0,. ..,0,1).
Let I =< P(x0,x1, . . . ,xn) > be the ideal in ’P”+1 = C[:r0,:r1, . . . ,zrn] generated by
the polynomials in (4.1.3). At solution zz- = (0,...,0,——Cncz—"'Ll,0,...,0) for i = 1,...,n,

we assert that the following two linearly independent differentiation functionals

dz} = 000...0[Zil(:0) = P(Zz')

and

0
(”1'2 = 310...0l2il(P) = 333M229

constitute a closed subset of the dual space D[I] with maximal number of differential

38

functionals with evaluation at 21-. Obviously P(zi) = 0, so by Proposition 4.1.1, (ll,1 6 D]I].

Further, dlz-2 is also in D[I] because

—}5j(22') =(26j0513j230 + 3djxg)(zi) =2 0 for j = 1,. . . ,n

and

a -
EI—Opn+l(zi) = 0-

Moreover,

32 Ci00n+1
—2 ‘—.—“ t 0-
0:120

,, 1
Pile) = 5(26101‘2' + 6di$0)(zi) = 6.

NIP-d

320...0l2z'l (131') =

So, by Proposition 4.1.1, 620.0(2)) ¢ D[I]. On the other hand, for j = 1,. . . ,n,
- (9 -
60...010...0lzil (Pn+1) = 5mm) = Cj 74 0,
.7

6
hence, aTj[z,] ¢ D[I] for all j = 1,. . . ,n. Consequently, by Theorem 4.1.1, chI-1 and (ill-2
are the only two linearly independent differential functionals with evaluation at zz- that
form a closed subset of D[I]. Therefore, for each i = 1,. . . ,n, the multiplicity of 21 is

two. All together, they account for 2n solutions at inﬁnity for the system in (4.1.1). CI

4.2 A special start system for Noon—n system

As Proposition 4.1.2 indicates, for the Noon-n system, the difference between the total
degree and its mixed volume is 2n, which, compared with its total degree 3", becomes very
slim even when n is of moderate size. Such slim difference will certainly make it difﬁcult to

enjoy the beneﬁts that are commonly provided by using the polyhedral homotopy method

39

in solving them. Thus, the classical linear homotopy
H(x, t) = (1 — t)Q(a:) + tP(a:) = 0 (4.2.4)
with the typical start system Q(:r) = (q1(a:), . . . ,qn(a:)) where

d
(11(3) = 013111 - ()1,

(171(2)) = anxg’n — bn

with randomly chosen complex numbers a1, . . . ,an,b1, . . . ,bn appears to be the pr0per
choice for solving those systems. On the other hand, beyond the reach of the polyhedral
homotopy method, the classical linear homotopy can take a huge advantage on the strong
symmetry structure existed in the Noon-n system.

In the ﬁrst place, the multi-homogeneous structure [36] of the system allows the choice

of the start system

c1(:z:1+a)(:z:2+a:3+---+:cn+ﬁ)(x2+:z:3+---+a:n+'7)
Cg($2+a)($1+$3+"'+.’L‘n+,8)(l'1+$3+'°'+$n+’7)
Q($)= (4.2.5)

0n($n+01)(331+$2+"'+$n—1+ﬂ)($1+$2+~-+xn_1+7)

where c1, 02, ..., on, a, ﬂ, and 'y are randomly chosen complex numbers. Clearly, with
this choice, the symmetry in the Noon-n system is retained and with the invariance of this
symmetry in the homotopy, much fewer paths need to be traced for generating the whole

solution set.

40

For instance, for Noon-3 system

x1(x§+ x3 — 1.1) +1
P(x) = ”(mg + 23% — 1.1) +1

3330:? + 23% - 1.1) + 1,

the start system for the linear homotopy in (4.2.4) is

C1031+ 00(332 + $3 + @0132 + 1‘3 + 7)
QC”) = c2(:1:2 + a)($1+ 2:3 + ﬂ)(:1:1+ 1:3 + 7)

C3(133 + a)(1‘1+ x2 + mm + $2 + 7)-

To attain the whole solution set of Q(:r) = 0, we only need to permute the variables
:81, 322, $3 on a subset of solutions of Q(:z:) = 0. For example, the solutions of the following

three linear subsystems

z1+a=0 $2+$3+ﬁ=0 $2+$3+ﬁ=0
x1+x3+ﬁ=0 $2+a=0 x1+$3+ﬁ=0
$1+x2+ﬂ=0 $1+x2+ﬁ=0 $3+a=0

of Q(;r) = 0 are 21 = (—a,a—ﬁ,a—ﬁ), 232 = (a—ﬂ, —a,a—,B), and 23 = (a—B,a—-B, —a)
respectively. Obviously, solution 23 may be attained by permuting 2:1 and 2:3 in 21 or
permuting 3:2 and 9:3 in 22. In fact, any one of 21,2:2, and .23 can generate all the others
by permutations. This property is actually retained on the homotopy paths initiated from
those three solutions of Q(:r) = 0. So we may just follow one of these homotopy paths to
reach a solution of P(x) = 0 and generate the other two solutions from this solution by

permutations.

41

It is clear that the above three linear subsystems of Q(a:) = 0 share one thing in
common: they all have one a and two 58 as constant terms. Let us represent this set of
linear subsystems of Q(:t) = 0 by (a, 25). In general, denoting (mla, mgﬁ, m3'y) for
the set of linear subsystems of Q(:r) with m1 as, m2 ﬁs, and m3 75 as constants terms
where m1 + mg + m3 = 3, it is easy to see that solution of any one linear subsystem in the
set can generate solutions of all other linear subsystems in the set by proper permutations.
Among all the possible divisions of the linear subsystems of Q(:c) = 0 in this manner,
there are two sets of singular linear subsystems, hence no solutions for such systems, they
are (20, B) and (2a, 7). The rest of the 8 groups and the number of linear subsystems in

the same group are listed in Table 4.1.

 

 

 

 

 

 

 

 

 

 

 

 

constant terms number of solutions
(30:) = (a, a, a) 1
(33) = ([3. 16,16) 1
(37) = (7. 7, a) 1
(a. 2/3) = (a. 3.13) 3
(a. 2'7) = (01.7.7) 3
(25. 7) = (ﬁ. ﬁ, '7) 3
(ﬂ, 27) = (ﬂ. 7, 7) 3
(a. ﬁ. '7) = (01.47) 6

 

Table 4.1. Number of linear subsystems for different grouping of constant terms.

Exhibited in Table 4.1, there are, in total, 21 solutions of Q(:r) = 0, and all those
solutions can be generated by just solving one linear subsystem from each of those 8 groups.

Note that 21 = 33 — 2 x 3, which agrees with the mixed volume of Noon-3 system given

42

in Proposition 4.1.2.

For the start system Q(:r) = (q1(:c), . . . ,qn(:c)) in (4.2.5) where

(11(93)=61(1‘1+a)($2+x3+~°+xn+ﬁ)($2+$3+“-+$n+7)

Q2(I)=02($2+a)($1+$3+-”+$n+ﬁ)($1+$3+~~+$n+7)

(112(3) = Onlxn + 0X11 + 1‘2 + - ' ' + 9311—1 + ﬁlm + 332 + ' ' ' + xn—l + 7),

let (l1(:r), . . . ,ln($)) = 0 be linear subsystems of Q(:v) = 0, where, for each i = 1,. . . ,n,
l,(:c) is a linear factor of q,-(:c). We divide those linear subsystems as follows: let
(mla, mgﬁ, m3'y) be the set of those linear subsystems in which m1, m2 and m3 of the
equations in (ll(:z:),...,ln(:r)) = 0 have a, ,6 and 'y as constant terms respectively. Of

m2

course, m1+m2+m3 = n. It is clear that for ﬁxed m1, m2 and m3 there are Cg“ ~C _m1

linear subsystems of Q(:r) = 0 in (mm, mgﬂ, m37) and except for m1 = n —- 1, all those
linear subsystems are nonsingular.

To count the total number of possible different combinations of m1, m2 and m3
for which (mla, mgﬂ, m37) provide nonsingular subsystems, note that for ﬁxed m1 6
{0,1,...,n — 2,n}, there are n + 1 — m1 choices for m2, and when m1 and m2 are
determined, m3 = n — (m1 + m2). Therefore, in total, there are

n2+3n—2

(n+1)+n+(n—1)+-~+3+1= 2

different such combinations.

One of the solutions for linear subsystems (mla, mgﬁ, m3'y) where m1 75 n - 1 is

F‘A—‘f—Jhﬂ
(011,...,al,a2,...,ag,a3,...,a3) (4.2.6)

43

for certain a1, 02, and a3 . This solution comes from the subsystem whose ﬁrst m1 equa-
tions have constant term 0:, followed by the next m2 equations having constant term 3
and all the remaining equations having constant term 7. We may use this solution to
generate the solution set of all linear subsystems in (mla, mgﬁ, mm) by permutations.
For simplicity in the description, we shall replace a], a2 and 03 by 1, 2, and 3 respec-

tively, so the solution 1in (4. 2. m6) becomes (1,. ,1, 2,. .,,2 3, .,3). We generate all the

permutations of (1, ,1, 2,. .,,2 3,. 3) by the following steps:

m1 m2+m3 m3

Step 1: Let sq1= (1, ,1, 2, ., 2) and sq2— — (2,. 2, 3,. .,.3)

Step 2: For each sql and SQ2, search from left for the ﬁrst smaller-larger pair and
interchange them. If an interchange is made, check if there are some smaller numbers
to the left of the interchange. If not, save the resulting permutation. Otherwise, move
all the smaller numbers to the left of the interchange to the most left end and save the
permutation. For the currently saved permutation, repeat the procedure until no smaller-
larger pairs exist. Rom this step, 077,711 permutations will be produced from sql and
0,, m3 m1 permutations from SQ2.

Step 3: For each permutation produced from sq], replace all the numbers labeled 2
by the numbers in the permutations from sqg and save all the possible permutations.
For instance, if one of the permutations generated from sql is (1,2,1,2) and all the
permutations produced by sqg are (2, 3) and (3, 2), then the resulting permutations are
(1,2,1,3) and (1,3,1,2). Namely we replace 2,2 in (1,2,1,2) by (2,3) and (3,2).

m1 m2 m3
A
In total, there will be 0,, m1 -Cm _m1 permutations for (1,. ,1 ,2,...,2,3,...,3 . For

44

instance, when n = 4, let m1 = 2, m2 = 1, m3 = 1 for the start system

(11($) = C1($1+ 01)($2 + $3 + $4 + 5)($2 + $3 + $4 + 7)

(12($) = C2($2 + a)($1+ $3 + $4 + ﬁ)($1 + $3 + $4 + 7)

Q($) =
Q3($) = €3($3 + a)($1+ $2 + $4 + ﬁ)($1 + $2 + $4 + 7)
(14($) = C4($4 + a)($1+ $2 + $3 + ﬁ)($1 + $2 + $3 + 7),
there are C7731 - 033ml = C2 . C21 = 12 linear subsystems (l1(r), . . . , ln(x)) = 0 of

Q(r) = 0 in which (11(2),. . .,ln(:r)) = 0 have 2 a and 1 ,6 and 1 'y as constant terms.

One of them is

l1(:r)=a:1+a:0
L1(:1:) : l2(a:) = 2:2 + a = 0
l3(:r)=:rl+:1:2+:z:4+ﬁ=0
14(2) =:r1 +rg+x3+7=0
and the solution for L1(x) = 0 is (—a, —a, 20 — 7, 2a — B). For simplicity, write the
solution (1, 1,2,3). For the permutations of (1, 1,2,3), we follow the above steps. Let
sql = (1, 1,2,2) and sqg = (2,3). All the permutations generated from sql = (1, 1,2, 2)
by following Step 2 are (1,2,1,2), (2,1,1,2), (1,2,2,1), (2,1,2,1) and (2,2,1,1), and
the permutation from sq2 = (2,3) is (3,2). Then by Step 3, replace all the number
23 in all the permutations generated from sql by the numbers in each of the permuta-
tions produced by 8(12 and reach all the permutations for (1, 1, 2, 3). They are (1,1, 3,2),
(1,2,1,3), (1,3,1,2), (2, 1,1,3), (3,1,1,2), (1,2,3,1), (1,3,2,1), (2, 1,3,1), (3, 1,2,1),
(2,3,1,1) and (3,2,1,1). By replacing 1, 2 and 3 back to —a, 20 — '7, and 2a — 3 re-
spectively, solutions (-a, —a, 2a — )6, 2a — '7), (—a, 2a — 'y, —a, 20 — 3), (—a, 2a —

B, —a, 20: —'y),(2a -— 'y, —a, —a, 2a — 3), (2a — 5, —a, —a, 20 — '7), (—a, 20 — 'y, 20: —

45

18) -0), (—ai 2a —ﬁ1 20 — '7: —a)1(2a —7)—a! 2a _ ﬁt —a))(2a —:Bi _a1 20 _7) _a)1

(201—7, 2a—ﬂ, —a, —a, ), and (Zn—)6, 201—7, —a, —a, ) are attained. They are exactly

the solutions of the following remaining 11 linear subsystems in (201, Ill, 17) :

L6($)

11(3) = 131+ a
l2(:12) = 1132 + a
l3($) = $1 +$2 +$4 +7

l4($)=$1+$2+$3+ﬁ

l1(:r) = 221+a
l2(113) = $1 +$3+$4 +7
l3($) = 173 +0

l4($)=$1+$2+$3+,6

l1($) =$2+$3+$4+7
l2(.’1:)= 332 +0
l3(.’B) = 333 +0

l4($)=$1+$2+$3+ﬁ

l1(£E)=IL‘1+Oz
l2(a:)=:r1+x3+a:4+7
l3($)=$1+l‘2+$4+,3

l4(:r) = 234 + a

46

L3($) =

L5($) =

L7($) =

r-——’\———-\/———’\——‘/——’h—-—\r———’¥——-—.

l1(:1:)== z1+a
l2($)=$1+$3+$4 +5
[3(2) = 2:3 +0:

l4(£L‘)=.’L‘1+$2+I3+’7

l1(:1:) =$2+z3+x4+ﬂ
l2(:r) = 2:2 + (1
13(2): 273 + a

l4($)=$1+$2+$3+7

l1(a:)=a:1+a
l2($)=$1+$3+x4+ﬁ
l3(:1.‘) =$1+$2+x4+7

14(2): :54 + Oz

l1($)=$2+$3+$4+5
l2(:l:)=a:2+a
l3($)=x1+xg+x4+7

l4(:z:) = .734 + a

l1($)=$2+$3+$4+7 l1($)=$2+$3+$4+ﬁ

lz($)=$2+a l2($)=$1+$3+$4 +7
1110(2)) = 141(2)) :

l3($)=$1+$2+$4+5 l3($)=$3+0

l4(a:) = x4 + 0: l4(:r) = $4 + a

and

l1($) = $2+$3+$4+7
12(w) =x1+x3 +x4 +ﬂ
13(2) = $3 + a
l4(:r) = :34 + 0:.
Therefore, tracing one of the homotOpy paths of the classical linear homotopy in (4.2.4)
emanated from one of the linear subsystems of 62(2)) =4 0 in (mla, mgﬁ, m37) is sufﬁcient

to generate all the corresponding solutions of P(x) = 0 in this group.

4.3 Numerical results

Numerical results on solving Noon-n systems by different homotopies are listed in Table
4.2. Recall that the difference between the total degree and the mixed volume of Noon-n

s stems is 2n. Total de ee, 3", paths need to be traced when the typical start system
Y gr

Q(:r) = (q1(:r), . . .,qn(:r)) where

d
91(3) = “13311— b1:

Q1205) = anxg" '— bn

47

with randomly chosen complex numbers a1, . . . ,an, b1, . . . , bn is used in the classical linear

homotopy

H(x,t) = (1 — t)Q(:I:) + tP(:r) = 0.

And twice of the mixed volume, 2 x (3" — 2n) , paths need to be traced when the polyhedral
homotOpy is applied. The table clearly shows that the classical linear homotopy with the
typical start system works better than polyhedral homotopy because much more paths

need to be followed as n gets larger for the polyhedral homotopy method. Moreover,

n2+3n—2
2

traced when a. proper start system as in (4.2.5) is assigned for the classical linear homotopy.

due to the symmetry of Noon-n systems, only homotopy paths need to be

This number is shown in the 3rd column on the table, it is much smaller than the mixed

volume. Apparently, solving Noon-n systems by choosing start system Q(:r) in (4.2.5)

leads in speed by a huge margin in ﬁnding all the isolated zeros of Noon-n systems.

48

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

CPU time

System Mixed Volume # of paths

Polyhedral Typical Q(2:) Special Q(:r)
noon-10 59,029 64 5m128 1m27s 1.13
noon-11 177,1 25 76 23m27s 5m32s 1.4s
noon-12 531,417 89 1h28m008 27m29s 2.23
noon— 13 1,594,297 103 7h02m103 3h7m10s 3. ls
noon-19 1,162,261,429 208 - - 18.53
noon-29 6.8630377E13 463 - - 2m103
noon-39 4.0525551E18 818 — - 16m488
noon-49 239299331323 1,273 - - 29m58s
noon-59 1.4130386E28 1,828 — - 1h11m395
noon-69 8.3438517E32 2,483 - - 2h16m59s
noon-79 4.9269609E37 3,238 - - 4h31m03s
noon—89 290932121342 4,093 - - 10h17m23s

 

 

 

 

 

 

 

Table 4.2. Comparison of the polyhedral homotopy and the classical linear homotopy with
different start systems in solving Noon-n systems.

49

CHAPTER 5

Generalized eigenvalue problem

By and large, polynomial system P(x) = (p1(a:), . . . , pn (1')) whose mixed volume is much
less than its total degree should be solved by the polyhedral homotopy method. However,
when certain m—homogeneous structure of the system is apparent, we may still choose
appropriate start systems 62(2) 2 0 in the classical linear homotopy so that the number
of homotopy paths that need to be traced matches the mixed volume of the system. In
such situations, the polyhedral homotopy method can no longer be beneﬁcial in reducing

wasteful computations.

5.1 Generalized eigenvalue problem

Consider the generalized eigenvalue problem

Ax 2 A82:

50

where

 

 

011 a12 ain
a21 $22 a2n
A:
“111 an2 arm
and
r 7
b11 b12 bln
b21 b22 b2n
B =
bnl bn2 bnn

 

 

are n x n matrices. This problem is actually an n polynomial equations in n+1 variables

A,:I:1,...,:I:n:

/\(b11$1+“-+ b1n$n)-(a11$1+-”+ aln$n) = 0,

A(bn1$1+ ‘ ' ' + bnnmn)—(an1$1+ ' ' ' + 041711.11): 0.

We augment the system with a linear equation

c1231+~~+onzn+cn+1=0

51

where C}, . . . , Gn+1 are randomly chosen complex numbers, yielding a polynomial system

of n + 1 equations in n + 1 variables

Mbu$1+m+ b1n$n)-(011$1+'°°+ ain$n)

(5.1.1)
A(b,,1:cl + - - - + bnnxn)—(an1x1 + - - - + annxn)

€1$1+"°+ 0n$n +Cn+1-
Proposition 5.1.1. The mixed volume of system (5.1.1) is 71.
To prove this proposition, we need to introduce the following fundamental lemmas.

Lemma 5.1.1. If 20,211,. . .,2n 6 IR" are aﬂinely independent, i.e., 21—20, 22—20, . . . ,2,,—
20 are linearly independent, then the volume of the convex hull of those points, denoted by
Voln(conv(z0, 2:1, . . . , 2n)), is

(.,_,0\

1 32—30

 

 

 

 

(.,.-..)

Lemma 5.1.2. For a polynomial system P(x) = (p1(x), . . . ,pn(x)), let 51,” .,Sn be the

support of p1(x), . . . ,pn(x) respectively. If 31 = 52 = = Sn = S, then

M(S, . . . , S) = n! Voln(conv(S)).

Proof. The mixed volume of P(x) is the coefficient of the term Al x x An in the

homogeneous polynomial Voln(A1conv(Sl)+- --+/\nconv(Sn)) of degree n in A1, . . . , An.

52

Since .9le2 = :5" :5, we have

Voln(A1conv(Sl) + -- - + /\nCOIlV(Sn))
=Voln(()\1 + - -- + An)conv(S'))
=(A1 + - - - + An)nVoln(conv(S))

=n!Voln(conv(S))/\1 x -- - x An + other terms.

Therefore,

M(S, . . . , S) = n! Voln(conv(S)).

E]
Proof of the proposition. Consider the system
W311$1+'°'+51n$n)-(&11$1+°“+ é1n$n) + 51n+1
(5.1.2)
’\(bn1$1+ ' ‘ ' + bnnmn) — (anlxl + ' ° ' + annxn) + Cinn+1
)‘(5n+llxl + ' ' ' + 5n+1n$n) + C1$1+m+ 0n$n + 0n+1
where (1,-j, bji, i = 1, . . . ,n, j = 1, . . . ,n + 1 are randomly chosen complex numbers. The

supports of all the polynomials of this system are the same. Taking n = 2 for instance,

the above system becomes

M511$1 + l312$2) — (a11$1 + 612$2) + (”113
M521$1 + 522$2) — (521$1 + 5.2ng) + €123 (5'1'3)

3(031271 + 032222) + C1131 + 021122 + C3

with variables A, 231 , and x2. We list the points in the support in descending lexicographic

53

 

 

 

 

Figure 5.1. The convex hull of S for n = 3.

order, that is 21 >181. zo for 20, 21 E Z30 if the left-most nonzero entry of the vector 21 -—
zo is positive. Then S = $1 = 52 = $3 = {(0, 0, 0),(0, 0,1),(0,1,0),(1,0, 1),(1,1,0)} =
{7.0, 21, 22, 23, .24}. The graph of the convex hull of S is shown in Figure 5.1.

From Lemma 5.1.2, the mixed volume of system (5.1.3) is M(S, S, S) =
3!Vol3(conv(S)). To compute the volume of the convex hull of S, we divide conV3(S)
into two simplices: Q1 = conv{z0,z1,22, :43}, and Q2 = conv{z0,z2,z3,z4}. Graphically

it is clear from Figure 5.1,

Vol3(conv(S)) = Vol3(Q1) + Vol3(Q2).

For a proof of this equality, ﬁrst note that Q1 and Q2 have three points 20, 2:2, z3 in

common and conv{zo, 22, 23} is a face for each. A normal of the face is v =- (1, 0, —1) since

(.,-1.) (.,-x.)

22—20 = 01 0 =1i+02+(—1)k-

(23—20) (101)

 

 

 

 

54

Apparently, 21 and 24 lie on different sides of the face because

(21,v) x (24,v) = ((0,0,1),(1,0,-1)) x ((1,1,0),(1,0,—1))

=—1x1=—1<0.

Therefore, Q1 ﬂQg = Q and conv(S) = Q1 U622, it follows that

V013(conv(S)) = Vol3(Q1) + Vol3(Q2).

On the other hand, 20, 21, 22, 23 are affinely independent. By Lemma 5.1.1

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

/ ,, _ ,0 ) l 0 0 1 )
1 1 1
V013(Q1)=§ 22—20 =§ O 1 0 :3?
K 23 — 20 J \ 1 0 1 j
K 22 — 20 \ K 0 1 0 \
1 1 1
V013(Q2) = 3’, 23 — 20 = g 1 0 1 = a,
K 24 — Zo ) K 1 l 0 )
thus,
2
Vol3(conv(S)) = 37.
And
M(S, S, S) = 3!V013(conv(S))= 3! x g = 2.
For the general system in (5.1.2), the variables are A, x1,x2, . . . ,xn. Listing the points

55

in the support in descending lexicographic order yields

5=&=&=m=nﬂ
={(0,0,...,0),en+1,en,...,e2,61+en+1,e1+en,..,,el+62}

= {20,21,22,...,22n}

where 20 = (0,0, . . . ,0), and

en+2_,- for i = 1, . . . ,n,
21' =

e1+ez(n+1)_,- for i=n+1,...,2n.

Similarly, conv(S) can be divided into n simplicies:

Q1 = conv{20,21, . . . , 2n+1}

Q2 = conv{20,22, . . . , 2n+2}

n = COHV{ZO,Zn1"" 22nl‘

These simplicies can intersect only at their faces and for each i = 1, . . . ,n,

56

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

{ Zz' - 20 \ K 21' \
1 Zi+1 — 30 1 Z{+1
V01n+l(Qi) =m : = m
\ Zi+n - 30 j \ Zi+n /
K \ { en+2—i \
en+2—i .
C
_ 1 62 _ 1 2
_(n+1)! 81 +871“ _ m en+1
K en+3—i
81 + en+2—i
/ \ ., l
l e, \
_ 1 o _ 1
_(n+1)! : _(n+1)!'
Ken+1 )

 

 

Hence,

Voln+1(conv(S)) = n x

(n+1) (n+1)!’

and the mixed volume of system (5.1.2) is

 

M(S, S, . . .,S) = (n +1)!Voln+1(conv(3)) ='(n +1)! x (n n

Now, support S = (S1, . . . , Sn) of system (5.1.1) is a subset of the support S = (S, . . .,S)

of system (5.1.2), that is, S,- Q S for all i = 1, . . . ,n. Thus

57

 

 

 

On the other hand, consider the system

Ax — ABx = 0
(5.1.4)

x1+x2+---+xn—n-—1=0

where
- .- ,- -_1
211 1 100-0 211 1
121 1 020-0 121 1
A=112 1X003 0X112 1
.111”'2. L000---n_ .111"'2l

 

 

 

 

 

 

and B = I , the n x n identity matrix. For these speciﬁc matrices A and B, the ze-
ros of system (5.1.4) are (A, x1, x2,..., xn) = (1,2,1,1,...,1), (2,1,2,1,...,1), ...,
(n,1,1,1,...,2), that is, for i = 1,...,n, the ﬁrst component of the ith zero is i, the
(i + 1)th component is 2 and all the others are 1. So the number of isolated zeros of system

(5.1.4) in (0')" is n, and therefore

M(Sl,...,§n) 2n.

So,

58

5.2 A special start system for generalized eigenvalue

problem

The total degree of system (5.1.1) is 2", but the system has at most n isolated zeros. So
the system is deficient. If the classical linear homotopy is used to solve the problem, at
least 2" — n paths will be extraneous, representing huge wasteful computations. If the
polyhedral homotopy is applied, 2n paths need to be followed. But when 11 becomes
larger, ﬁnding all the mixed cells requires a big amount of computations . To alleviate
this problem, Li et al. [17] suggested the random product homotopy and proposed a more

efﬁcient choice for the start system Q(x) = 0:

Q1($) = (A + 611)($1 + 012)

(12($) = (A + C21)($2 + 622)

Q($) = < 5 (5.2.5)
(171(37) = (A + 0n1)($n + 0112)

qn+1($) = €1$1+m+ onxn + 0n+1

 

where qj’s i = 1,...,n,j = 1,2 and 6),, k =1,...,n+1 are randomly chosen complex
numbers. It is clear that Q(x) = 0 has exactly n isolated solutions. It is proved in [17]

that for this choice of Q(x) = 0, properties 0—2 hold for the linear homotopy

H(x,t) = (1 — t)Q(x) + tP(x) = 0.

Thus all the isolated solutions for the generalized eigenvalue problem can be found by

following n paths emanating from the solutions of Q(x) = 0.

59

The generalized eigenvalue problem

Ax = ABx,

in particular the eigenvalue problem Ax = Ax, for B = I , has important applications in
many scientiﬁc areas. It is widely known that very efﬁcient algorithms for matrix eigenvalue
problems, QR algorithm for Ax = Ax and Q2 algorithm for Ax = ABx, have been im-
plemented and asserted in the software package LAPACK [16]. However, as the size of the
matrix becomes larger, more computing resources are required. And a natural way to allo-
cate extra computing resources efﬁciently is to perform independent tasks simultaneously
in parallel. Since each isolated zero of a polynomial system is computed independently
of all the others in the homotopy continuation method, it provides a natural environment
for the parallelization. We have tested the parallel version of our homotopy algorithms on

generalized eigenvalue problem

Ax = ABx

with augmented linear equation

clxl+---+onxn+cn+1=0

where _ _
an 0.12 . . . “111
(121 022 . . . 0.2”
A =
an] an2 ann

 

 

60

and

 

 

L . ..
are randomly chosen n x n matrices and c1, . . . , cn+1 are randomly chosen complex num-
bers for n = 100 and n = 200. We also tested the parallelization for eigenvalue problem,
i.e. B = I, the n x n identity matrix and A is a randomly chosen matrix. Our preliminary
numerical results are listed in Table 5.1. The speed-up ratio on the table represents the
ratio of the CPU time of a single processor to that of multiple processors. Almost perfect
speed-ups in the table illustrate the great potential in solving very large algebraic general-

ized eigenvalue problems in parallel by the homotopy continuation method in contrast to

highly serial QZ or QR algorithms.

61

 

 

 

 

 

 

 

 

 

 

 

 

 

CPU time Speed-up ratio
n # of processors
Ax=ABx Ax=Ax Ax=ABx Ax=Ax
100 1 86.5 54.6 1 1
2 43.7 27.5 1.99 1.99
3 28.9 18.2 2.99 3
5 17.9 11.2 4.83 4.88
7 12.6 7.9 6.86 6.91
200 1 1795 1146 1 1
2 898 573 2 2
3 598 384 3 2.98
5 366 233 4.9 4.92
7 260 166 6.9 6.9

 

 

 

 

 

 

 

Table 5.1. The parallel speed—up for solving generalized eigenvalue problem Ax = ABx and
eigenvalue problem Ax = Ax with n = 100 and n = 200.

62

BIBLIOGRAPHY

[1] R. Abraham and J. Robbin: Transversal Mappings and Flows. W. A. Benjamin, Inc.,
New York-Amsterdam, 1967.

[2] E. L. Allgower and K. Georg, Numerical Continuation Methods, an Introduction,
Springer Series in Comput. Math, Springer-Velag, Berlin, Heidelberg, 13 (1990).

[3] E. L. Allgower and K. Georg, Continuation and path following, in: Acta Numerica.
1993, A. Iserles, ed., Cambridge Univ. Press, Cambridge, 1993, 1—64.

[4] D. N. Bernshtein, The number of the roots of a system of equations, Funct. Anal. Appl.,
9 (1975), 183—185.

[5] J. Canny and J. M. Rojas, An optimal condition for determining the exact number of
roots of a polynomial system, in: Proceedings of the 1991 International Symposium on
Symbolic and Algebraic Computation, ACM, 1991, 96—101.

[6] S. N. Chow, J. Mallet-Paret and J. A. Yorke, Homotopy method for locating all zeros
of a system of polynomials, in: Functional Differential Equations and Approximation
of Fixed Points, H. O. Peitgen and H. O. Walther, eds., Lecture Notes in Mathematics,
Springer-Velag, Berlin, Heidelberg, 730 (1979), 77—88.

[7] H. H. Chung, polynomial homotopy and its applications to polynomial system solving,
PH.D. dissertation, Michigan State University, 1998.

[8] D. Cox, J. Little and D. O’Shea, Ideals, Varieties and Algorithms, An Introduction to
Computational Algebraic Geometry and Commutative Algebra, Springer-Verlag, New
York, 1998.

[9] F. J. Drexler, Eine methode zur Berechnung siimtlicher Lbsungen von Polynomgle—
ichungssystemen, Numer. Math, 29 (1977), 45-58.

[10] C. B. Garcia and W. I. Zangwill, Finding all solutions to polynomial systems and other
systems of equations, Math Programming, 16 (1979), 159—176.

[11] T. Gao, T. Y. Li and M. Wu, MixedVol: A software package for mixed Volume com-
putation, ACM Transactions on Math. Software, Vol. 31, No. 4 (2005), 555-560.

63

[12] B. Huber and B. Sturmfels, A polyhedral method for solving sparse polynomial sys-
tems. Math. Comp, 64 (1995), 1541—1555.

[13] B. Huber and B. Sturmfels, Bernshtein’s theorem in afﬁne space, Discrete Comput.
Geom., 7 (1997), 137-141.

[14] A. G. Khovanskii, Newton polyhedra and the genus of complete intersections, Funct.
Anal. Appl., 12 (1978), 38—46.

[15] A. G. Kushnirenko, Newton polytopes and the Bézout theorem, Einct. Anal. Appl.
10 (1976), 233—235.

[16] http://www.netlib.org/lapack/

[17] T. Y. Li, Solving polynomial systems by the homotopy continuation method, Hand-
book of numerical analysis, XI (2003), 209—304,

[18] T. Y. Li, On Chow, Mallet-Paret and Yorke homotopy for solving systems of polyno-
mials, Bull. Inst. Math. Acad. Sinica 11 (1983), 433—437.

[19] T. Y. Li and T. Gao, Mixed volume computation via linear programming, Taiwanese
J. of Math. 4 (2000), 599—619.

[20] T. Y. Li and T. Lee, Mixed volume computation, A revisit, Submitted.

[21] T. Y. Li, T. Lee and C. Tsai, HOM4PS—2.0: A software package for solving polynomial
systems by the polyhedral homotopy continuation method, Submitted.

[22] T. Y. Li and X. Li, Finding mixed cells in the mixed volume computation, Found.
Comput. Math. 1 (2001), 161-181.

[23] T. Y. Li and T. Sauer, A simple homotopy for solving deﬁcient polynomial systems,
Japan J. Indust. Appl. Math. 6 (1989), 409—419.

[24] T. Y. Li, T. Sauer and J. A. Yorke , The cheaters homotopy: an efﬁcient procedure for
solving systems of polynomial equations, SIAM J. Numer. Anal., 26 (1989), 1241-1251.

[25] T. Y. Li and C. Tsai, HOM4PS—2.0para: Parallelization of HOM4PS—2.0 for solving
polynomial systems, Submitted.

[26] T. Y. Li and X. Wang, Nonlinear homotopies for solving deﬁcient polynomial systems
with parameters, SIAM J. Numer. Anal. 29 (1992), 1104—1118

[27] T. Y. Li and X. Wang, The BKK root count in C", Math. Comp. 65 (1996), 1477-1484.

[28] P.Meravy, Symmetric homotopies for solving systems of polynomial equations, Math.
Slocava, 39 (1989), 277—288.

64

 

[29] A. P. Morgan, A homotopy for solving polynomial systems, Appl. Math. Comput. 18
(1986), 173—177.

[30] A. P. Morgan and A. J. Sommese, A homotopy for solving general polynomial systems
that respect m—homogeneous structures, Appl. Math. Comput. 24 (1987), 101—-113.

[31] V. W. Noonburg, A neural network modeled by an adaptive Lotka—Volterra system,
SIAM J. Appl. Math. 49 (1989), 1779—1792.

[32] J. M. Rojas, A convex geometric approach to counting the roots of a polynomial
system, Theoret. Comput. Sci. 133 (1994), 105—140.

[33] I. R. Shafarevich, Basic Algebraic Geometry, Springer-Verlag, New York, 1977.
[34] H. J. Stetter, Numerical Polynomial Algebra, SIAM, 2004
[35] C. Traverso, The PoSSo test examples, available at: www.inria.fr/saga/ POL.

[36] J. Verschelde and A. Haegemans, The GBQ—Algorithm for Constructing Start Systems
of Homotopies for Polynomial Systems, SIAM Journal on Numerical Analysis, Vol. 30,
No. 2 (1993), 583—594

[37] A. H. Wright, Finding all solutions to a system of polynomial equations, Math. Comp.
44 (1985), 125—133.

[38] W. Zulener, A simple homotopy method for determining all isolated solutions to poly-
nomial systems, Math. Comp. 50 (1988), 167—177.

65