CAREER:Matrix Products: Algorithms and Applications

矩阵乘法的方法通常用于解决各种各样的计算问题：在网络中寻找良好的路线，在网络中进行模式检测，在计算机图形学和动画中模拟运动，在生物化学中预测蛋白质和RNA结构，在量子力学、机器学习、电子学、科学计算以及任何需要解决线性方程组的问题。更快地将大型矩阵相乘的能力将对世界产生切实的影响。在过去的五十年里，计算机科学家已经开发了丰富的矩阵乘法算法的数学理论；然而，矩阵相乘的速度究竟有多快还不清楚，也不清楚最好的算法是什么样子。PI的主要目标是深化和扩展矩阵乘法理论，并寻找更快的算法来解决问题。矩阵乘法研究最多的版本是当矩阵条目来自一个底层环，比如整数(Z)时，“加”和“乘”操作是对Z的加法和乘法。环矩阵乘法的算法进展是算法独创性的一个主要例子。几十年来，这种简单的方法被认为是最优的，直到深入的理论带来了重大而令人惊讶的改进。环矩阵乘法算法的理论研究旨在确定矩阵乘法的指数，这被认为是衡量该问题进展的主要指标。数字是最小的实数，有一个算法可以用n^（+o(1)）运算（数字的加法和乘法）将两个n维的方阵相乘。因为输出的大小是n^2，至少是2；最近的边界2.373是由PI得到的。PI的目标是研究新的方法来改进ω和相关参数的界，长期目标是设计一个快速实用的算法。上述令人印象深刻的改进仅适用于环矩阵乘法。然而，在许多应用中，需要不同的、可能更复杂的矩阵乘积。例如，在计算网络中的最短路径时，人们依赖于所谓的实矩阵的距离积，其中“加”操作是最小的，“乘”操作是加法。矩阵乘积不再是环上的，而是半环上的。非环矩阵乘积不像环矩阵乘法那样容易理解；有些算法，比如距离乘积，甚至不承认比从它们的定义中得出的暴力算法更快的算法。PI的第二个主要目标是研究各种各样的非环矩阵乘积，为它们开发算法，并扩大和加强它们的应用。这个项目有几个教育目标。这些包括指导本科生和研究生，开发与所描述的主题直接相关的新课程，并将这些主题纳入现有的核心算法课程。讲座和项目材料将在课程网站上提供给公众。PI全心全意地致力于多样性。PI在招收和指导本科生和研究生方面都有经验，并将继续在寻找和招收来自不同文化和背景的学生方面发挥积极作用。

Methods for multiplying matrices are routinely used to approach computational problems from a huge variety of applications: finding good routes in networks, pattern detection in networks, simulating motion in computer graphics and animation, protein and RNA structure prediction in biochemistry, questions in quantum mechanics, machine learning, electronics, scientific computing, and anywhere linear systems of equations need to be solved. The ability to multiply large matrices faster would have tangible impact on the world. For the past fifty years, computer scientists have been developing a rich mathematical theory of matrix multiplication algorithms; still, it is not clear exactly how fast matrices can be multiplied, nor what the best algorithms would even look like. The main goal of the PI is to deepen and extend the theory of matrix multiplication, and to search for faster algorithms for the problem. The most studied version of matrix multiplication is when the matrix entries come from an underlying ring such as the integers (Z), and the "plus" and "times" operations are addition and multiplication over Z. The algorithmic progress on ring matrix multiplication is a prime example of algorithmic ingenuity. For decades the trivial approach was deemed optimal until deep theory led to significant and surprising improvements. The theoretical study of ring matrix multiplication algorithms aims to pinpoint the exponent "omega" of matrix multiplication, considered to be the main measure of progress on the problem. The number omega is the smallest real number for which there is an algorithm that multiplies two square matrices of dimension n using n^(omega+o(1)) operations (additions and multiplications of numbers). Since the output has size n^2, omega is at least 2; the most recent bound omega 2.373 was obtained by the PI. The PI aims to investigate new approaches to improving the bound on omega and related parameters, with a long-term goal of designing a fast and practical algorithm. The impressive improvements above only apply to ring matrix multiplication. However, in many applications, different, potentially more complex matrix products are needed. For instance, in computing shortest paths in a network, one relies on the so called distance product of real matrices for which the "plus" operation is minimum and the "times" operation is addition. The matrix product is no longer over a ring, but rather over a semiring. Non-ring matrix products are not as well understood as ring matrix multiplication; some, such as the distance product, don't even seem to admit much faster algorithms than the brute-force algorithm that follows from their definition. The second major goal of the PI is to study a large variety of non-ring matrix products, develop algorithms for them, and broaden and strengthen their applications. This project has several educational goals. These include mentoring undergraduate and graduate students, the development of new courses directly related to the described topics, and incorporating these topics into existing core algorithms courses. The lectures and project materials will be available on the course website for the general public. The PI is wholeheartedly committed to diversity. The PI has experience in recruiting and mentoring both undergraduate and graduate minority students, and will continue to take an active role in seeking and recruiting students from diverse cultures and backgrounds.