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

合作研究：求解带参数多项式系统的数值算法和软件

• 批准号: 0410036
• 负责人: Jan Verschelde
• 金额: $ 8.09万
• 依托单位: University of Illinois at Chicago
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2004
• 资助国家: 美国
• 起止时间: 2004-09-15 至 2008-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0410036&HistoricalAwards=false
• 关键词: Collaborative; Research; Numerical; Algorithms; Software

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.

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