AF: Small: Algorithms Based on Discrete and Algebraic Methods

本研究关注离散计算任务，主要是数学决策和优化问题。这些问题通常可以用离散方法直接求解。本研究的重点是研究代数方法产生更好的解决方案的情况。即使问题的制定可以是完全离散的，重要的洞察力和有效的算法可能会通过应用复杂的代数方法。组合问题具有简单而优雅的公式并不罕见，但除了非常小的实例之外，明显的算法对于它们的解决方案来说太慢了。在这种情况下，代数方法可能会提供决定性的见解。图同构问题是一个组合问题，代数方法已经成功地产生了有效的算法。本研究还涉及具有这些特征的其他基础数学问题，如长整数的有效乘法和单体二聚体问题，以及网格图中匹配的计数。使用的典型代数工具是群论、离散傅立叶变换、以及zeta变换及其逆变换、莫比乌斯变换。通常，没有明显的方法可以最有效地应用这些工具。例如，最快的整数乘法算法都是基于傅立叶变换，但效率在很大程度上取决于所应用的傅立叶变换的类型。这个项目涉及基本的组合和代数任务，有效的算法是可取的。这项研究意义重大，因为它有助于更好地理解这些问题背后的数学结构，并导致发现更有效的算法。该项目的一个重要目标是促进新一代研究生的发展，他们欣赏数学洞察力的发展，以产生有效的算法为目标，解决困难的组合和代数问题。特别是，整数乘法是一项基本的算术任务，理解和改进它显然是一项基本的智力挑战。这些理论目标在这个项目中是最重要的。但是，对梅森素数的搜索和高次多项式的通用计算有潜在的影响。这项研究的其他方面涉及物理和化学应用的主题。

This research is concerned with discrete computational tasks, mainly mathematical decision and optimization problems. Often such problems can be attacked directly by discrete methods. The focus of this research is to study situations where algebraic approaches produce better solutions. 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 the obvious algorithms are too slow for their solutions except for very small instances. In such situation, algebraic methods might provide the decisive insights. The graph isomorphism problem exemplifies a combinatorial problem where algebraic methods have successfully produced efficient algorithms. This research also deals with other foundational mathematical problems having these characteristics, like efficient multiplication of long integers and the monomer dimer problem, and the counting of matchings in grid graphs. Typical algebraic tools used are group theory, the discrete Fourier transform, as well as the zeta transform and its inverse, the Mobius transform. Usually, there is no obvious way of how to apply these tools most effectively. For example, the fastest integer multiplication algorithms are all based on Fourier transforms, but the efficiency heavily depends on the type of Fourier transform applied. This project deals with fundamental combinatorial and algebraic tasks for which efficient algorithms are desirable. This research is significant, because it contributes to a better understanding of the mathematical structures behind these problems and leads to the discovery of more efficient algorithms.An important goal of this project is to contribute to the development of a new generation of graduate students, who appreciate the development of mathematical insight into difficult combinatorial and algebraic problems with the goal of producing efficient algorithms. In particular, 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 is a potential for an impact on the search for Mersenne primes and on general purpose computations with high degree polynomials. Other aspects of this research involve topics with applications in Physics and Chemistry.