AF: Medium: Algorithms Based on Algebraic and Combinatorial Methods

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

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.