权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

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”，该指数被认为是衡量问题进展的主要指标。欧米伽是最小实数，对于它，有一种算法可以使用n^(欧米伽+o(1))运算(数字的加法和乘法)将n维的两个方阵相乘。因为输出的大小是n^2，所以omega至少是2；最近的界限omega 2.373是由PI获得的。PI旨在研究新的方法来改善omega和相关参数的界限，长期目标是设计一个快速而实用的算法。上述令人印象深刻的改进仅适用于环矩阵乘法。然而，在许多应用中，需要不同的、可能更复杂的矩阵乘积。例如，在计算网络中的最短路径时，人们依赖于实数矩阵的所谓距离乘积，对该实数矩阵的“加”运算是最小的，而“乘”运算是加法。矩阵乘积不再位于环上，而是位于半环上。非环形矩阵乘积没有环形矩阵乘法理解得那么好；一些算法，如距离乘积，似乎并不比根据它们的定义得出的蛮力算法快得多。PI的第二个主要目标是研究大量的非环矩阵乘积，为它们开发算法，并扩大和加强它们的应用。这个项目有几个教育目标。这些措施包括指导本科生和研究生，开发与所述主题直接相关的新课程，以及将这些主题纳入现有的核心算法课程。讲座和项目材料将在课程网站上向公众开放。国际和平协会全心全意致力于多样性。国际学生联合会在招收和指导少数民族本科生和研究生方面有经验，并将继续在寻找和招收来自不同文化和背景的学生方面发挥积极作用。