Approximate Polynomial System Solving and Generic Groebner Bases

符号计算是精确的——计算结果保证是正确的。这是有代价的——计算有时非常缓慢或占用大量内存；有时，计算的正确结果太大而无法使用。另一方面，数值计算更快，并且，在条件良好的输入问题实例中，人们可以期望在反向误差分析的意义上得到正确的解。数值方法在解决科学和工程中广泛的计算问题方面非常成功。然而，在某些情况下，这种方法并不完全令人满意。在几何建模和运动学等领域中出现的多项式系统求解的几个应用中，人们需要给定问题实例的精确答案，而不是邻近实例的精确答案。另一方面，在许多应用问题中，输入多项式系统不是精确已知的，而是在很小的误差范围内。这就改变了可以向求解者提出的问题的性质。例如，一个问题，如“一个给定的多项式方程组是否有一个复数根r?”“变为”是否给定的多项式方程组靠近一个具有复数根r的方程组？以某种适当的方式接近。现有的符号/数值算法无法很好地处理这类问题。在这个框架中需要解决的一些问题是：在存在小输入误差的情况下多项式方程/不等式系统的解的特征；设计求解精度有限（或自适应）的多项式系统的有效算法；了解影响这些算法稳定性的因素；研究多项式系统求解中有时独立的符号相位和数值相位的排列方法，以最大限度地利用彼此的优势。本课题研究了在上述框架下多项式系统求解的一些具体实例，特别关注了近似多项式最大公约数和几个特殊的多项式系统族。研究了一种新的参数最小化方法，并将其应用于近似GCD问题及其几种变体。引入了一般Groebner基的概念，并结合特征值计算，研究了它们在近似求解某些特殊多项式系统族中的有效性。一般格罗布纳碱基的研究为格罗布纳碱基理论中一些众所周知的尚未解决的问题提供了新的思路。新技术将应用于几何建模和运动学中出现的多项式系统。

Symbolic computation is exact -- the result of a computation is guaranteed correct. This comes at a cost -- the computations are sometimes very slow and/or memory intensive; at times, the correct results of a computation are too huge to be of use. Numerical computation, on the other hand, is faster, and, on well conditioned input problem instances, one can expect correct solutions in the sense of backward error analysis. The numerical approach has been very successful in solving a wide spectrum of computational problems in science and engineering. However, there are situations where this approach is not completely satisfactory. In several applications of polynomial system solving arising in areas such as geometric modeling and kinematics, one needs the exact answer to a given problem instance and not to a near-by instance. On the flip side, in many application problems, the input polynomial system is not known exactly but to within small error bounds. This changes the nature of questions that can be asked of a solver. For instance, a question such as ``does a given system of polynomial equations have a root of multiplicity r?'' changes to ``is the given system of polynomial equations near a system that has a root of multiplicity r?'' with respect to some appropriate measure of nearness. Existing symbolic/numeric algorithms are not equipped to handle such questions well. Some of the issues that need to be addressed in this framework are: characterization of the solutions to a system of polynomial equations/inequalities in the presence of small input errors; design of efficient algorithms for solving polynomial systems that work in limited (or adaptive) precision; understanding the factors that affect the stability of these algorithms; investigation of ways to arrange the sometimes independent symbolic phase and numerical phase in polynomial system solving to take maximum advantage of the strengths of each other. This project investigates some specific instance s of polynomial system solving in the above framework with particular focus on approximate polynomial greatest common divisors and several special families of systems of polynomials. A new parametric minimization technique is being studied and applied to the approximate GCD problem and several of its variants. The concept of generic Groebner bases is introduced and in combination with eigenvalue computations, their effectiveness in the approximate solving of certain special families of polynomial systems is being investigated. The investigation of generic Groebner bases throws fresh light on some well-known unresolved issues in Groebner base theory. The new techniques will be applied to polynomial systems arising in geometric modeling and kinematics.