Research on polynomial systems has a wide range of applications in such
diverse
areas as algebraic geometry, CAD/CAM, computer graphics, computer vision,
solid
modeling, robotics, virtual reality, and etc.
Resultants are one of the most
powerful of these computational techniques.
For a given n polynomials f1, … , fn
in n variables x1, … , xn,
the vanishing of the multiresultant Ri(xi)=
det Mi(xi),
where Mi denotes a multiresultant matrix
and generally is a large sparse matrix, is a necessary condition on the ith
component of any zero point x of f(x).
Eugene Allgower, Kurt Georg and Rick Miranda use this condition to
determining
the real solution to polynomial system. Since the multiresultant matrix
Mi is large sparse,
Ri(xi) is a
polynomial of very high degree in the xi, the calculation
of
the determinant of the resultant is an unstable problem, thus they replace
the
unstable calculation of determinant by a stable minimization problem:
min||u||=1||Mi(xi)u||2 =
0.
Then they use a conjugate gradient method constrained on the unit
sphere.
The above minimization problem is equivalent to the minimum eigenvalue
problem
of the semidefinite matrix Mi(xi)*
Mi(xi).
So in this paper, I use Lanczos method to this minimum eigenvalue problem.
Lanczos method is a powerful tool for computing eigenvalues of large, spare
matrices, the information about extremal eigenvalues of given matrix tends
to
emerge long before the tridiagonalization is complete. Therefore, it becomes
very useful when only a few of largest or smallest eigenvalues are
desired.
In the method of Allgower etc., there is a possibility that the resultant
matrix is always singular for any data of variables, thus the minimal
eigenvalue
can not produce any information of solution. To decrease this possibility, I
modify the structure of the S set, which is used to construct the row of
multiresultant matrix Mi, then the multiresultant matrix
Mi is extended to a rectangle matrix Ni,
whose column size is the same as Mi, and determine the
solution via the minimum eigenvalue of semidefinite matrix
Ni(xi)* Ni(xi).