Let us consider a system of n+1 generic polynomials
where
- =(ci,j) are parameters
- x is a point of the projective variety X Ì PN,
of dimension n,
- The vector functions
Li(x)=(yi,j(x))j=0,...,ki
are regular functions on X independent (see [Har92]) of the
parameters .
The elimination problem consists, in this case, in finding some
necessary and sufficient conditions on the parameters =(ci,j)
such that the equations f0=0, ...,
fn=0 have a common root in X.
In the classical case, Li(x) is the vector of all the
monomials of degree di and X= Pn. The necessary and
sufficient condition on the parameters =(ci,j) such that the
homogeneous polynomials f0,...,fn have a common root in
X= Pn is Res Pn(f0,...,fn)=0 where
Res Pn is the classical projective resultant.
From a geometric point of view, we are looking for the set of parameters
=(ci,j) such that there exists x in X with Sj ci,j
yi,j (x) =0 for i=0,...,n. This means that is the
projection of the point (,x) of the incidence variety
| WX ={(,x) in P |
|
|
× ··· × P |
|
|
× X
; |
|
ci,j yi,j(x)=0 ;
i=0,...,n}.
|
We denote by
the two natural projections. The image of WX by p 1 is the
set of parameters for which the system has a root. The image by
p 2 of a point of WX is a root in X of the associated
system. Thus we have the following definition (see [ElMbzt98]):
Definition 0.1 We denote Z=p1(WX). If Z is a hypersurface, then its
equation (unique up to a scalar) is called the resultant of
f0,...,fn over X. It is denoted by ResX(f0,...,fn).
In order to be in this case, we impose the following conditions (see [ElMo96]):
Hypotheses 0.2
- X is a projective irreducible variety.
- The regular functions Li, i=0, ...,n do not vanish
identically at a point of X.
- For generic values of , the system f0,...,fn
has no common root in X, and n of these equations (say
f1,...,fn) have a finite number of common solutions.
Thus, the system f0= ··· = fn=0 has a solution in X
if and only if ResX(f0,...,fn)=0. This generalizes,
under the conditions X, the definition of the classical
resultant over Pn to other projective varieties.
The approaches to compute effectively the resultant are based on
matrix constructions whose determinant will give the
resultant or a non-trivial multiple. These resultant matrices can be
classified into two main families: the class of Sylvester matrices, which
generalize the construction of Sylvester (1835, see
[Sylvester]) to the multivariate case and the class of Bezoutian matrices generalizing the construction of E. Bézout
(1779, see [Bez79]) to the multivariate case.
1 Sylvester-like matrices
We consider the construction due to Macaulay of a resultant matrix for
n+1 polynomials f0...,fn, in n variables, which generalizes the Sylvester map for two polynomials in one variable.
Let V0, ..., Vn, n+1 vector spaces generated by xEi={xa, a in Ei}, where Ei is the set of exponents specified hereafter,
Ei = {bi,1, bi,2,...}.
Let V be the vector space generated by all the monomials of the polynomials fixbi for bi in Ei. This set of monomials is denoted by xF = (xb)b in F. We define the following map :
|
S : V0 × ··· × Vn |
-> |
V |
(1) |
|
(q0, ..., qn) |
-> |
|
|
The matrix S associated to S in the monomial basis of V0 × ··· × Vn and V is
|
|
| |
|
|
|
é
ê
ê
ê
ê
ê
ê
ê
ë |
|
| · |
|
|
· |
|
| · |
|
|
· |
|
|
|
··· |
··· ··· ··· |
|
··· |
| · |
|
|
· |
|
| · |
|
|
· |
|
|
|
ù
ú
ú
ú
ú
ú
ú
ú
û |
.
|
|
|
In this matrix of type Macaulay, if d0, ... ,dn are the degrees of
the polynomials f0, ... ,fn, and n = d0+ ... + dn
- n, the set xF is the set of all the monomials of degree £ n
in the variables x1, ... ,xn and Ei is the subset of the
monomials of degree n - di. We can check that the hypothesis
X are well respected.
2 Projective resultant
We consider the construction due to Macaulay of a resultant matrix for
n+1 polynomials f0...,fn, in n variables, which generalizes
the Sylvester map for two polynomials in one variable.
Let V0, ..., Vn, n+1 vector spaces generated by
xEi={xa, a in Ei}, where Ei is the set of
exponents specified hereafter,
Ei = {bi,1, bi,2,...}.
Let V be the vector space generated by all the monomials of the
polynomials fixbi for bi in Ei. This set
of monomials is denoted by xF = (xb
)b in F. We define the map (X) :
|
S : V0 × ··· × Vn |
-> |
V |
(2) |
|
(q0, ..., qn) |
-> |
|
|
The matrix S associated to S in the monomial basis of
V0 × ··· × V
n and V is
|
|
| |
|
|
|
é
ê
ê
ê
ê
ê
ê
ê
ë |
|
| · |
|
|
· |
|
| · |
|
|
· |
|
|
|
··· |
··· ··· ··· |
|
··· |
| · |
|
|
· |
|
| · |
|
|
· |
|
|
|
ù
ú
ú
ú
ú
ú
ú
ú
û |
.
|
|
|
In this Macaulay matrix, if d0, ... ,dn are the degrees
of the polynomials f0, ... ,fn, and n = d0+ ... +
dn - n, the set xF is the set of all the monomials of degree
£ n in the variables x1, ... ,xn and Ei is the
subset of the monomials of degree n - di. We can check that the
hypothesis X are well respected. In this resultant construction,
it may happen that for specific values of the coefficients of the input
polynomials, the matrix D become singular. In this case another
construction must be applied.
Here is an example of such a matrix of size 792× 792, coming from the
autocalibration problem of a camera with Kruppa's equations:
file=../help/kruppa.ps, height=10cm,width=10cm
mpoly/resultant/Macaulay.H
unsigned int SizeOfS(unsigned int n, unsigned int k)
Compute the size of the Sylvester-like matrix.
template< class POL>
int Choose(int k, int n, POL & ML)
Return the polynomial, which is the sum of all monomials in n variables
of degree k, with coefficient 1. The output is stored in the variable ML.
template< class R, class L>
VAL< R*> Macaulay(const L & f, char z='N')
Construction of the Macaulay matrix, for the projective resultant of n+1
polynomials in n variables.
It will be of minimal degree in the coefficients
of f[0], that is the product of the degree of f[1], ..., f[n].
The order choosed to sort the monomials indexing the rows of the matrix
is the reverse of the order associated to the polynomials of the
sequence f. L is the type of a sequence of polynomials.
R specifies the type of the output matrix. For instance, Macaulay< Mat> (f);
will output a matrix of type VAL< Mat*> . It should have a constructor
Mat(m,n) which allocates the necessary place to store a n× m
matrix and the method Mat::operator()(size_type i, size_type j).
If z is 'T', the transposed matrix is constructed.
template< class R, class L>
VAL< R*> Macaulay(const L & f, unsigned int nu, unsigned int nv, char z='T')
Construction of the matrix of all multiples of degree nu of all the polynomials f[0], f[1], ..., f[n].
The argument nv is the number of variables.
The order choosed to sort the monomials indexing the rows of the matrix
is the reverse order associated to the polynomials of the sequence f.
The second template argument specifies the type of the
output matrix. For instance, Macaulay< Mat> (f);
will output a VAL< Mat*> .
The usual Macaulay matrix is a submatrix of this one, for
n= Si=0n deg(fi) -n +1.
3 Toric resultant
I. Emiris
We define the Newton polytope of f in S as the convex hull of
the set AÌ Zn of all monomial exponents corresponding
to nonzero coefficients is the support of f.
The mixed volume of polytopes Q1,..., Qn is the coefficient of
l1··· ln in the volume of
Q=l1 Q1+l2 Q2 +··· + ln Qn.
An interesting fact is that the mixed volume MV(f1,...,fn) counts the
(generic) number of roots of Z(f1,...,fn) in ( K*)n
[Be].
This bound is known as the BKK bound to underline the contributions
of Kushnirenko and Khovanskii in its development and proof [Ku76, Kh78].
Theorem 3.1
Let f1,...,fn in K[x1,x-1,..., xn,xn-1] with Newton
polytopes Q1,...,Qn.
The number of isolated common zeros in ( K*)n, multiplicities counted,
is either infinite, or does not exceed
MV(Q1, ...,Qn), where K is the algebraic closure of K.
For the construction of Toric Resultant matrices, we consider n+1 Laurent
polynomials f0,...,fnin
K[x,x-1], with support respectively in the polytopes
A1,...,An+1.
Here is a short description of the algorithm used (see [CaEm93] for more
details):
Construction of the Newton matrices.
- Subdivide the monomials of the Minkowski sum Q=A0 + ···
An into cells (mixed subdivision).
- Decompose each of these cells as a sum ai0 + Bi0 of a
vertex of some Ai0 and faces of the other polytopes Ai,
i ¹ i0. This gives a partition of xB as an union of sets
xai0xB (to be compared with the partition of xB into the
union of the sets xidi xBi in the previous
section).
- For all these cells, replace the monomial xai0 by the
polynomial fi0 and construct the corresponding coefficient matrix of
all these polynomials.
This matrix is also the matrix of the following map:
Here are the functions connecting the C-implementation for mixed volume
and toric resultant of I.Z. Emiris.
template< class POL>
int MixedVolume (const list< POL> & l, int numvars)
Input a list of polynomials, and the number of variables.
Output the mixed volume of the polytopes for the variables 1..numvars.
template< class POL> inline int MixedVolume (const list< POL> & l)
Mixed Volume. The number of variables is supposed to be the size of the list.
template < class R,class POL>
VAL< R*> ToricResultant(const list< POL> & l)
Compute the Toric resultant by the incremental algorithm [].
4 Bezoutian resultant
Here we recall some definitions and properties of the Bezoutian theory
(for more details, see [CaMo96, ElMo96]).
To the set of variables x we add a new set of variables
y=(y1,...,yn) and we denote x(0)=x,
x(1)=(y1,x2,...,xn), ..., x(n)=y.
For a polynomial q in R, we define
qi(p)=p(x(i))-p(x(i-1))/ yi-xi.
Definition 4.1 For n+1 polynomials f=(f0, f1,...,fn) in R, we call
Bezoutian of f0,f1,...,fn the polynomial in x et y
def
ined by:
|
Q(f0,f1, ..., fn) = Qf(f0)
= det |
æ
ç
ç
ç
ç
è |
|
| f0(x) |
q1(f0) |
··· |
qn(f0) |
·
·
· |
·
·
· |
|
·
·
· |
| fn(x) |
q1(fn) |
··· |
qn(fn)
|
|
ö
÷
÷
÷
÷
ø |
= |
|
qi,jf
x |
|
|
y |
|
|
,
(3) |
It is a polynomial of degree at most Si=0ndeg(fi)-n.
In the monomial basis xa and yb, Qf
can be written:
Definition 4.2 the set of monomials xa (resp. yb) is called the
x-support (resp. y-support) of Qf(f0).
Let the following map:
Definition 4.3 We denote by Bf0(f), the matrix of
Ff(f0) from the dual basis of R# into the monomial
basis (xa) of R. This matrix is the Bezoutian matrix
of the polynomials f0, f1,...,fn.
mpoly/resultant/MBezout.H
template < class POL> inline
POL MBezout(const list< POL> & l, typename POL::monom_t::index_t c=0)
Compute the polynomial in the two set variables, which is the the
determinant associated with the list of polynomials l. The c
first variables are considered as parameters. The n next variables
(where n is the length of l-1) are the variables x and the next
n variables are the y.
template < class POL, class RM>
VAL< RM*> DeltaOf(const POL & P, int l0, int l1, int l2, RM M)
Compute the matrix associated with the polynomial p, assuming the variables
up to l0 are hidden, the first block of variables is of size l1 and
the second one of size l2. The monomials in the first block of variables
are indexing the rows, the monomials in the second block of variables are
indexing the columns. The entries of this matrix are polynomials
in the variables x0,..xl0. The type RM specifies the
the type of the output matrix.