CAREER:Matrix Products: Algorithms and Applications
CAREER:Matrix Products: Algorithms and Applications
批准号:
1651838
负责人:
Virginia Williams
金额:
$40.0万
依托单位国家:
美国
项目类别:
Continuing Grant
财政年份:
2017
资助国家:
美国
项目状态:
已结题
起止时间:
2017-03-15 至 2022-02-28
中文摘要
矩阵乘法的方法通常用于解决各种各样的计算问题:在网络中寻找良好的路线,在网络中进行模式检测,在计算机图形学和动画中模拟运动,在生物化学中预测蛋白质和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.
期刊论文(11)
专著(0)
科研奖励(0)
会议论文
登录
查看更多内容
Algorithms, Reductions and Equivalences for Small Weight Variants of All-Pairs Shortest Paths
全对最短路径的小权值变体的算法、约简和等价
DOI:
--
发表时间:
2021
期刊:
and Programming (ICALP 2021
影响因子:
--
作者:
[Chan, Timothy M., Vassilevska Williams, Virginia, Xu, Yinzhan]
通讯作者:
Xu, Yinzhan
DOI:
10.1137/17m112720x
发表时间:
2019-01-01
期刊:
SIAM JOURNAL ON COMPUTING
影响因子:
1.6
作者:
[Bringmann, Karl, Grandoni, Fabrizio, Williams, Virginia Vassilevska]
通讯作者:
Williams, Virginia Vassilevska
Faster Monotone Min-Plus Product, Range Mode, and Single Source Replacement Paths
更快的单调最小加产品、范围模式和单一来源替换路径
DOI:
--
发表时间:
2021
期刊:
and Programming (ICALP 2021
影响因子:
--
作者:
[Gu, Yuzhou, Polak, Adam, Vassilevska Williams, Virginia, Xu, Yinzhan]
通讯作者:
Xu, Yinzhan
Faster Replacement Paths and Distance Sensitivity Oracles
更快的替换路径和距离敏感性预言机
DOI:
10.1145/3365835
发表时间:
2019
期刊:
ACM Transactions on Algorithms
影响因子:
1.3
作者:
[Grandoni, Fabrizio, Williams, Virginia Vassilevska]
通讯作者:
Williams, Virginia Vassilevska
DOI:
10.4230/lipics.itcs.2018.25
发表时间:
2018
期刊:
9th Innovations in Theoretical Computer Science Conference (ITCS 2018
影响因子:
--
作者:
[Alman, J., Vassilevska Williams, V.]
通讯作者:
Vassilevska Williams, V.
共 9 条
AF:Small: Algorithms and Limitations for Matrix Multiplication
-
批准号:2330048
-
项目类别:Standard Grant
-
资助金额:$60.0万
-
财政年份:2023
-
负责人:Virginia Williams
-
依托单位:
AF: Small: Shortest Paths and Distance Parameters: Faster, Fault-Tolerant and More Accurate
-
批准号:2129139
-
项目类别:Standard Grant
-
资助金额:$50.0万
-
财政年份:2021
-
负责人:Virginia Williams
-
依托单位:
NSF Student Travel Grant for 2019 Theoretical Computer Science (TCS) Women Meeting at Symposium on Theory of Computing (STOC)
-
批准号:1931307
-
项目类别:Standard Grant
-
资助金额:$1.0万
-
财政年份:2019
-
负责人:Virginia Williams
-
依托单位:
AF: Small: Average-Case Fine-Grained Complexity
-
批准号:1909429
-
项目类别:Standard Grant
-
资助金额:$50.0万
-
财政年份:2019
-
负责人:Virginia Williams
-
依托单位:
AF: Small: Graphs and structures for distance estimation
-
批准号:1740525
-
项目类别:Standard Grant
-
资助金额:$21.9万
-
财政年份:2017
-
负责人:Virginia Williams
-
依托单位:
AF: Medium: Collaborative Research: Hardness in Polynomial Time
-
批准号:1740519
-
项目类别:Continuing Grant
-
资助金额:$45.31万
-
财政年份:2017
-
负责人:Virginia Williams
-
依托单位:
BSF:2012338:Shortest Paths: Upper and lower bounds
-
批准号:1740501
-
项目类别:Standard Grant
-
资助金额:$0.24万
-
财政年份:2017
-
负责人:Virginia Williams
-
依托单位:
AF: Medium: Collaborative Research: Hardness in Polynomial Time
-
批准号:1514339
-
项目类别:Continuing Grant
-
资助金额:$60.0万
-
财政年份:2015
-
负责人:Virginia Williams
-
依托单位:
AF: Small: Graphs and structures for distance estimation
-
批准号:1528078
-
项目类别:Standard Grant
-
资助金额:$30.0万
-
财政年份:2015
-
负责人:Virginia Williams
-
依托单位:
EAGER: Formal models of intention
-
批准号:1347214
-
项目类别:Standard Grant
-
资助金额:$15.0万
-
财政年份:2013
-
负责人:Virginia Williams
-
依托单位:
BSF:2012338:Shortest Paths: Upper and lower bounds
-
批准号:1330843
-
项目类别:Standard Grant
-
资助金额:$4.5万
-
财政年份:2013
-
负责人:Virginia Williams
-
依托单位:
BSF:2012338:Shortest Paths: Upper and lower bounds
-
批准号:1417238
-
项目类别:Standard Grant
-
资助金额:$4.5万
-
财政年份:2013
-
负责人:Virginia Williams
-
依托单位:
国内基金
海外基金
基于Matrix2000加速器的个性小数据在线挖掘
-
批准号:2020JJ4669
-
项目类别:省市级项目
-
资助金额:--
-
批准年份:2020
-
负责人:甘新标
-
依托单位:
多模强激光场R-MATRIX-FLOQUET理论
-
批准号:19574020
-
项目类别:面上项目
-
资助金额:7.5万元
-
批准年份:1995
-
负责人:朱颀人
-
依托单位: