Reality, exactness, and computation in numerical algebraic geometry

该奖项由2009年美国复苏和再投资法案(公共法律111-5)资助。数值代数几何方法将代数几何的范围扩展到现有符号方法不能很好地解决的问题，例如，由于变量数量或系数的不精确。这些方法的价值正在继续得到认可。例如，代数几何软件包Macaulay 2和Cocoa都在积极开发新的同伦模块或与现有数值软件(如Bertini和PHCpack)的接口。尽管这些数值方法有好处(例如，可并行化)，但也有一些缺点。例如，要使用同伦方法求多项式系统的实孤立解，必须首先产生所有复孤立解，然后将虚部低于预先选择的容差的解进行排序。此外，数值代数几何的一个主要优点是，在代数集合的任何给定的不可约分量上产生许多通用点的近似是很容易的。然而，目前还没有办法恢复组件的准确定义方程。这个项目有两个方向。其中，基于Gale对偶性和Khovanskii-Rolle定理的一组新技术将被开发用于仅寻找多项式系统的实解。在另一门课程中，我们将利用数值方法在代数集合上寻找类属点的简单性。后一个方向将包括通过LLL或PSLQ等格基缩减技术恢复精确定义方程的工作。这两个方向都有望导致新的、免费可用的软件。在数学、科学和工程中，多项式方程组无处不在。一个完整的数学领域--代数几何--产生于寻找这类方程的解的需要。然而，直到20世纪60年代，还没有已知的求解此类方程组的通用技术。然而，当时开发的方法需要太多内存才能有效，除非出现相对较小的问题。最近开发的方法-Sommese、Verschelde和Wsamer的数值方法，现在统称为数值代数几何-允许求解更大的多项式系统，从而将代数几何方法应用于更广泛的问题类别。然而，这些数值方法仍然存在缺陷。该项目的目标包括解决其中两个缺点。特别是，PI将致力于开发有效的方法，以仅找到那些在现实世界应用中感兴趣的解决方案(即，真实解决方案而不是复杂解决方案)，并从作为这些强大的新数值方法的输出提供的近似数据中恢复有价值的准确数据。

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.