Algorithms for Algebraic and Combinatorial Problems

这项研究涉及计算困难的代数和组合问题。它研究了最近更快的整数乘法算法的变体，并探索了它在多项式乘法和傅立叶变换中的应用。整数乘法是一项基本的算术任务，理解和提高它显然是一项基本的智力挑战。这可能会对寻找梅森素数产生影响。另一个主要目标是设计和分析离散算法，这些算法是组合优化和计数问题的近似解。困难问题的确切解决方案往往是不可行的。在这种情况下，近似算法是一种可行的选择。特别令人感兴趣的是单体二聚体问题，即网格图中匹配的计数，这在统计物理中非常重要。作为一种近似永久的工具，本研究探索了高效并行进行矩阵缩放的可能性。这样的解决方案可以解决(NC)并行计算中悬而未决的二部匹配问题。虽然匹配问题对于一台顺序机来说是很容易的，但要协调一台并行机的多个处理器同时进行相同的匹配并保持高效是非常具有挑战性的。这项研究的智力价值依赖于这样一个事实，即许多解决方案需要复杂的数学推理方法。成功的解决方案通常有可能增强对近似和并行计算可能性的理解。对统计物理学中的一个重大问题产生重大影响的可能性，给出了更广泛的影响。

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.