BIB-VERSION:: CS-TR-v2.0
ID:: CORNELLCS//TR93-1394
ENTRY:: 1994-03-17
ORGANIZATION:: Cornell University, Computer Science Department
LANGUAGE:: English
TITLE:: An Algorithm for the Newton Resultant
AUTHOR:: Canny, John 
AUTHOR:: Pedersen, Paul
DATE:: October 1993
PAGES:: 21
ABSTRACT::
Given a system of $n+1$ generic Laurent polynomials, for $i \,=\,
1, \ldots, n+1$,
$$\eqlabel(\InputSystem)
  f_i(\x) \quad = \quad \sum_{q\in \A_i} c_{iq} \,x^q;
    \qquad    q \,=\, (q_1,\ldots,q_n);
    \qquad \x^q \,=\, x_1^{q_1}x_2^{q_2}\cdots x_n^{q_n};
    \eqno(\InputSystem)
$$
with (finite) support sets $\A_i \subset L$, where $L$ is some affine
lattice isomorphic to $\Z^n$; we consider algorithms for the {\it
Newton resultant} $R(f_1,f_2, \ldots, f_{n+1})$.  This is the unique
(up to sign) irreducible polynomial with coefficients in $\Z$ and
monomials in the $c_{iq}$ which determines whether or not
system~(\InputSystem) has common roots in the {\it algebraic torus}
$(\C-\{0\})^n$.  The resultant depends only on the {\it Newton
polytopes} $N_i \,:=\, conv(\A_i) \subset \R^n$ of the sets $\A_i$.
Our terminology emphasizes the dependence on the combinatorics of the
Newton polytopes.  The algebraic torus is the natural setting for us
because we are interested in the properties of systems of polynomials
which are invariant under symmetries of the affine lattice $L$, and
translation by $q\in L$ corresponds to multiplication by $x^q$ at the
level of polynomials.  Since $x^q$ may have negative exponents, we
restrict to points none of whose coordinates are zero.
END:: CORNELLCS//TR93-1394
BODY::
An Algorithm for the Newton Resultant
John Canny***
Paul Pedersen
TR 93-1394
October 1993
Department of Computer Science
Cornell University
Ithaca, NY 14853-7501
* Supported by a David and Lucille Packard Foundation Fellowship and by NSF PYl
Grant lRl-8958577.
** Partially supported by NYl (NSF) CCR-9258533
An Algorithm for the Newton Resultant
JOHN CANNY *			PAUL PEDERSEN **
U.C. BERKELEY			CORNELL UNIVERSITY
1 Introduction
Given a system of n + 1 generic Laurent polynomials, for `			1? + 1,
fi(x)			=			? cjqx?;			q = (q?,...,q?);			_ = ??11?2?2... rq?n; (1.1)
qEA?
with (finite) support sets Ai c L, where L is some affine lattice isomorphic to
?fl; we consider the Newton resultant R(f1,f2,... ,fn+1). This is the urnqlle
(up to sign) irreducible polynomial with coeflicients in ? and monomials iii
the Ciq which determines whether or not system (1.1) has common roots in the
algebraic torus (? --H fOJ)?. The resultant depends only on the Newton polytopes
Nj := conv(Aj) ? [R? of the sets Aj. If the system could not have
roots in the torus for any choice of the Cjq then the resultant is defined to equal
1, by convention. What we call the Newton resultant appears as the "sparse
mixed resultant" in [CE], [PS], and the "A--Hresultant" in [GKZ].
Our terminology emphasizes the ??ependence on the combinatorics ol the
Newton polytopes, and removes the rnisle?'?ding reference to sparcity in the sense
of having few monomials. The algebraic t??rus is the natural setting for `is since
we are interested in the properties of systems of polynomials which are invariant
under symmetries of the affine lattice L. Translation by q E L corresponds to
multiplication by ?? at the level of polynomials, and since rq may have negative
exponents, we should restrict to points none of whose coordinates are zero, i. e.
the algebraic torus. We refer to roots in tile algebraic torus as toric roots.
2 Basics about mixed volumes
The Minkowski sum A ? B ??f polytopes A, B C [Rfl is their pointwise sum,
A ? B := f u + v : u ? A, v E B ?. We shall consider the iterated Minkowski
* Supported by a David and Lucile J)??kard Foundatio,i Fellowship an?l by NSF PY!
Grant IRI-8958577
** Partially supported by NYl (NSF) (Ci?-9258533
2
sum N			N1 .... 0
A basic combinatorial-geonietric invariant of any n lattice polytopes
P1, .. , Pn is their mixed volume ?\4V(Pi, . , Pn). It is defined as the coefildeiit
of the monomial ....... An in the polynomial Vol(AiPi o A2P2 .... 1. AnPn).
Classic expositions on mixed volumes niay be found in [BF], and [E].
The mixed volume is determined (and may be coniputed) using mixed
subdivisions of the Minkowskii sum P := Pi 0... 0Pn. Mixed subdivisions arise
by choosing (randomly) lifting fnnctionals ?? : H [R, and then considering
"lifted polytopes" Pffi C [Rn+1 = the graph of Pj under Wi:
Pi [ (q,w?(q)) : q E Pit.
Let P = P1 .... ? P??denote the Minkowski sum of t?e lifted polytopes. The
lower convex hull A of P is the collection of f?tcets F of P?who?e inner normal has
p?sitive last co?ponent. Each s?ch fac?t has the form F = P1 ... .0 Fn, where
Fi is a face of Pi. We say that F is a mixed facet if dim(FA) = 1 for i = 1,. . ,
More generally, any facet of A has a type (d1,... , dn), where dj = dim(Ej).
Facets of A may be found usilig linear pr()gi'amming.
Suppo?e 7r : [Rfl+i H [Rn projects t() the first n coordinates, then A
f 7r(F) : F ? A ? is a subdivision of P. Each cell C of A has the form 7r(F) --H?
F1 0... 0 F? where 7r(??) = Fj is a face of Pj. We assume that the weights w
are sufficiently generic, meaning that ditn(C) = dini(F1) + ... + (hrn(Fn)t for
every C ? A. In this case A is called a mixed subdivision of P. The pr()jedi(?n
of mixed facets of A are mixed cells of A. The sum of the volumes of the mixe?l
cells of any mixed subdivision A equals the mixed volume MV(P1Pn). This
is an integer which does not depend on tlie choice of subdivision. For details oii
mixed subdivisions and their relation to mixed volumes see [Bet]
Mixed cells are parallelotopes. If one considers them "halfopen", th?,ii
their volume equals their number of lattice points. We may determine a coiisis
tent sense of "half open" by fixing some random direction 6, and only coiintiiig
lattice points lying on facets where 6 is iii'vard pointing, for instance.
In our application we have n + 1 ?)olytopes. Their Minksowski suiii also
has a mixed decomposition obtained by means identical to the above i.e. as
the projection of the lower envelope of a lifted sum, with the difference that
now every cell, even a mixed cell, is the sum of at least one vertex from one
of the n + 1 inputs. Mixed cells iii tILis setting are sums of n edges and oiie
vertex, so that lattice points lying in inixe?t cells of a mixed decomposition of
N = N1 ... .0 Nn+1 have associated to them a unique index which contributes
the vertex. This index is crucjal to the c??tistruction we are going to des?ribe.
3
3 Basics about Newton Resultants
The mathematical foundations for the theory of Newton resultants can be found
in [GKZ], [PS], and [CE], where it is shown that:
(1)
(2)
(3)
degj?(ft) = A/IV(N1,... , Nj,..., Nn+i).
R(f1,J2,...,fn+1) =R'.H fi(?),
where the product in item (3) is over toric roots of f2 = = fn+1 = 0, and R'
is a product of lower dimensional resuftants not involving f1.
In [CE] an algorithm is proposed f??r computing the Newtoii resultant
using analogues of Macaulay matnces ??e shall describe an explicit implemen-
tation of this algorithm with complexity estimates. Maple code for the imple-
mentation is included in the Appen?hx.
The basic principle underlying the construction is simple: regard each
equation fj(x) = 0 as a linear relation on the power-products ?? : q E A5:
fj(?x) = (c1,. . .,c?) . (??i			,x?n) = 0.			(3.1)
Any common solution ?x0 determines a null vector of this linear system by eval-
uation of the monomials ?? at x0. however, one typically has more variables
in UjAj than equations (n + 1). New equations can be generated by takiiig
monomial multiples ?xUfj = 0 of thc old equations. This generates new power-
products ?u+q, and the game is to pick multiples which generate as few new
power-products as possible, so that one eventually ends up with as many equa-
tions as variables. Suppose we write this linear system as Al (ru) = 0, where
M has components Cjq as in (3.1).
The vanishing of the determinant of this linear system is a necessary
condition for the existence of a common root. Therefore the resultant, which is
irreducible ([PS]) must divide det(Al) . Multivariate factorization of the deter-
minant, and extraction of the factor of ;??)ropriate degree (according to item (1)
above) gives you the resultant.
This is exactly the type of algonthm defined in [CE], where a matrix A/I
is constructed whose columns arc indexed by the monomials of the Minkowski
sum N = N1 .... ? Nn+1, ai?d whose rows are indexed by monomial multiples
4
ofthefj's: ffp?CcN = Ni(?...(DN?+i,andC = E'(D...tF?+1,and
if i is the largest index for which Fj is a vertex --H say qJ, corresponding to the
j-th monomial c????I of f? --H then let RC(p) (i,j). This is the so called "n)w
content" of p. Define M by
Mp?q =			Cik,			if q--H p+ q?? = q?? for some k, where (i,j) = RC(p)
0,			if q--H p+ q?5 ? Ai
We refer to [CE] for details of the proof that the matrix so constructed is square
and has non-identically-vanishing determinant. We refer to this matrix Al as (I
Newton matrixfor the system (1.1).
Our objective here is to describe a cc?ncrete impl?mentation of this algo-
rithm. Optimally there would be exactl? MV(f1,.. ....... . ,f?) rows indexed
by multiples of f?, so that the degree of the determinant det(M) would coinci?I?,
with the degree predicted in item (1) <`ove. Generally speaking, this will not
happen. We can hope that by adding rows "greedily", i.e. only according as we
need them to cover the monomials (leterntined by columns of M which w( have
already occupied, then we might find a s?tb-determinant of M which is already
good enough.
4 Description of the Algorithm
Input: A system of generic polyiioirnals (1.1)
Output: A matrix A', whose determinan?- has the Newton resultant as a factor.
Parameters: n = dimension; mboiinds A,: I; mbounds the number of extreni?
points of Nj = conv(A?); h = tlie number points of the Minkowski sum N --H-
N1 .... e Nn+1, which is O(in?+1).
Step 1.
Compute the convex hulls Nj = conr(A?) of the exponent vectors of the in
puts (1.1). Assemble the vertices of ]V? a:, the columns of a matrix,
qjil ... qjim
qjnm
We approximate the convex hull by sorting the given lattice points in a linear
number of pseudo-random directions, an?3 tiien run LP's to determine which of
the remaining points are not hull vertices. Any such point p will b(. f?asiI?l?. for
5
the LP with convexity constraints
jEC
= 1,
Aj > O? j E C.
where C is the current set of candidate hull vertices.
Suppose we use k random directions. The cc?mbinatonal complexity of approxi-
mating the hull is O(knm log2(m)). The remaining LP's run in O(md3,'?) steps
using interior point methods. The initial approximation appears as a heuristic
improvement.
Step 2.
Compute a collection of pseudo-random vectors which will be used to lift tIK
points of each polytope, L = [L1Ln+1]. The cost here is 0(n2).
Step 3.
Set up LP equations defining the l()wer -envelope of the Minkowski sum of the
lifted points as follows. A general point of of Nj has the form
--H A??? A?l, . . . , AimiT,
where the Aj satisfy a convexity constr;iiiit
Aj = Aj1 + ... ? Aim = 1
A general point of N = N1 .... ? Nn+1 has the form
v --H
The objective function is determined by the random lifting vectors. The l??wer
envelope ? consists of those points t = (v, Vn+i) whose height t'n+i over the
point v E N is minimal. Therefore, the objective function is defined to bE-
B = L1?v?1?+...+L?+1.v
The cost here is O(nm?2).
Step 4
Compute the Minkowski sum N, and the center of gravity g of N; g is used as an
initial monomial for the construction of Af. Then ?nqueue(V,g), z.e. enqiieue g
on the work queue V
The cost here is 0(h).
6
Step 5.
Loop:
If V is empty then break (goto 7).
Set v0 := dequeue(V).
Check which polytope points contribute t() the optimum sum for v0. This is done
by running the LP
v = v0,
Aj = 1, 1 ffi? < n t 1
Aij > 0
min(B)
The vertices appearing in the represetitatioll of v as a sum points from the Nj
can be read off from the coefficients whici? equal 1 in the representation ? =
The cost here is O((mn)3??) since there aL'( rnn variables Aij.
Step 6.
Compute the next row of the Newton matrix M:
step 6.1 Find the larg(st index i A <? vertex q?? contributin?,? to the rep
resentation of v0 from st(?I) 5.
step 6.2 Compute the displaced l;?tt'ce vector v' := v --H
step 6.3 Compute the product .rV' . fi, placing the indeterminate coeffi-
cients in the ?`?propnate columns of M.
step 6.4 For each colui?n j of Af fLit by a monomial from step 6.3, if the
lattice point Wj labehiig ??lumn j is not already processed or
enqueued, then enqueve( 17, wj).
step 6.5 GOTO 5 (Loop)
The cost here is linear in n and rn.
Step 7. Compute det(M).
The cost here is O(h?+1+? h?g2(!z)), using Berkowitz's algorithm [B],
where ? is the current best exponent for `natrix multiplication, and e > 0.
The overall cost is d??minated b? the cost of the determinant. Apart
from this, the dominant component of the w??rst case complexity comes from the
LP's occuring in the loop at step 5. The loop may execute as many as h times,
with each loop costing as much as O((rnr)3?5) steps for the LP.
7
5 Appendix A
Maple code for the Newton matrix algorithm. (?\Jarning: there are fUrward
references.)
with(linalg):
with(simplex):
# verts -- calculates array of exponents of monomials in poly
verts proc(poly, vars)
local d, n, vert;
d nops(vars);
n nopsCpoly);
vert			arrayCi. .d, 1. .n);
for I to n do
term op(i, poly);
for j to d do
vert[j, I]			degree(term, vars[j])
od
od;
vert
end: * verts
* randlin -- random linear functionals
n
randlin := proc(d)
8
dieC) od
local i,j,l,die;
die			rand(1. .1000);
1 arrayCi. .d):
for i to d do
l[i] array(1. .d-1);
for j to d--H1 do l[i][j]
od;
end: # randlin
It randvect -- random displacement `?ector of length n
randvect := proc(n)
local rproc;
rproc := rand(1. .1000);
r := arrayCi. .n)
for I to n do r[i] := convert(rproc()/1OOOO, float) od;
r
end: It randvect
#ItIt##It###It####It##It###It##It##It###It###It#It#####It########It######It#####
It make?eqns -- sets up LP for lower envelope
flflnnnnnnnnnnnntkntk?n???????
?###It#It#ItItItItItItItItItItItItItItItItItItItItItItItItItItItItItItItIt
make?eqns := proc(A, 1, d)
It A = array of matrices, each contains vertices as columns.
9
* 1 = random linear functional
* d = length of A = dimension - 1;
*
* Constructs the following input equations for LP package:
* objective = \sum?i l?i(\sum?j \lambda??i,j+ A??i,jJ),
* vertex eqns lhs = \sum??ij+ \lambda??ij? A??ijJ,
* conv. constr. = \sum \lambda??i,j1 = 1;
* where
*			1_i			= random linear functional,
* \lambda?+i,j+ = LP variables,
local C, cd, conveq, convsum, i, ipoly,
local lambda, nverts, objective, vertlhs;
objective := 0; * objective function
vertlhs := vector(d-1, 0); * lbs vertex equations
conveq := ?Y; * convexity constraints
nverts := dotp(vector(d,1), map(coldim, A));* tot. no. vert
for i to d do
ipoly :=
convsum := 0;
cd := coldim(ipoly);
lambda := array(1. .cd); * array for new variables
for j to cd do
lambda[j] := `lam'.i.'x'.j;
convsum := convsum + l?ubda[j];
od;
conveq := conveq union ?convsum =
C := multiply(ipoly, lambda);
vertlhs			add(vertlhs, C);
objective := objective + multiply(transposeCl[i]), C);
od;
[objective, conveq, vertlhs, nverts]
end: It make?eqns
It cog -- computes center of gravity
ItItItItItItItItItItItItItItItItItItItItItItItItItItItItItItItItItItItItItItItItItItItItit
cog := proc(ipoly, d)
It ipoly = array of exponent columns.
local cd, i, v;
cd := coldim(ipoly);
v := multiplyCipoly,
scalarmul(v, 1/cd)
end: It cog
convert(vector(cd, 1), matrix));
ItItItItItItItItItItItItItItItItItItItItItItItItItItItItItItItItItItItItItItItItItItItItItItItItItItItItItItItItItItItItItItItItIt
It Table of digit to num conversions
ItItItItItItIt#ItItItititItitItitItititItItItItItItItItItItItItItItItItItItItItItItItItItItItItItItItItItItItItItItItItItItItItIt
chars := 0:
chars[`0']
chars[`I']
chars[`2`3
chars[`3']
0:
1:
2:
3:
chars['4'] := 4:
chars['5'] := 5:
10
chars[ 6C]
chars[C7C]
chars['8']
6:
7:
8:
chars[C9C]			9:
# recode -- converts string `lamMx!?' into vector [M, N]
recode proc(z)
# converts string `l?mMxN' into vector [M, N]
local i, L, M, N, s, state;
end:
L := length(z);
M := 0;
N := 0;
state := 1;
for I from 4 to L do
5 := substring(z,i. .1);
if 5 = CxC then state := 2 fi;
if state = 1 then M := 1O*M + chars[s]
elif state = 2 then state := 3
elif state = 3 then N := 1O*N + chars[s] fi
od;
[M, N]
# opt?verts -- checks which polytope points contribute
to optimum sum for vert.
11
opt_verts procCedata, vert, d)
# edata = equations from make?eqns(),
# vert = vertex in Minkowski sum,
# d = dimension + 1.
local assigns, conveq, eps, eqns, ivert, j, nverts, objective,
optverts, verteq, vertlhs;
# Pick apart input from make?eqns()
objective := op(1, edata);# objective function
conveq op(2, edata); # convexity constraints
vertlhs := op(3, edata); # vertex eqns left hand sides
nverts := opC4, edata); # total number of input vertices
# Run LP to find optimal sum (on lower envelope) for vert
eps := 1.0 *
eqns := conveq;
for j to d-1 do
eqns := eqns union ?vertlh?[j] = vert[j,1J? od;
assigns := minimize(objective, eqns, NONNEGATIVE);
# find vertices appearing in the representation
optverts :=
for a in assigns do
if Cabs(rhs(a)-1.O) < eps) then
optverts := optverts union ?recode(lhs(a))1;
fi
od;
optverts
end: # opt?verts
12
*********nnnnnnnnnn
* compute?rows -- greedy algorithm for rows of Newton matrix
compute?rows proc(A, B, edata, v, delta, d)
*			A			= array of arrays ((d-1) X num vert.), input vert
*			B			= array of arrays like A plus interior points
*			edata			= eqn.'s defining lower hull for simplex package
*			v			= vertex in the Minkowski sum of the inputs ALi]
*			delta			= random small displacement vector
*			d			= dimension + 1
local cols, guide, i, imax, ipoly, jmax, overts, rows, vti, vt2;
rows
guide :=
cols := ?eval(v)>;
while not (eval(v) = f?) do * i.e. cont. while v is defined
print(v);
rows := rows union ?eval(v)?;
* lower hull vertices:
overts := opt?verts(edata, add(v,delta), d);
imax := 0;
jmax := 0;
for vti in overts do * find index of last polytope
if vti[1] > imax then * . contrib. vert. to opt. sum
imax := vtl[1];
jmax := vti[2]
13
fi
od;
guide guide union ?[eval(v),ima::,jmax]+;
vt2 add(v, col(A[imax], jmax), 1, -1);
ipoly B[imax];
for I to coldim(ipoly) do * find exp. in
vtl add(vt2, colCipoly, I)); * . mult. of B[imax]
if not vmem(vtl, cols) then
cols			cols union ?eval(vt1)> fi
od;
v (+; # undefine v, and then check
for vtl in cols do # . if any new rows are needed
if not vmem(vtl, rows) then v := eval(vtl); break fi
od
od;
guide
end: * compute rows
* newtonres -- computes Newton resultant matrix
newtonres := proc(A, B)
* A, B = array of arrays, ((d-1) X no. vert.), cols are vert.
* A = vertices only,
* B = all exponents in Newton polytopes
local d, delta, edata, i, ip, ipoly;
local ivert, j, k, M, msize, v, vtl, vt2;
d := rowdim(convert(A,matrix)); * no. polytopes = dim. - 1
delta := randvect(d-1); * rand. displacement vector
1 := randlin(d); # rand. linear functional
14
print('Computing data common to all vertex equations');
edata make?eqns(A, 1, d); # [obj, conveq, vertlhs]
print('greedy search for row indices');
v			cog(A[1], d);			# start at the ctr. grav.
for I from 2 to d do			of Minkowski sum
v add(v, cogCA[i], d)) od;
v			map(round, v);
guide compute?rows(A, B, edata, v, delta, d);
printC'constructing the matrix');
msize nops(guide);
guide convert(guide, list);
N array(1..msize, 1..msize)
for i to msize do
ivert guide[i];
ip ivert[2];
vti add(ivert[1], col(A[Ip], ivert[3]), 1, -1);
ipoly B[ip];
for j to msize do
vt2 add(guide[j][1], vti, 1, --H1);
M[i, j] 0;
for k to coldim(ipoly) do
if equal(vt2, submatrix(ipoly, 1. .d-1, [k])) then
M[i, j] `C'.ip.'x'.k
od;
M
15
fi
od
od
end: # mixed
# randhull -- approx. convex hull, sorting in random directions
randhull := proc(v,limit)
* v = input vector o? vertices
* limit = number of random directions to sort by
local d, i, j, k, max, maxindex, min, minindex, n, newc, rv, t;
local processed, unprocessed, vertlhs, conveq, convsum, lambda;
local work, worki, possible, sub, temp;
d := rowdim(v); * v = input ve?:tor of vertices, d = dim.
n := coldim(v); * n = numbers of vertices
processed :=
unprocessed :=
for i to n do unprocessed := uilprocessed union ?i? od;
for i to limit do
rv := randmatrix(1,d);
rv := scalarmul(rv, 1/norm(rv));
minindex := 1;
maxindex := 1;
min
min
max
multiply(rv, col(v, 1));
min[1];
eval(min);
16
for j from 2 to n do
t multiply(rv, col(v, j));
t
if t < min then
minindex
min			t
elif t > max then
maxindex			j;
max			t
od;
fi
processed processed union ?minindex, maxindex+;
unprocessed unprocessed minus ?minindex, maxindex?
od; # ends random iterations
# Now use LP to check other vertices
lambda			matrix(1, n);
for i to n do lambda[1, I]			o+`lam'.i od;
worki			unprocessed;
possible			processed;
work
while (work minus worki <> ??) or (worki minus work <> ?+) do
work worki;
for i in work do
temp			possible minus ?i+;
sub			convert(temp, list);
vertlhs			vector(d, 0); # vertex equation lhs
conveq			+?; # convex:ity constraint
17
convsum 0;
?or j in temp do
convsum convsum + lambda[1, j]
ad;
conveq := conveq union ?convsum = 1+;
vertlhs multiply(submatrix(v, 1. .d, sub),
transpose(submatrix(lambda, 1.1, sub)));
?or j to d do
conveq conveq union ?vertlhs[j, 13 = v[j, i]?
od;
if feasible(conveq, NONNEGATIVE) then
print(col(v,i) ?interior')
worki := worki minus ?iJ;
possible := possible minus +i+
else
possible := possible union fij
od
fi
od;
possible;
end: # randhull
# dotp -- dot product of vectors
dotp := proc(x, y)
multiply(transposeCx),
18
end: # dotp
# norm -- computes the 2 norm of a vector (as iXn matrix)
norm			proc(x)
local i,r;
r x[1,1]?2;
for I from 2 to coldim(x) do r r + x[1,i]?2 od;
convert(sqrt(r), float)
end: # norm
# vmem -- checks if el lies in (set or list) vset, using equal
itflfltkfltk?fltk???fl?????????
vinem := proc(el, vset)
local found, el2;
found := false;
for el2 in vset do
if equalCel, el2) then found := true; break fi od;
found
end: # vmem
# set2array -- convert set of row vectors to array of col vectors
19
set2array			proc(s)
n nops(s);
d nops(convert(op(1, 5), list));
transposeCarrayCi .n, 1. .d, convert(s, list)));
end: # set2array
20
6 References
[B] Berkowitz, 5. "On computing the determinant in small parallel time with
a small number of processors", Inform. Process. Lett., 18, (1984).
[Ber] Bernstein, D.N.: "The number of roots of a system of equations", F\inc-
tional Analysis and its Applications 9 (1975), 1--H4.
[Bet] Betke, U.: "Mixed volitmes of polytopes": Arcffiv der Matbematik 58
(1992), 388--H391.
[BF] Bonnesen, T., Fenchel, ?r.: "Theorie der Konvexen K6rper", Chelsea Pub-
lishing, New York (1948).
[CE] Canny, J., I. Emiris: "An Efficient Algorithm for the Sparse Mixed Re-
sultant", in Proc. AAECC-10, edited by G. Cohen, T. Mora and 0. Moreno",
Springer Lect. Notes in Comp. Sci. 263 (1993), pp. 89--H104.
[E] Eggleston, H.G.: "Convexity", Cambridge Tracts in Mathematics and Math-
ematical Physics 47, Camb. Univ. Press (1966).
[GKZ] Gelfand, I.M., M.M. Kapranov A. V. Zelevinsky: "Discriminants of poly-
nomials in several variables and triangitlations of Newton polytopes", Al?ei?ra 1
analiz (Lernngrad Math. J.) 2 (1990)1--H62.
[PS] Pedersen, P., B. Sturmfels: "Prodii??t formulas for resultants and Chow
forms", to appear in Mathem??tische Zeit?chrift.
21
