Approximate Polynomial System Solving and Generic Groebner Bases

近似多项式系统求解和通用 Groebner 基

• 批准号: 9712219
• 负责人: Lakshman Yagati
• 金额: $ 7.58万
• 依托单位: Drexel University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1997
• 资助国家: 美国
• 起止时间: 1997-08-15 至 2000-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9712219&HistoricalAwards=false
• 关键词: Approximate; Polynomial; System; Solving; Generic

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.

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