AF: Medium: Algorithms Based on Algebraic and Combinatorial Methods

许多高级组合问题都有代数方面的问题。即使问题的表述可以是完全离散的，通过应用复杂的代数方法也可以获得重要的洞察力和高效的算法。组合问题具有简单而优雅的公式并不少见，但它们在计算上很困难，这意味着除了非常小的实例外，明显的算法对于它们的解是毫无用处的。也可能发生这样的情况，即使传统的算法方法是成功的，代数方法仍然更有效，并为组合问题提供了更多的见解。图同构问题举例说明了一个组合问题，其中似乎需要代数方法来获得有效的解。对于代数和组合方法来说，有趣的还有单体二聚体问题，即网格图中匹配的计数，这在统计物理中非常重要。该方案研究了基于尺度方法的算法。一个特别的目标是高效地并行进行矩阵缩放，作为近似永久矩阵的工具。这个项目将着眼于树和有界树宽的图的图多项式的所有系数的计算。该项目的另一个主要重点是探索最近更快的整数乘法算法的变化，并研究其在多项式乘法和傅立叶变换中的应用。一个目标是开发一种新的算法，基于一种更离散的方法，提高渐近复杂性，并导致计算超长整数乘积的更实用的算法。整数乘法是一项基本的算术任务，理解和改进它显然是一项基本的智力挑战。这样的理论目标在这个项目中是最重要的。但这可能会对寻找梅森素数以及使用高次多项式的通用计算产生影响。这项研究的其他方面涉及在物理和化学中的应用主题。

Many advanced combinatorial problems have algebraic aspects. Even though the problem formulation can be entirely discrete, significant insight and efficient algorithms might be obtained by applying sophisticated algebraic methods. It is not uncommon that combinatorial problems have simple and elegant formulations, yet they are computationally hard, meaning that the obvious algorithms are useless for their solutions except for very small instances. It can also happen that even though traditional algorithmic approaches are successful, algebraic methods are still more efficient and provide additional insights into a combinatorial problem.The graph isomorphism problem exemplifies a combinatorial problem where algebraic methods seem to be required for efficient solutions. Interesting for algebraic and combinatorial approaches is also the monomer dimer problem, the counting of matchings in grid graphs, which is of much importance in statistical physics. This proposal studies algorithms based on the scaling method. A particular goal is doing matrix scaling efficiently in parallel, as a tool for approximating the permanent. This project will look at the computation of all coefficients of graph polynomials for trees and graphs of bounded tree-width. The goal is to compute all coefficients together almost as fast as a single coefficient.The other main focus of this project is the exploration of variations of the recent faster integer multiplication algorithm and the study of its application to polynomial multiplications and Fourier transforms. One goal is to develop a new algorithm, based on a more discrete method, improving the asymptotic complexity as well as leading to a more practical algorithm for computing products of very long integers.Integer multiplication is such a fundamental arithmetic task that understanding and improving it is an obvious basic intellectual challenge. Such theoretical goals are foremost in this project. But there could be an impact on the search for Mersenne primes as well as on general purpose computations with high degree polynomials. Other aspects of this research involve topics with applications in Physics and Chemistry.