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)开发有用的机器，两者都旨在最终解决这些核心算法问题。