AF:Small: Algorithms and Limitations for Matrix Multiplication

AF:Small：矩阵乘法的算法和限制

• 批准号: 2330048
• 负责人: Virginia Williams
• 金额: $ 60万
• 依托单位: Massachusetts Institute of Technology
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2023
• 资助国家: 美国
• 起止时间: 2023-08-01 至 2026-07-31
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2330048&HistoricalAwards=false
• 关键词: AF; Small; Algorithms; Limitations; Matrix

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.

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