Collaborative Research: Numerical Algorithms and Software for Solving Polynomial Systems with Parameters

在这个合作项目中，研究人员Sommese、Wampler和Verschelde构建并实现了新的算法，以数值方式描述由参数化多项式方程系统定义的代数集。工作范围超出了传统问题，即在给定参数时寻求解决方案集，包括以特定方式改变解决方案组成部分性质的参数集的确定。特别有趣的是维数特别大的解集。诸如此类的问题，例如，过度约束机构的发现和分类，可以简化为计算具有参数的多项式系统的某些异常轨迹的不可约分解。然后将其简化为寻找有限个相关多项式系统的数值不可约分解。由于这导致了大型系统，因此开发了一种新的逐方程求解多项式系统的方法。为了解决重要的问题，算法在并行计算机上实现。解决一个多项式方程——找到多项式的根——是一个古老的问题，在整个科学和工程中以更复杂的形式反复出现。在涉及机械设计的应用中，寻找多项式方程系统的解只是更大方案中的一步：通过描述多项式系统的解集如何依赖于系统参数来达到更好的设计。例如，这个问题出现在工业机器人的设计中。研究人员发展了描述带参数多项式系统解集的新方法。这些方法有可能成为机器人和机构设计的标准工具。此外，这些方法有望对数值分析和计算机代数的研究领域产生更广泛的影响，特别是在努力为科学界提供解决数学问题的软件方面。这项工作的一个重要成果是基于这些新方法的公开可用软件，其接口便于更广泛的社区使用。通过解决科学和工程中出现的一些困难的多项式系统，该团队激发了对这些先进方法的兴趣，并为非专业人士提供了使用它们的说明。该项目包括与学生的合作和培训。

In this collaborative project the investigators Sommese,Wampler, and Verschelde construct and implement new algorithms tonumerically describe algebraic sets defined by systems ofparameterized polynomial equations. The scope of work goesbeyond conventional problems, where one seeks the solution setwhen the parameters are given, to include the determination ofparameter sets that change the nature of solution components in aspecified manner. Of special interest are solution sets whosedimension is exceptionally large. Problems such as these, e.g.,the discovery and classification of overconstrained mechanisms,can be reduced to computing the irreducible decomposition ofcertain exceptional loci of polynomial systems with parameters. This is then reduced to finding the numerical irreducibledecomposition of a finite number of associated polynomialsystems. As this leads to large systems, a newequation-by-equation approach to solving polynomial systems isdeveloped. To tackle nontrivial problems, the algorithms isimplemented on parallel computers. Solving a polynomial equation -- finding the roots of thepolynomial -- is an old problem that occurs over and over in morecomplicated forms throughout science and engineering. Inapplications involving mechanical design, finding the solution ofa system of polynomial equations is only one step in a largerscheme: to arrive at better designs by describing how the set ofsolutions of a polynomial system depends on parameters of thesystem. This problem arises in design of industrial robots, forexample. The investigators develop new methods for describingthe solution sets of polynomial systems with parameters. Themethods have the potential to become a standard tool in thedesign of robots and mechanisms. Furthermore, the methodspromise to have a wider impact on the research fields ofnumerical analysis and computer algebra, especially in effortsseeking to provide the scientific community with software tosolve mathematical problems. An important result of this work ispublicly available software based on these new methods, withinterfaces facilitating use by the wider community. By solvingsome difficult polynomial systems that arise in science andengineering, the team stimulates interest in these advancedmethods and provides illustration of their usage for thenonspecialist. The project includes collaboration with andtraining of students.