权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

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发现，被广泛使用并被认为是最好的矩阵乘法算法并不是最优的。从那时起，在确定矩阵乘法的效率和确定Strassen算法可以改进的限度方面，人们进行了密集的研究。这个项目将同时解决效率和限制问题。这两个部分都将使用传统上不用于研究这些问题的理论数学，即表示论和代数几何。现代数学技术的新应用将丰富理论计算机科学和纯数学，因为它们将打开数学中的新问题，并为计算机科学提供新的技术。矩阵乘法的指数，表示为欧米伽，是支配矩阵乘法和线性代数中所有基本运算的复杂性的基本常数。目前已知的omega在2到2.38之间。1968年斯特拉森的发现导致了指数的定义，并证明指数至多为2.81，在接下来的20年里，指数稳步下降到2.38。在过去的33年里，它的改善幅度不到0.004。自1987年以来的所有改进都是通过使用辅助张量间接取得的，在过去10年中，出现了对为什么进展是渐进的解释：目前使用的辅助张量的用途有限。这个项目的上限部分将发现(使用几何方法)并利用不受这种实用限制的新辅助张量。项目的下限部分将约束张量的边界等级。指数没有非平凡的下界，为了证明它，人们必须证明某个张量的边界秩有一个超线性下界，这是目前技术无法达到的目标。现有的技术很难证明(N，N，N)张量的2N的边界秩界。该项目将通过引入更多现代代数几何学的新工具，如形变理论，显著改进下限技术。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。