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

应用领域中的许多问题，包括工程设计、机器人、逆运动学、图形学、实体建模、CAD-CAM设计、几何构造、分子生物学、药物设计和控制理论，都可以使用具有多变量的参数多项式系统建模。然而，求解多元多项式系统，尤其是符号化的，是一个主要的挑战。无论何时成功，符号方法都比数值方法有相当大的优势，因为符号解只需计算一次，而数值解必须在每次参数值变化时计算。实验和理论分析表明，Kapur、Saxena和Yang提出的广义Cayley-Dixon结式对于实际应用中出现的大量这类参数多项式系统的求解是非常有效的。这个公式的一个特别吸引人的特点是它的问题适应性：它隐含地利用了多项式系统的稀疏结构和非泛型。Kapur和Chtcherba已经确定了一个几何对象，支撑壳，将多项式系统（与相关的凸壳相关）中出现的术语描述为一个强大的概念。时间和空间的复杂性，以及是否精确计算的结果是使用凯利-狄克逊合力公式，是由支持船体。此外，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.