AF: Small: Algorithms Based on Discrete and Algebraic Methods

AF：小：基于离散和代数方法的算法

• 批准号: 1320814
• 负责人: Martin Furer
• 金额: $ 39.94万
• 依托单位: Pennsylvania State Univ University Park
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2013
• 资助国家: 美国
• 起止时间: 2013-09-01 至 2017-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1320814&HistoricalAwards=false
• 关键词: AF; Small; Algorithms; Based; Discrete

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.

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