Preconditioning, analysis, and applications of numerical algebraic geometry methods

数值代数几何方法的预处理、分析和应用

• 批准号: 1115668
• 负责人: Daniel Bates
• 金额: $ 30.7万
• 依托单位: Colorado State University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2011
• 资助国家: 美国
• 起止时间: 2011-09-15 至 2015-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1115668&HistoricalAwards=false
• 关键词: Preconditioning; analysis; applications; numerical; algebraic

Numerical algebraic geometry involves the use of numerical methods to extract data from ideals about the corresponding varieties or schemes. This area has grown rapidly over the last 20 years and has found applications in many areas of science and engineering. This grant is funding four projects in the area of numerical algebraic geometry. First, the PI and his students will investigate several forms of preconditioning for homotopy continuation, including algorithms for finding (near-)optimal multihomogeneous and linear product start systems, as well as the use of dual bases to reduce the number of paths tracked to "bad" endpoints. Second, the PI and several collaborators will work on three application areas: exceptional mechanisms (via fiber products), software in Macaulay2 for algebraic geometry-related applications, and software for repeated parameter homotopies. Third, the PI will work on analyzing the complexity of numerical algebraic geometry algorithms. Finally, the PI and several collaborators will continue to work on methods to extract information about real algebraic sets both from standard continuation methods and from Khovanskii-Rolle continuation. Polynomial systems of equations arise in many places 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. The methods developed in that era require too much memory to be effective except for relatively small problems. More recently developed methods - the numerical methods of Sommese, Verschelde, Wampler, Li, and others, 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 is still much to understand about these numerical methods. The goals of this project include addressing four open problems in this direction. This work includes the development of techniques to streamline some of these computations, the implementation of valuable algorithms in popular and useful software packages, a careful analysis of the computational costs associated with the computational methods in this field, and the continued effort to extract useful real-world data from the data provided as output from these methods.

数值代数几何涉及使用数值方法从有关相应品种或方案的理想中提取数据。 该领域在过去 20 年中发展迅速，并在科学和工程的许多领域得到了应用。 这笔赠款将资助数值代数几何领域的四个项目。 首先，PI 和他的学生将研究同伦延拓的几种预处理形式，包括寻找（接近）最优多同质和线性乘积起始系统的算法，以及使用双基来减少跟踪到“坏”端点的路径数量。 其次，PI 和几位合作者将致力于三个应用领域：特殊机制（通过光纤产品）、Macaulay2 中用于代数几何相关应用的软件以及用于重复参数同伦的软件。 第三，PI将致力于分析数值代数几何算法的复杂性。 最后，PI 和一些合作者将继续研究从标准延拓方法和 Khovanskii-Rolle 延拓中提取有关实代数集信息的方法。多项式方程组出现在数学、科学和工程的许多地方。整个数学领域——代数几何——源于寻找这类方程的解的需要。然而，直到 20 世纪 60 年代，还没有已知的通用技术来求解此类方程组。那个时代开发的方法除了相对较小的问题外都需要太多的内存才能有效。最近开发的方法——Sommese、Verschelde、Wampler、Li 等人的数值方法，现在统称为数值代数几何——允许求解更大的多项式系统，从而将代数几何方法应用于更广泛的问题。然而，关于这些数值方法仍有很多需要理解的地方。该项目的目标包括解决这个方向的四个悬而未决的问题。 这项工作包括开发简化其中一些计算的技术、在流行且有用的软件包中实现有价值的算法、仔细分析与该领域的计算方法相关的计算成本，以及不断努力从作为这些方法的输出提供的数据中提取有用的现实世界数据。