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.
Polynomial systems can be used to model problems arising in many application domains, including engineering systems,cyber-physical systems, drug design, control theory, software verification, etc. This project investigated the structure of the solution space of such polynomial systems using the generalized Dixon multivariate resultant method and Groebner basis techniques. One advantage of analyzing parametric polynomial systems is that their behavior can be analyzed for a wide class of parameter values, thus obviating the need to repeatedly study the polynomial system for different specific values of parameters. New algorithms were developed and implemented to solve parametric polynomial systems and conditions were identified on parameters in a parametric polynomial system under which the polynomial system has common solutions. Parameter space can be partitioned depending upon different behavior of the polynomial system and the associated solution space. A particular focus was on the cases when problems can be formulated as a composition of two polynomial systems, in which case the complexity of problems can be substantially reduced by exploiting their structure. Software developed during the project was made available to other researchers for experimentation. Graduate students were trained at the University of New Mexico(UNM). Collaborations with researchers at Peking University and the Institute of Mathemaics and Systems Scieces of the Chinese Academy of Sciences were developed. A graduate course at UNM incorporated the research outcomes of this project.
