AF: Small: Algorithms for Matrix Multiplication, Polynomial Factorization and Generalized Fourier Transform

AF：小：矩阵乘法、多项式分解和广义傅立叶变换算法

• 批准号: 1423544
• 负责人: Christopher Umans
• 金额: $ 50万
• 依托单位: California Institute of Technology
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2014
• 资助国家: 美国
• 起止时间: 2014-07-01 至 2017-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1423544&HistoricalAwards=false
• 关键词: AF; Small; Algorithms; Matrix; Multiplication

This project addresses three prominent algorithmic problems: matrix multiplication, polynomial factorization, and the generalized discrete Fourier transform (DFT). In the first two, the challenge is to obtain fast algorithms for basic manipulations of matrices and polynomials, and in the third, the challenge is to obtain fast algorithms for transforming data in certain mathematically meaningful ways. Matrix multiplication is a central open problem in theoretical computer science, both because of its intrinsic mathematical appeal, and because improved algorithms for this important problem would have immediate consequences for a broad variety of related problems. Univariate polynomial factorization occupies a similar central position among the basic operations on polynomials, and the generalized DFT is one of the most interesting and useful linear maps, with structure that should admit a fast algorithm. All three problems are fundamental and longstanding open problems, and they have a diversity of applications in computer science, and beyond.The project's goal is to achieve "nearly-linear" time algorithms for all three problems. These problems possess rich structure that is susceptible to a sophisticated mathematical treatment; for example, one technique is to embed matrix multiplication into algebraic structures arising from groups and coherent configurations. This project develops these ideas, and at the same time aims to make further progress by injecting some more "computer science"-style ideas -- recursion, approximation, reductions, relaxations, and a mixture of Boolean computation with algebraic operations. Because all three focus areas of this project revolve around difficult and longstanding open problems, the project will take concrete steps towards (1) building up understanding and (2) developing useful machinery, both aimed at an eventual resolution of these central algorithmic problems.

这个项目解决了三个突出的算法问题：矩阵乘法、多项式因式分解和广义离散傅立叶变换(DFT)。在前两种情况下，挑战是获得用于矩阵和多项式基本运算的快速算法，而在第三种情况下，挑战是获得以某些数学意义的方式转换数据的快速算法。矩阵乘法是理论计算机科学中的一个中心开放问题，这既是因为它内在的数学吸引力，也是因为这个重要问题的改进算法将立即对各种相关问题产生影响。一元多项式因式分解在多项式的基本运算中占有类似的中心位置，而广义DFT是最有趣和最有用的线性映射之一，其结构应该允许快速算法。这三个问题都是基本的和长期开放的问题，它们在计算机科学和其他领域都有不同的应用。该项目的目标是为这三个问题实现“近线性”的时间算法。这些问题具有丰富的结构，易于进行复杂的数学处理；例如，一种技术是将矩阵乘法嵌入到由群和相干构型产生的代数结构中。该项目发展了这些思想，同时旨在通过注入更多的“计算机科学”风格的思想来取得进一步的进展--递归、近似、简化、松弛以及布尔计算和代数运算的混合。由于这个项目的所有三个重点领域都围绕着困难和长期存在的公开问题，该项目将采取具体步骤，以(1)建立理解和(2)开发有用的机制，两者都旨在最终解决这些核心算法问题。