Algebraic and Geometric Computation with Applications

代数和几何计算及其应用

• 批准号: 0914107
• 负责人: Jesus De Loera
• 金额: $ 19.45万
• 依托单位: University of California-Davis
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2009
• 资助国家: 美国
• 起止时间: 2009-09-15 至 2013-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0914107&HistoricalAwards=false
• 关键词: Algebraic; Geometric; Computation; Applications

The goal of this project is to develop algorithms and software in both algebraic-symbolic computation and computational geometry. The algorithms will be useful in a wide variety of problems of discrete mathematics, optimization, and computer science. First, regarding algebraic computation, the PI will use ideas from commutative algebra, real algebraic geometry, large-scale linear algebra, semidefinite analysis, and combinatorics to develop very fast algorithms that can solve large, but highly-structured systems of polynomial equations that carry an extra rich combinatorial structure (e.g., they are defined from a graph and their solutions correspond to colorings or matchings, or their group of automorphisms is very large). Although solving arbitrary systems of non-linear equations is a very hard problem in general, we have been able to provide fast solutions for unusually large polynomial systems with thousands of variables. The second area of work is more related to the geometry of convex polyhedra. It is common that software in Operations Research and Optimization requires a quick way to decide when a polyhedron is integrally feasible. Relying on computational geometry analysis, convex analysis and probability, the PI intends to develop fast heuristics for detecting the existence of a lattice point inside a polyhedron as well as for counting of all its lattice points. The PI hopes to incorporate these ideas to mathematical programming software.Software and Algorithms that solve systems of equations and inequalities or that decide whether a system of equations has a solution with integer numbers are extremely useful in all areas of mathematics, engineering, and beyond. Most of the problems we will consider are directly related to problems where one wishes to find an optimal arrangement or make best decisions with scarce resources. Examples include the problem of selecting the least expensive network connecting given sites or selecting the least expensive tour for visiting a given set of locations. Since such optimization problems appear in all areas of society (data mining, finances and economics, transport scheduling and circuit design, to name a few) but are very difficult to solve, researchers have explored special structures to be able to solve them in practice (e.g., in the case of theTSP) or settle for algorithms that compute near-optimal solutions. In our project we use non-traditional tools based on recent mathematical progress as a way to approach these very difficult problems. Last, but not least, the project also has a strong educational component for this project. The PI is committed to integrate this new knowledge within curriculum development, undergraduate research projects, training of graduate students and postdocs, and the development of new open source software tools for computational optimization. Several graduate and undergraduate students will play important roles in the project's development.

这个项目的目标是开发代数-符号计算和计算几何的算法和软件。这些算法将在离散数学、最优化和计算机科学的各种问题中发挥作用。首先，关于代数计算，PI将使用交换代数、实代数几何、大规模线性代数、半定分析和组合学的思想来开发非常快速的算法，这些算法可以求解具有特别丰富的组合结构的大型但高度结构的多项式方程系统(例如，它们是从图定义的，其解对应于颜色或匹配，或者它们的自同构组非常大)。虽然求解任意的非线性方程组通常是一个非常困难的问题，但我们已经能够为具有数千个变量的异常大的多项式系统提供快速的解。第二个工作领域更多地与凸多面体的几何有关。运筹学和优化中的软件通常需要一种快速的方法来确定多面体何时是整体可行的。PI以计算几何分析、凸分析和概率论为基础，旨在开发快速启发式算法来检测多面体内部格点的存在以及对其所有格点进行计数。PI希望将这些想法结合到数学编程软件中。解决方程和不等式系统的软件和算法，或者决定方程系统是否有整数解的软件和算法，在数学、工程和其他领域都非常有用。我们将考虑的大多数问题都与人们希望用稀缺的资源找到最佳安排或做出最佳决定的问题直接相关。例如，选择连接给定站点的最便宜的网络的问题，或者选择访问给定地点的最便宜的旅游的问题。由于这样的优化问题出现在社会的所有领域(数据挖掘、金融和经济、交通调度和电路设计等)，但都很难解决，研究人员探索了特殊的结构，以便能够在实践中解决这些问题(例如，在TSP的情况下)或满足于计算近最优解的算法。在我们的项目中，我们使用基于最新数学进展的非传统工具来解决这些非常困难的问题。最后，但并非最不重要的一点是，该项目也有很强的教育成分。该研究所致力于将这一新知识融入课程开发、本科生研究项目、研究生和博士后培训，以及开发新的计算优化开源软件工具。几名研究生和本科生将在该项目的发展中发挥重要作用。