Nov, 2015

通过在线矩阵 - 向量乘积猜想统一和加强动态问题的难度

PDF
TL;DR探索使用次立方算法解决在线布尔矩阵向量乘法问题的困难程度，并将此问题与许多动态问题的困难程度联系起来，以展示它们之间的多项式时间困难性，并可能为它们展示深入的无条件下界或突破共同的障碍，并为一些未解决的问题提供了一个新的，统一的证明方法。
online boolean matrix-vector multiplicationpolynomial time hardnesscombinatorial algorithmsdynamic problemsunconditional lower bounds
发现论文，激发创造
  • 矩阵乘法：验证强唯一可解谜题

    在构建约束解算算法的基础上，我们对计算中出现的强唯一可解难题进行了系统的计算机辅助搜索，并针对小常数的宽度 k，我们发现的强唯一可解难题暗示着在指数为 ω ≤ 2.66 的情况下以 O (n^ω) 的时间运行的矩阵乘法算法。

    Dec, 2022

  • 不流泪的快速矩阵乘法：一种约束编程方法

    本研究提出一种简单而新颖的基于约束编程的方法，以查找快速矩阵乘法的非交换算法或提供不可行性证明。实验结果表明，我们可以在短时间内找到 $3 imes 3$ 的矩阵的快速矩阵乘法算法。

    Jun, 2023

  • 高效可验证的强唯一可解拼图与矩阵乘法

    研究了一种解决快速矩阵乘法计算的算法，介绍了高效验证的可简化的独特可解谜题，指出可以通过可简化的 SUSPs 实现和无限个 SUSPs 同样强的矩阵乘法上限，利用电脑搜索构建了比现有更大的 SUSPs 用于提高矩阵乘法上限。

    Jul, 2023

  • 在线矩阵 - 向量 (max，+)- 乘法加速解码隐马尔可夫模型

    本文提出了一种新的算法，通过多项式预处理矩阵来解决时间均匀的 HMM 中 MAPD 问题，并将最坏情况下的运行时间改善了一个对数因子。

    Nov, 2015

  • 矩形矩阵乘法的更快算法

    本文主要研究矩阵乘法相关问题，提出了一种新算法，相比于之前的算法能够更快地计算带有权值的有向图中的所有点对最短路径问题和稀疏矩阵的乘法问题。

    Apr, 2012

  • 关于帽集与矩阵乘法的群论方法

    该论文通过限制阿贝尔群中三色无和集的大小，阐述了如何从阿贝尔群中获取矩阵乘法乘积的指数 $ω=2$ 的具体猜想，从而得出这一框架无法获得 $ω=2$ 的结论，并证明了 Tao 提出的张量秩的一个变体可以量化几何不变理论中的不稳定张量的概念。

    May, 2016

  • 利用 Coppersmith-Winograd 张量的幂次改进矩阵乘法

    本文提出一种利用张量幂次的对称和非对称结构实现矩阵乘法复杂度下界优化的新方法，通过分析 Coppersmith-Winograd 张量的四次幂进一步降低矩阵乘法复杂度下界，并得到了许多基于矩阵乘法的问题的新解法。

    Aug, 2017

  • 矩阵乘法的群论算法

    利用群论方法改进矩阵乘法算法，并描述了多个实现矩阵乘法指数小于 3 的交替积群族，最快的指数为 2.41。同时提出了两个关于改进算法的猜想，其一组合学的，其二代数学的，证明其中任意一个即可使得矩阵乘法的指数为 2。

    Nov, 2005

  • 压缩矩阵乘法

    介绍一种利用哈希函数、多项式乘法和误差纠正编码的简单算法来近似计算两个实数矩阵的乘积、计算精确的乘积矩阵，并可以以近线性时间内恢复其显著项。

    Aug, 2011

  • 矩阵相乘的无乘法方法

    介绍了一种学习算法，用于高效的近似矩阵乘法，其常用特性是需要零次乘积添加操作。实验表明，它比现有方法快 10 倍以上，而且比确切矩阵积快 100 倍。此外，核心操作 - 混合哈希，平均和字节混洗，可以是机器学习的更有前途的构建块，而不是近期研究和硬件投资重点的稀疏、因式分解和 / 或标量量化矩阵乘积。

    Jun, 2021