CAREER: Complexity of Matrix Operations

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

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.