AF: Small: The complexity of matrix multiplication

线性代数，包括计算线性方程组的解，是所有科学计算的核心。线性代数的核心计算是矩阵乘法。1968年，V。Strassen发现，被广泛使用并被认为是矩阵乘法的最佳算法并不是最优的。从那时起，在确定矩阵相乘的效率和确定Strassen算法可以改进多少的极限方面，人们进行了大量的研究。这个项目将解决效率和限制问题。这两部分都将使用传统上不用于研究这些问题的理论数学，即表示理论和代数几何。现代数学技术的新应用将丰富理论计算机科学和纯数学，因为它们将在数学中开辟新的问题并为计算机科学提供新的技术。矩阵乘法的指数，记为，是控制矩阵乘法的复杂性和线性代数中所有基本运算的基本常数。目前已知的是在2到2.38之间。1968年，斯特拉森的发现给指数下了定义，并证明了它至多为2.81。此后的20年里，指数稳步降至2.38。在过去的33年里，它只提高了不到0.004。自1987年以来，所有的改进都是通过使用辅助张量间接实现的，在过去的10年里，关于为什么进展变得渐进式的解释已经出现：目前使用的辅助张量的效用是有限的。这个项目的上界部分将发现（使用几何方法）和利用新的辅助张量，不受这种效用限制。项目的下界部分将约束张量的边界秩。指数上没有非平凡的下界，为了证明它，我们必须证明某个张量的边界秩上有一个超线性的下界，这是目前技术无法达到的目标。对于（N，N，N）张量，目前的技术只能勉强证明2N的边界秩界。该项目将通过引入现代代数几何（如变形理论）的新工具，显著改善下界技术。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

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.