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的情况下），或者满足于计算接近最优解决方案的算法。在我们的项目中，我们使用基于最近数学进展的非传统工具来解决这些非常困难的问题。最后，但并非最不重要的是，这个项目也有很强的教育成分。PI致力于将这些新知识整合到课程开发、本科生研究项目、研究生和博士后培训以及用于计算优化的新开源软件工具的开发中。一些研究生和本科生将在项目的发展中发挥重要作用。