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致力于将这一新知识整合到课程开发、本科生研究项目、研究生和博士后培训以及开发用于计算优化的新开源软件工具中。一些研究生和本科生将在项目的发展中发挥重要作用。