AF: Small: The complexity of matrix multiplication

AF：小：矩阵乘法的复杂度

基本信息

批准号：
2203618
负责人：
Joseph Landsberg
金额：
$ 45万
依托单位：
Texas A&M University
依托单位国家：
美国
项目类别：
Standard Grant
财政年份：
2022
资助国家：
美国
起止时间：
2022-03-01 至 2025-02-28
项目状态：
未结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=2203618&HistoricalAwards=false
关键词：
AF Small complexity matrix multiplication

项目摘要

Linear algebra, which includes computing the solutions to a system of linear equations, is at the heart of all scientific computation. The core computation of linear algebra is matrix multiplication. In 1968 V. Strassen discovered that the widely used and assumed best algorithm for matrix multiplication is not optimal. Since then there has been intense research in both determining just how efficiently matrices may be multiplied and determining the limits of how much Strassen's algorithm can be improved. This project will address both efficiency and limits. Both parts will be approached using theoretical mathematics not traditionally utilized in the study of these questions, namely representation theory and algebraic geometry. The novel use of modern mathematical techniques will enrich both theoretical computer science and pure mathematics, as they will open new questions in mathematics and provide new techniques to computer science.The exponent of matrix multiplication, denoted omega, is the fundamental constant that governs the complexity of matrix multiplication and all basic operations in linear algebra. It is currently known that omega is somewhere between 2 and 2.38. After Strassen's 1968 discovery, which led to the definition of the exponent and proof that it is at most 2.81, over the next twenty years it was steadily lowered to 2.38. In the past 33 years, it has been improved by less than .004. All improvements since 1987 have been made indirectly through the use of auxiliary tensors and in the past 10 years explanations for why progress became incremental have emerged: the utility of auxiliary tensors currently being used is limited. The upper bound part of this project will discover (using geometric methods) and utilize new auxiliary tensors that are not subject to such utility limits. The lower bound part of the project will bound border rank of tensors. There are no nontrivial lower bounds on the exponent, and in order to prove one, one would have to prove a super-linear lower bound on the border rank of some tensor, a goal that is out of reach with current technology. The current technology can barely prove border rank bounds of 2N for (N,N,N)-tensors. This project will significantly improve lower bound technology by introducing further new tools to the area from modern algebraic geometry such as deformation theory.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.

线性代数包括计算线性方程组的解，是所有科学计算的核心。线性代数的核心计算是矩阵乘法。 1968 年，V. Strassen 发现广泛使用和假设的最佳矩阵乘法算法并不是最优的。从那时起，人们在确定矩阵乘法的效率和确定斯特拉森算法可以改进多少的极限方面进行了大量的研究。该项目将解决效率和限制问题。这两部分都将使用传统上在这些问题的研究中不使用的理论数学来处理，即表示论和代数几何。现代数学技术的新颖使用将丰富理论计算机科学和纯数学，因为它们将提出数学中的新问题并为计算机科学提供新技术。矩阵乘法的指数，表示为 omega，是控制复杂性的基本常数矩阵乘法和线性代数中的所有基本运算。目前已知 omega 介于 2 到 2.38 之间。施特拉森 1968 年的发现导致了指数的定义并证明指数最多为 2.81，之后的 20 年里指数稳步降至 2.38。在过去的33年里，它的改善幅度不到0.004。自 1987 年以来的所有改进都是通过使用辅助张量间接实现的，并且在过去 10 年中，对于为什么进步变得渐进的解释已经出现：目前使用的辅助张量的效用是有限的。该项目的上限部分将发现（使用几何方法）并利用不受此类效用限制的新辅助张量。该项目的下界部分将限制张量的边界等级。指数不存在非平凡的下界，为了证明这一点，必须证明某个张量的边界秩上的超线性下界，这是当前技术无法实现的目标。目前的技术几乎无法证明 (N,N,N) 张量的 2N 边界等级界限。该项目将通过向变形理论等现代代数几何领域引入更多新工具，显着改进下限技术。该奖项反映了 NSF 的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。