## 氏名: 鮑 忠忠 (289934222)

## 論文題目: Resultant method for real solutions of real polynomial system with Lanczos
method

実多項式系の実解に対するランチョス法を用いた終結式法

## 論文概要

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 *f*_{1}, … , f_{n}
in *n* variables* x*_{1}, … , x_{n},
the vanishing of the multiresultant *R*_{i}(x_{i})=
det* M*_{i}(x_{i}),
where *M*_{i} 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
*M*_{i} is large sparse,
*R*_{i}(x_{i}) is a
polynomial of very high degree in the *x*_{i}, 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}||*M*_{i}(x_{i})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 *M*_{i}(*x*_{i})*
*M*_{i}(*x*_{i}).
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 *M*_{i}, then the multiresultant matrix
*M*_{i} is extended to a rectangle matrix *N*_{i},
whose column size is the same as *M*_{i}, and determine the
solution via the minimum eigenvalue of semidefinite matrix
*N*_{i}(x_{i})* N_{i}(x_{i}).

目次に戻る

提出時刻：2001/02/08 17:45:35