CAREER: Complexity of Matrix Operations

矩阵是矩形的数字网格，可以以多种形式表示数据，包括几何转换、统计模型、物理系统和数据点之间的关系。正因为如此，涉及矩阵的计算任务出现在整个计算理论和实践中，特别是在优化、科学计算、信号处理、数据压缩和现代机器学习等领域。快速执行矩阵运算通常是设计有效算法以理解和操作这些领域数据的关键。这个项目的首要目标是研究这些矩阵运算：我们能否为它们设计更快的算法？我们能证明进一步的改进是不可能或不可能的吗？我们能否利用它们与其他领域的许多联系，或者建立新的联系？由于矩阵无处不在，这个项目的教育目标是在许多层面上教学和传播研究成果，从当地的高中学生到广泛的研究矩阵运算不同方面的理论和实践的研究社区。该项目特别旨在通过研究机会和新课程的开发，培养本科生和研究生在矩阵运算理论和应用方面的能力。这个项目更具体地关注两个基本问题，这两个问题构成了大多数其他涉及矩阵的计算任务的主干。第一个问题是快速矩阵乘法：两个输入矩阵相乘的速度有多快？矩阵乘法在许多基本计算问题的已知最快算法中使用。它通常被认为是瓶颈，这意味着需要更快的矩阵乘法来加速最佳算法。第二个问题是快速线性变换：一个输入向量与一个感兴趣的矩阵（比如傅里叶矩阵）相乘的速度有多快？像快速傅里叶变换和快速沃尔什-阿达玛变换这样的算法是一些最适用和最有影响力的算法。这些变换也是整个计算复杂性理论中突出主题的基础。研究者最近证明了关于为矩阵乘法和线性变换设计更快算法的形式障碍的结果。该项目追求的主要见解之一是，来自这些障碍结果的想法可以帮助在算法上取得新的进展。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

Matrices are rectangular grids of numbers that can represent data in many forms, including geometric transformations, statistical models, physical systems, and relationships between data points. Because of this, computational tasks involving matrices appear throughout the theory and practice of computation, especially in areas like optimization, scientific computing, signal processing, data compression, and modern machine learning. Quickly performing matrix operations is frequently the key to designing efficient algorithms for understanding and manipulating data in these areas. The overarching goal of this project is to study these matrix operations: Can we design faster algorithms for them? Can we prove that further improvements are unlikely or impossible? Can we exploit their many connections with other areas or establish new connections? Since matrices are so ubiquitous, this project includes an educational goal of teaching and disseminating research results across many levels, from local high school students to a wide range of research communities in theory and practice who study different facets of matrix operations. The project particularly aims to train undergraduate and graduate students in the theory and applications of matrix operations through research opportunities and the development of a new course.This project focuses more specifically on two fundamental problems which form the backbone for most other computational tasks involving matrices. The first problem is fast matrix multiplication: How quickly can one multiply two input matrices? Matrix multiplication is used in the fastest known algorithms for many fundamental computational problems. It is frequently known to be the bottleneck, meaning faster matrix multiplication is required to speed up the best algorithms. The second problem is fast linear transformation: How quickly can one multiply an input vector times a matrix of interest, such as a Fourier matrix? Algorithms like the Fast Fourier transform and the Fast Walsh-Hadamard transform have been some of the most applicable and impactful algorithms. These transforms also underlie prominent topics throughout computational complexity theory. The investigator has recently proven results about formal barriers to designing faster algorithms for both matrix multiplication and linear transforms. One of the main insights that this project pursues is that ideas from these barrier results can help to make new progress on algorithms.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.