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

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

• 批准号: 0410047
• 负责人: Andrew Sommese
• 金额: --
• 依托单位: University of Notre Dame
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2004
• 资助国家: 美国
• 起止时间: 2004-09-15 至 2009-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0410047&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 构建并实现了新算法，以数值方式描述由参数化多项式方程组定义的代数集。 工作范围超出了传统问题，即在给定参数时寻求解决方案集，包括确定以指定方式改变解决方案组件的性质的参数集。 特别令人感兴趣的是尺寸异常大的解决方案集。 诸如此类的问题，例如过度约束机制的发现和分类，可以简化为计算带有参数的多项式系统的某些异常轨迹的不可约分解。然后将其简化为寻找有限数量的相关多项式系统的数值不可约分解。 由于这会导致大型系统，因此开发了一种新的逐方程方法来求解多项式系统。 为了解决重要问题，算法在并行计算机上实现。 求解多项式方程——找到多项式的根——是一个老问题，在整个科学和工程领域以更复杂的形式反复出现。 在涉及机械设计的应用中，找到多项式方程组的解只是更大方案中的一个步骤：通过描述多项式系统的一组解如何依赖于系统的参数来获得更好的设计。 例如，这个问题出现在工业机器人的设计中。 研究人员开发了新的方法来描述带有参数的多项式系统的解集。 这些方法有可能成为机器人和机构设计的标准工具。 此外，这些方法有望对数值分析和计算机代数的研究领域产生更广泛的影响，特别是在寻求为科学界提供解决数学问题的软件方面。 这项工作的一个重要成果是基于这些新方法的公开软件，其界面便于更广泛的社区使用。 通过解决科学和工程中出现的一些困难的多项式系统，该团队激发了对这些先进方法的兴趣，并为非专业人士提供了它们的用法说明。 该项目包括与学生的合作和培训。