CAREER:Matrix Products: Algorithms and Applications

矩阵相乘的方法通常用于处理各种应用中的计算问题：在网络中寻找良好的路由，网络中的模式检测，计算机图形和动画中的模拟运动，生物化学中的蛋白质和RNA结构预测，量子力学，机器学习，电子学，科学计算以及任何需要求解线性方程组的问题。更快地将大型矩阵相乘的能力将对世界产生切实的影响。在过去的50年里，计算机科学家们一直在开发一个丰富的矩阵乘法算法的数学理论;仍然不清楚矩阵相乘的速度有多快，也不清楚最好的算法是什么样子的。 PI的主要目标是深化和扩展矩阵乘法的理论，并寻找更快的算法。矩阵乘法的研究最多的版本是当矩阵元素来自一个基础环，如整数（Z），并且“加”和“乘”操作是在Z上的加法和乘法。环矩阵乘法的算法进展是算法独创性的一个很好的例子。几十年来，琐碎的方法被认为是最佳的，直到深入的理论带来了重大和令人惊讶的改进。环矩阵乘法算法的理论研究主要集中在矩阵乘法的指数“omega”的确定上，而指数“omega”被认为是衡量环矩阵乘法算法研究进展的主要指标。数字omega是最小的真实的数字，对于该数字，存在使用n^（omega+o（1））个操作（数字的加法和乘法）将两个n维的方阵相乘的算法。由于输出的大小为n^2，因此omega至少为2; PI获得了最近的边界omega 2.373。PI旨在研究改进Omega和相关参数的新方法，其长期目标是设计快速实用的算法。上述令人印象深刻的改进仅适用于环矩阵乘法。然而，在许多应用中，需要不同的、可能更复杂的矩阵产品。例如，在计算网络中的最短路径时，人们依赖于真实的矩阵的所谓距离积，对于该距离积，“加”运算是最小的，而“乘”运算是加法。矩阵积不再是环上的，而是半环上的。非环矩阵乘积不像环矩阵乘法那样容易理解;一些非环矩阵乘积，比如距离乘积，似乎甚至不承认比其定义所遵循的蛮力算法快得多的算法。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.