Algorithms for Algebraic and Combinatorial Problems

代数和组合问题的算法

• 批准号: 0728921
• 负责人: Martin Furer
• 金额: $ 30万
• 依托单位: Pennsylvania State Univ University Park
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2007
• 资助国家: 美国
• 起止时间: 2007-09-15 至 2011-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0728921&HistoricalAwards=false
• 关键词: Algorithms; Algebraic; Combinatorial; Problems

This research deals with computationally hard algebraic and combinatorial problems. It investigates variations of the recent faster integer multiplication algorithm and explores its applications to polynomial multiplication and Fourier transforms. Integer multiplication is such a fundamental arithmetic task that understanding and improving it is an obvious basic intellectual challenge. There could be an impact on the search for Mersenne primes. Another major goal is to design and analyze discrete algorithms that are approximating solutions to combinatorial optimization and counting problems. Exact solutions for hard problems are often not feasible. In such cases approximation algorithms are a viable alternative. Of particular interest is the monomer dimer problem, the counting of matchings in grid graphs, which is of much importance in statistical physics.As a tool for approximating the permanent, this research explores the possibility of doing matrix scaling efficiently in parallel. Such a solution would allow to solve (in NC) the outstanding bipartite matching problem of parallel computing. Even though the matching problem is easy for asequential machine, it is very challenging to coordinate the many processors of a parallel machine to work simultaneously on the same matching and be efficient. The intellectual merit of this research relies on the fact that many solutions require sophisticated methods of mathematical reasoning.Successful solutions have the potential to enhance the understanding of the possibilities of approximations and parallel computations in general. A broader impact is given by the potential of having a significant effect on a major problem in statistical physics.

这项研究涉及计算困难的代数和组合问题。它研究了最近的更快的整数乘法算法的变化，并探讨其应用多项式乘法和傅立叶变换。乘法是一项基本的算术任务，理解和改进它显然是一项基本的智力挑战。这可能会对梅森素数的寻找产生影响。另一个主要目标是设计和分析离散算法，近似解决组合优化和计数问题。困难问题的精确解决方案往往是不可行的。在这种情况下，近似算法是可行的替代方案。特别感兴趣的是单体二聚体问题，在网格图中的匹配计数，这是非常重要的统计physics.As一种工具，用于近似的永久，本研究探讨了并行进行矩阵缩放有效的可能性。这样的解决方案将允许解决（在NC中）并行计算的突出的二分匹配问题。尽管匹配问题对于序列机来说很容易，但是协调并行机的多个处理器同时工作在同一匹配上并且是高效的是非常具有挑战性的。这项研究的智力价值依赖于这样一个事实，即许多解决方案需要复杂的数学推理方法。成功的解决方案有可能提高对近似和并行计算的可能性的理解。更广泛的影响是由对统计物理学中的一个重大问题产生重大影响的潜力所赋予的。