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.

该项目的目的是在代数符号计算和计算几何形状中开发算法和软件。这些算法将在离散数学，优化和计算机科学的各种问题中有用。 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匹配或他们的自动形态群体非常大）。尽管解决非线性方程式的任意系统通常是一个非常困难的问题，但我们已经能够为具有数千个变量的异常大型多项式系统提供快速解决方案。工作的第二个区域与凸多面体的几何形状有关。通常，操作研究和优化中的软件需要一种快速的方法来决定何时多面体可行。依靠计算几何分析，凸分析和概率，PI打算开发快速的启发式方法，以检测多面体内部的晶格点以及计算其所有晶格点。 PI希望将这些想法纳入数学编程软件。解决方程和不平等系统的软件和算法，或者决定方程系统是否具有具有整数数字的解决方案在数学，工程，工程以及其他所有领域都非常有用。我们将考虑的大多数问题与希望找到最佳安排或以稀缺资源做出最佳决策的问题直接相关。示例包括选择连接给定网站的最便宜网络或选择最便宜的旅行以访问给定的位置的问题。由于此类优化问题出现在社会的所有领域（数据挖掘，财务和经济学，运输计划和电路设计，仅举几例），但很难解决，因此研究人员探索了特殊的结构，以便能够在实践中（例如，就THETSP而言）解决这些结构（例如，就THETSP而言），以计算近似近距离解决方案的算法。在我们的项目中，我们根据最近的数学进步使用非传统工具，以解决这些非常困难的问题。最后但并非最不重要的一点是，该项目还具有强大的教育组成部分。 PI致力于将这些新知识纳入课程开发，本科研究项目，研究生和博士后的培训以及开发用于计算优化的新开源软件工具。几位毕业生和本科生将在项目的发展中发挥重要作用。