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

在这个合作项目中，研究人员Sommese、Wsamer和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.