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

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

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.