CAREER:Matrix Products: Algorithms and Applications

职业：矩阵产品：算法和应用

基本信息

批准号：
1651838
负责人：
Virginia Williams
金额：
$ 40万
依托单位：
Massachusetts Institute of Technology
依托单位国家：
美国
项目类别：
Continuing Grant
财政年份：
2017
资助国家：
美国
起止时间：
2017-03-15 至 2022-02-28
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1651838&HistoricalAwards=false
关键词：
CAREER Matrix Products Algorithms Applications

项目摘要

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.

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