High-performance computations with rational generating functions

使用有理生成函数进行高性能计算

• 批准号: 0914873
• 负责人: Matthias Koeppe
• 金额: $ 14.28万
• 依托单位: University of California-Davis
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2009
• 资助国家: 美国
• 起止时间: 2009-09-01 至 2013-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0914873&HistoricalAwards=false
• 关键词: performance; computations; rational; generating; functions

This is a research project in Discrete Computational Mathematics. The investigator and his students will use and significantly advance the technology of short rational generating functions introduced by Barvinok (1994). In short, this technology allows to efficiently count the integer points in families of polytopes, which has numerous applications. Research in this project will involve methods from mathematical optimization, discrete geometry, convexity, and computer-based search. The PI has written and maintains the open-source software "LattE macchiato", which is one of the two state-of-the-art implementations of short rational generating functions. Past and current research of the PI has established, by introducing algorithms and proving theorems on their computational complexity, that short rational generating functions have a large computational potential that goes beyond what has been achieved so far in practice. This potential relates to applications in many fields, including combinatorics, mathematical optimization (nonlinear mixed integer programming), and algorithmic game theory. The general theme of the research project is to find new theorems on decomposition schemes with special properties, generalizing the signed decomposition of simplicial cones in the primal or dual space. The PI's research will involve, among other techniques, computer-based search for optimal decomposition schemes. There is a deep theoretical interest in this, independent of algorithmic consequences. On the basis of the new decompositions and other new techniques (such as exploiting symmetry), the PI expects to develop and implement new efficient algorithms, including a parallel implementation for use on multi-core systems and clusters. The overall goal is to expand the range of applicability of short rational generating function methods significantly. The success of these methods will be measured by specific computational challenges listed in this proposal, which are intractable by current computer software.Mathematical optimization is the science of making the best decisions possible, when resources are limited. In the past 10 years it has become clear that a wide array of key technologies, ranging from biotechnology to chemical engineering and healthcare, depend on the ability to solve a complicated type of mathematical optimization problems, called "nonlinear mixed-integer programs". The PI and collaborators have shown recently that a mathematical technique called short rational generating functions is very powerful to solve these optimization problems, surpassing all other known techniques, at least in mathematical theory. However, there still is a huge gap between theory and practice. This research project is about fundamental research on this technique of short rational generating functions, to help bridge the gap. This will lead to new mathematical insights and more efficient algorithms and new, more powerful open-source mathematical software. This project also has a strong educational impact. The PI plans to train several undergraduate and graduate students in this research area. One component of the training will be to create new course material on the topics of this proposal, and to use it for new classes for undergraduate and graduate students. The second component of the training consists of direct involvement of students in this research project, involving theoretical work, computer experimentation, and software implementation, all of which lead to undergraduate and graduate theses.

这是一个离散计算数学的研究项目。 研究人员和他的学生将使用和显着推进技术的短理性生成功能介绍Barvinok（1994）。 简而言之，该技术允许有效地计算多面体族中的整数点，这具有许多应用。 本计画的研究将涉及数学最佳化、离散几何、凸性与电脑搜寻等方法。 PI编写并维护了开源软件“LattE macchiato”，这是短有理生成函数的两个最先进的实现之一。 过去和目前的研究PI已经建立，通过引入算法和证明定理的计算复杂性，短的有理生成函数有一个大的计算潜力，超越了迄今为止在实践中取得的成就。 这种潜力涉及到许多领域的应用，包括组合学，数学优化（非线性混合整数规划）和算法博弈论。 该研究项目的总主题是寻找具有特殊性质的分解方案的新定理，推广原始或对偶空间中单纯锥的符号分解。 PI的研究将涉及，除其他技术外，基于计算机的搜索最佳分解方案。 在这方面有一个深刻的理论兴趣，独立于算法的后果。 在新的分解和其他新技术（如利用对称性）的基础上，PI希望开发和实现新的高效算法，包括用于多核系统和集群的并行实现。总体目标是扩大短有理生成函数方法的适用范围显着。 这些方法的成功将通过本提案中列出的具体计算挑战来衡量，这些挑战是当前计算机软件无法解决的。数学优化是在资源有限的情况下做出最佳决策的科学。 在过去的10年里，人们已经清楚地认识到，从生物技术到化学工程和医疗保健等一系列关键技术都依赖于解决一种复杂的数学优化问题的能力，这种问题被称为“非线性混合整数规划”。 PI和合作者最近表明，一种称为短有理生成函数的数学技术非常强大，可以解决这些优化问题，超过了所有其他已知的技术，至少在数学理论上。 然而，理论与实践之间仍存在巨大差距。 本研究计画即是对短有理母函数技术进行基础性研究，以弥补这一差距。 这将带来新的数学见解和更有效的算法，以及新的、更强大的开源数学软件。 该项目也具有很强的教育影响力。 PI计划在这一研究领域培养几名本科生和研究生。 培训的一个组成部分将是就本提案的主题编写新的课程材料，并将其用于本科生和研究生的新课程。培训的第二部分包括学生直接参与这个研究项目，涉及理论工作，计算机实验和软件实施，所有这些都导致本科和研究生论文。