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

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

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.