AF: Medium: Algorithms Based on Algebraic and Combinatorial Methods

AF：媒介：基于代数和组合方法的算法

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

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.

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