Reality, exactness, and computation in numerical algebraic geometry

数值代数几何中的真实性、精确性和计算

• 批准号: 0914674
• 负责人: Daniel Bates
• 金额: $ 15.96万
• 依托单位: Colorado State University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2009
• 资助国家: 美国
• 起止时间: 2009-08-01 至 2012-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0914674&HistoricalAwards=false
• 关键词: Reality; exactness; computation; numerical; algebraic

This award is funded under the American Recovery and Reinvestment Act of 2009 (Public Law 111-5).The methods of numerical algebraic geometry extend the reach of algebraic geometry to problems for which existing symbolic methods are not well suited, e.g., due to the number of variables or the inexactness of the coefficients. The value of these methods is continuing to gain recognition. For example, the algebraic geometry software packages Macaulay 2 and CoCoA are both actively developing either new homotopy modules or interfaces to existing numerical software, such as Bertini and PHCpack. Despite the benefits of these numerical methods (e.g., parallelizability), there are a few drawbacks. For example, to find the real isolated solutions of a polynomial system using homotopy methods, one must first produce all complex isolated solutions and then sort out those with imaginary part below a pre-chosen tolerance. Also, one major benefit coming from numerical algebraic geometry is that it is simple to produce approximations of many generic points on any given irreducible component of an algebraic set. However, there is currently no way to recover exact defining equations for the component. This project has two directions. In one, a new set of techniques, based on Gale duality and the Khovanskii-Rolle theorem, for finding only the real solutions of polynomial systems will be developed. In the other, the simplicity of finding generic points on algebraic sets via numerical methods will be exploited. The latter direction will include work on recovering exact defining equations via lattice basis reduction techniques such as LLL or PSLQ. Both directions are expected to result in new, freely available software.Polynomial systems of equations are ubiquitous throughout mathematics, science, and engineering. An entire mathematical field - algebraic geometry - grew out of the need to find solutions to these sorts of equations. Until the 1960s, though, there was no known general technique for solving such systems of equations. However, the methods developed at that point require too much memory to be effective except for relatively small problems. More recently developed methods - the numerical methods of Sommese, Verschelde, and Wampler, now collectively known as numerical algebraic geometry - allow for the solution of much larger polynomial systems, opening the application of algebraic geometry methods to a wider class of problems. However, there are still drawbacks to these numerical methods. The goals of this project include addressing two of these drawbacks. In particular, the PI will work on developing efficient methods to find only those solutions that are of interest in real-world applications (i.e., real solutions rather than complex solutions) and on recovering valuable exact data from the approximate data that is provided as the output of these powerful new numerical methods.

该奖项是根据2009年美国复苏和再投资法案（公法111-5）资助的。数值代数几何的方法将代数几何的范围扩展到现有符号方法不太适合的问题，例如，由于变量的数量或系数的不精确性。 这些方法的价值正在不断得到承认。 例如，代数几何软件包Macaulay 2和可可都在积极开发新的同伦模块或现有数值软件的接口，如Bertini和PHCPack。 尽管这些数值方法有好处（例如，可并行性），但是存在一些缺点。 例如，要用同伦方法求一个多项式系统的真实的孤立解，首先必须求出所有的复孤立解，然后选出那些虚部小于预定容差的复孤立解。 此外，数值代数几何的一个主要好处是，它可以简单地产生代数集合的任何给定的不可约分量上的许多通用点的近似。 然而，目前没有办法恢复组件的精确定义方程。 这个项目有两个方向。 在一个，一套新的技术，盖尔对偶和Khovanskiii-Rolle定理的基础上，只找到真实的解决方案的多项式系统将开发。 另一方面，将利用通过数值方法在代数集上找到通用点的简单性。 后一个方向将包括通过LLL或PSLQ等格基约简技术恢复精确定义方程的工作。 这两个方向都有望产生新的、免费可用的软件。多项式方程组在数学、科学和工程中无处不在。 整个数学领域--代数几何--就是从寻找这类方程的解的需要中产生的。 然而，直到20世纪60年代，还没有已知的通用技术来求解这样的方程组。 然而，在这一点上开发的方法需要太多的内存，除了相对较小的问题是有效的。 最近开发的方法-数值方法的Sommese，Verschelde，和Wampler，现在统称为数值代数几何-允许解决更大的多项式系统，开放的应用代数几何方法，以更广泛的一类问题。 然而，这些数值方法仍然存在缺点。 该项目的目标包括解决其中两个缺点。 特别是，PI将致力于开发有效的方法，以仅找到那些在现实世界应用中感兴趣的解决方案（即，真实的解而不是复杂的解）和从作为这些强大的新数值方法的输出而提供的近似数据中恢复有价值的精确数据。