AF:Small: Algorithms and Limitations for Matrix Multiplication

矩阵乘法是最基本、最基本的数学运算之一。它在科学、技术和其他领域都有应用。例如，每当需要计算轨迹或坐标变化时，矩阵都需要相乘：在图形、计算机动画、物理和化学模拟、地图路由计算、机器学习、经济学等领域。矩阵乘法算法的研究旨在为计算机开发最快的矩阵乘法方法。在当今的大数据世界中，我们感兴趣的矩阵比以往任何时候都要大，因此非常快速的矩阵乘法方法非常重要。该项目的一个重要教育目标是指导本科生和研究生进行研究，特别强调在矩阵算法及其应用方面建立专业知识。研究人员还将继续开发有关该项目主题的课程，其中包含大量研究内容。课堂讲稿和项目材料将在课程网站上提供给公众。几十年来，矩阵乘法的简单方法被认为是最优的，直到1969年Strassen的突破和随后的深度理论的发展导致了重大的改进。矩阵乘法算法的理论研究旨在确定矩阵乘法的指数：使用n^{omega+o(1)}运算（字段元素的加法和乘法）在字段上乘以两个n × n矩阵的算法的最小实数。因为输出的大小是n^2，在最坏的情况下，至少是2。最著名的上界是由Alman和研究者获得的，最近在arXiv上的预印本给出了对omega2.372的改进。本课题的主要目标是研究改进ω和相关参数的界的新方法，并设计一个可证明的低运行时指数的实用算法。为了补充这一点，研究者还将探索新方法的局限性，旨在指出它们的优点和缺点。该项目的第二个目标是考虑矩阵乘法问题的变体，例如在图算法中应用其他代数结构上的矩阵乘法。算法和条件下界都将被考虑。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Matrix multiplication is among the most basic and fundamental mathematical operations. It finds applications throughout science, technology and beyond. For instance, matrices need to be multiplied whenever trajectories or changes of coordinates need to be computed: in graphics, computer animation, physics and chemistry simulations, map routing computations, machine learning, economics and more. The study of matrix multiplication algorithms seeks to develop the fastest methods for computers to multiply matrices. With today's world of big data, the matrices of interest are larger than ever, and very fast matrix multiplication methods are of great importance. An important educational goal of the project is to mentor undergraduate and graduate students in research, with a particular emphasis on building expertise in matrix algorithms and their applications. The investigator will also continue developing courses on the topics of this project, with a large research component. The lecture notes and project materials will be available on the course website for the general public.For decades the trivial approach to multiplying matrices was thought to be optimal until a 1969 breakthrough by Strassen and the subsequent development of deep theory led to significant improvements. The theoretical study of matrix multiplication algorithms aims to pinpoint the exponent omega of matrix multiplication: the smallest real number for which there is an algorithm that multiplies two n-by-n matrices over a field using n^{omega+o(1)} operations (additions and multiplications of field elements). Since the output is of size n^2, in the worst case, omega is at least 2. The best known published upper bound omega2.37286 was obtained by Alman and the investigator, and a recent preprint on the arXiv gives an improvement to omega2.372. The main goal of this project is to investigate new approaches to improving the bound on omega and related parameters, and to design a practical algorithm with a provably low runtime exponent. To complement this, the investigator will also explore the limitations of the new approaches, aiming to pinpoint both their strengths and weaknesses. A second goal of the project is to consider variants of the matrix multiplication problem, such as multiplying matrices over other algebraic structures with applications in graph algorithms. Both algorithms and conditional lower bounds will be considered.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.