Analyzing Polynomial Systems using Cayley-Dixon Resultant Matrices based on Support Hull

使用基于支撑船体的 Cayley-Dixon 结果矩阵分析多项式系统

• 批准号: 0729097
• 负责人: Deepak Kapur
• 金额: $ 21.2万
• 依托单位: University of New Mexico
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2008
• 资助国家: 美国
• 起止时间: 2008-02-15 至 2013-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0729097&HistoricalAwards=false
• 关键词: Analyzing; Polynomial; Systems; using; Cayley

Many problems in application domains including engineering design, robotics, inverse kinematics, graphics, solid modeling, CAD-CAM design, geometric construction, molecular biology, drug-design, and control theory, can be modeled using parametric polynomial systems with many variables. Solving multivariate polynomial systems, especially symbolically, is however a major challenge. Whenever successful, symbolic methods have considerable advantage over numerical methods, since a symbolic solution has to be computed only once whereas numerical solutions must be computed every time parameter values change. Experimental and theoretical analyses indicate that the generalized Cayley-Dixon resultant formulation developed by Kapur, Saxena and Yang is very effective in practice for solving a large class of such parametric polynomial systems arising in practical applications. A particularly attractive feature of this formulation is its problem-adaptiveness: it implicitly exploits the sparse structure and non-genericity of a polynomial system.Kapur and Chtcherba have identified a geometric object, the support hull, characterizing the terms appearing in a polynomial system (which is related to the associated convex hull) as a powerful concept. Time and space complexity as well as whether the resultant is computed exactly or not using the Cayley-Dixon resultant formulation, are governed by the support hull. Further, the problem-adaptiveness feature of the Cayley-Dixon resultant formulation appears also to be due to the support hull and the nature of the nonzero coefficients of the terms in the support hull. This project will use the support hull as the key technical concept for developing new methods for computing resultants and investigating symbolic-numeric methods. Techniques will be developed to extract resultants efficiently for mixed non-generic polynomial systems (where polynomials have different subsets of terms) since problems arising from applications are mixed. Geometric methods that approximate the support hull of a polynomial system by well behaved support hulls for which the resultant can be computed easily, will be developed. Incremental construction of dialytic resultant matrices guided by support hulls will be explored. These approaches are expected to generate resultant matrices of much smaller size, leading to significant gains in computational performance and solutions of problems beyond the reach of existing methods.

应用领域中的许多问题，包括工程设计、机器人、逆运动学、图形、实体建模、CAD-CAM 设计、几何构造、分子生物学、药物设计和控制理论，都可以使用具有许多变量的参数多项式系统进行建模。 然而，求解多元多项式系统，尤其是象征性的，是一个重大挑战。只要成功，符号方法就比数值方法具有相当大的优势，因为符号解只需计算一次，而数值解必须在每次参数值变化时计算。实验和理论分析表明，Kapur、Saxena 和 Yang 开发的广义 Cayley-Dixon 合成公式对于求解实际应用中出现的一大类参数多项式系统非常有效。该公式的一个特别吸引人的特征是它的问题适应性：它隐式地利用了多项式系统的稀疏结构和非通用性。Kapur 和 Chtcherba 已经识别了一个几何对象，即支撑船体，它描述了多项式系统中出现的项（这与相关的凸包有关）作为一个强大的概念。时间和空间复杂度以及结果是否使用 Cayley-Dixon 合成公式精确计算，均由支撑船体控制。此外，Cayley-Dixon 合成公式的问题适应性特征似乎也是由于支撑壳和支撑壳中项的非零系数的性质所致。 该项目将使用支撑船体作为关键技术概念，开发计算结果的新方法和研究符号数值方法。由于应用程序产生的问题是混合的，因此将开发技术来有效地提取混合非通用多项式系统（其中多项式具有不同的项子集）的结果。将开发通过性能良好的支撑壳来近似多项式系统的支撑壳的几何方法，其结果可以容易地计算。 将探索由支撑船体引导的透析合成基质的增量构建。这些方法预计将生成尺寸小得多的结果矩阵，从而显着提高计算性能并解决现有方法无法解决的问题。