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; 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已经确定了几何对象，支持船体，表征了在多项式系统中出现的术语（与多项式系统相关的术语（这与相关的convex hull相关）。时间和空间的复杂性以及是否完全使用Cayley-Dixon结果配方计算结果，该配方受支持船体的控制。此外，Cayley-Dixon产生的配方的问题适应性特征似乎也归因于支撑船体的支持船体和术语中术语的非零系数的性质。 该项目将使用支持船体作为开发用于计算结果和调查符号数字方法的新方法的关键技术概念。由于混合使用的问题是混合使用的问题，因此将开发有效提取产生剂的技术来有效提取产生剂（多条件具有不同的术语子集）。通过表现良好的支撑船体近似多项式系统的支撑船体的几何方法，将很容易地计算出该船体。 将探索由支撑船体引导的透析产生矩阵的增量结构。预计这些方法将产生尺寸较小的结果矩阵，从而导致计算性能和解决现有方法范围之外的问题解决方案的显着提高。