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结式对于求解实际应用中出现的一类参数多项式系统是非常有效的.一个特别有吸引力的特点，这制定是它的问题适应性：它隐含地利用稀疏结构和非genericity的多项式system.Kapur和Chtcherba确定了一个几何对象，支持船体，表征出现在多项式系统（这是相关的凸船体）作为一个强大的概念。时间和空间复杂度以及是否使用Cayley-Dixon合成公式精确计算合成，都由支持船体决定。此外，Cayley-Dixon合成公式的问题适应性特征似乎也是由于支持船体和支持船体中项的非零系数的性质。 该项目将使用支撑船体作为开发计算结果的新方法和研究符号-数值方法的关键技术概念。技术将被开发，以有效地提取混合非通用多项式系统（多项式有不同的子集的条款），因为应用程序所产生的问题是混合的结果。几何方法，近似的支持船体的多项式系统的良好性能的支持壳，其结果可以很容易地计算，将开发。 将探索由支持壳引导的透析合成矩阵的增量构建。这些方法预计将产生小得多的大小的结果矩阵，导致显着的增益在计算性能和解决方案的问题超出了现有的方法。