Computational Polyhedral Geometry: Applications in Algebra, Combinatorics, and Optimization

计算多面体几何：在代数、组合学和优化中的应用

• 批准号: 0309694
• 负责人: Jesus De Loera
• 金额: $ 18.89万
• 依托单位: University of California-Davis
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2003
• 资助国家: 美国
• 起止时间: 2003-08-01 至 2007-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0309694&HistoricalAwards=false
• 关键词: Computational; Polyhedral; Geometry; Applications; Algebra

The investigator uses methods from commutative algebra,convexity, and analysis to design computer algorithms that allowthe practical fast detection or counting of lattice points insiderational convex polytopes. The main idea is to represent thelattice points using rational functions. This can be done in atleast three different complementary ways. He implements themethods in the computer software LattE. The investigator usesthis software to help investigate theoretical questions incombinatorics (properties of Ehrhart functions), algebra(representation theory and partitions), and optimization (newinteger programming algorithms). The investigator carries out geometric, analytic, andcomputational studies of problems in the convexity andcombinatorics of polyhedra, including development of algorithmsand software. Informally speaking, the project can be thought ofas an attempt to understand how to count the possiblenon-negative integer solutions of a system of linear equations.With two unknowns, this amounts to counting the number ofregularly distributed points -- lattice points -- in a polygon.With more unknowns, the solutions correspond geometrically to thehigher-dimensional analogs to cubes and polygons. Examples ofregularly distributed points are arrangements of atoms orcrystals. Many of the theoretical questions under study aremotivated by problems in data security and computation (in thecontext of RSA encryption, which is used in internettransactions), operations research (via certain techniques forsolving integer programs when levels of uncertainty areexpected), statistics (contingency tables, data analysis), andproblems in abstract algebra (number theory, representationtheory). The training of students is a very important componentof the project.

研究人员使用交换代数，凸性和分析的方法来设计计算机算法，使实际的快速检测或计算格点inderational凸多面体。 其主要思想是用有理函数表示格点。 这至少可以通过三种不同的互补方式来实现。 他在计算机软件LattE中实现了这些方法。 调查员使用这个软件来帮助调查组合学（Ehrhart函数的性质），代数（表示论和分区）和优化（新整数规划算法）的理论问题。 该研究员进行几何，分析和计算研究的问题，凸性和组合的多面体，包括发展的算法和软件。 非正式地说，这个项目可以被认为是试图了解如何计算一个线性方程组的可能的非负整数解。有两个未知数，这相当于计算多边形中规则分布的点（格点）的数量。有更多的未知数，这些解在几何上对应于立方体和多边形的高维类似物。 规则分布点的例子是原子或晶体的排列。 许多正在研究的理论问题是由数据安全和计算问题（在RSA加密的背景下，这是在互联网交易中使用的），运筹学（通过某些技术解决整数规划时，预期的不确定性水平），统计学（列联表，数据分析）和抽象代数问题（数论，表示论）。 学生的培训是该项目的一个非常重要的组成部分。