课题基金 / 基金详情

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

项目摘要

项目成果

Virginia Williams的其他基金

相似基金

相关文献

中文摘要
翻译
点击翻译按钮获取中文摘要
英文摘要
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
9
    AF:Small: Algorithms and Limitations for Matrix Multiplication
    AF: Small: Shortest Paths and Distance Parameters: Faster, Fault-Tolerant and More Accurate
    NSF Student Travel Grant for 2019 Theoretical Computer Science (TCS) Women Meeting at Symposium on Theory of Computing (STOC)
    AF: Small: Average-Case Fine-Grained Complexity
    国内基金
    海外基金
    基于Matrix2000加速器的个性小数据在线挖掘
    多模强激光场R-MATRIX-FLOQUET理论
    • 批准号:
      19574020
    • 项目类别:
      面上项目
    • 资助金额:
      7.5万元
    • 批准年份:
      1995
    • 负责人:
      朱颀人
    • 依托单位: