Jun, 2023

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

PDF
TL;DR本研究提出一种简单而新颖的基于约束编程的方法，以查找快速矩阵乘法的非交换算法或提供不可行性证明。实验结果表明，我们可以在短时间内找到 $3 imes 3$ 的矩阵的快速矩阵乘法算法。
matrix multiplicationconstraint programmingnon-commutative algorithmssymmetry-breaking constraintscp optimizer
发现论文，激发创造
  • 通过在线矩阵 - 向量乘积猜想统一和加强动态问题的难度

    探索使用次立方算法解决在线布尔矩阵向量乘法问题的困难程度，并将此问题与许多动态问题的困难程度联系起来，以展示它们之间的多项式时间困难性，并可能为它们展示深入的无条件下界或突破共同的障碍，并为一些未解决的问题提供了一个新的，统一的证明方法。

    Nov, 2015

  • 矩阵乘法：验证强唯一可解谜题

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

    Dec, 2022

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

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

    Jul, 2023

  • 矩阵相乘的无乘法方法

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

    Jun, 2021

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

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

    Apr, 2012

  • 矩阵乘法的群论算法

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

    Nov, 2005

  • 正半定规划的更快速、更简单的宽度独立并行算法

    本文研究了正半定规划的近似算法，提出了一种简单的 NC 并行算法，其迭代次数为 O (1/ϵ³ log³ n)，总工作量近似为因子分解中非零条目数的线性级别。

    Jan, 2012

  • 使用线性规划分解非负矩阵

    本论文提出了一种新的基于线性规划的计算非负矩阵分解的方法，其中关键思想是使用数据中最显著的特征来表示其他特征，以实现低秩近似且扩展到更一般的噪声模型并具有高效可扩展性的算法。

    Jun, 2012

  • 在当前矩阵乘法时间内解决线性规划问题

    本文介绍了一种解决线性规划问题的算法，旨在在对矩阵乘法进行研究后，以次二次时间复杂度解决规模为 n 的问题，同时提出了新的概念，如随机中心路径法和投影矩阵等。

    Oct, 2018

  • 用 Cauchy 矩阵和多项式进行快速近似计算

    本文提出了一种新的数字算法，该算法使用快速多极法来加速多点多项式求值和插值问题的解决，以实现近乎线性的时间。

    Jun, 2015