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。Alman和研究人员获得了最著名的已发表上限omega2.37286，最近在arxiv上的预印本对omega2.372进行了改进。这个项目的主要目标是研究新的方法来改善omega和相关参数的界限，并设计一个实用的算法，可以证明运行时间指数很低。为了补充这一点，调查人员还将探索新方法的局限性，旨在找出它们的优点和缺点。该项目的第二个目标是考虑矩阵乘法问题的变体，例如将矩阵与其他代数结构相乘，并将其应用于图算法。算法和条件下限都将被考虑。这一奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。