Algorithms for Algebraic and 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.