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 和CoCoA 都在积极开发新的同伦模块或现有数值软件（例如Bertini 和PHCpack）的接口。 尽管这些数值方法有很多优点（例如，可并行性），但也存在一些缺点。 例如，要使用同伦方法找到多项式系统的实孤立解，必须首先产生所有复数孤立解，然后将虚部低于预先选择的容差的那些解分类出来。 此外，数值代数几何的一个主要好处是，可以很容易地在代数集的任何给定的不可约分量上生成许多通用点的近似值。 然而，目前还没有办法恢复该组件的精确定义方程。 这个项目有两个方向。 其中，将开发一套基于盖尔对偶性和 Khovanskii-Rolle 定理的新技术，用于仅找到多项式系统的实解。 另一方面，将利用通过数值方法在代数集上寻找通用点的简单性。 后一个方向将包括通过 LLL 或 PSLQ 等晶格基约简技术恢复精确定义方程。 预计这两个方向都会产生新的、免费的软件。多项式方程组在数学、科学和工程中无处不在。 整个数学领域——代数几何——源于寻找这类方程的解的需要。 然而，直到 20 世纪 60 年代，还没有已知的通用技术来求解此类方程组。 然而，当时开发的方法需要太多的内存才能有效，除非是相对较小的问题。 最近开发的方法 - Sommese、Verschelde 和 Wampler 的数值方法，现在统称为数值代数几何 - 允许求解更大的多项式系统，从而将代数几何方法应用于更广泛的问题。 然而，这些数值方法仍然存在缺陷。 该项目的目标包括解决其中两个缺点。 特别是，PI 将致力于开发有效的方法，以仅找到那些在实际应用中感兴趣的解决方案（即真实的解决方案而不是复杂的解决方案），并从作为提供的近似数据中恢复有价值的精确数据。这些强大的新数值方法的输出。