Local Search for Fast Matrix Multiplication
Local Search for Fast Matrix Multiplication
复制标题
快速矩阵乘法的本地搜索
DOI：
10.1007/978-3-030-24258-9_10
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Seidl, Martina
中科院分区：
文献类型：
--
作者：
Heule, Marijn;Kauers, Manuel;Seidl, Martina
1976年，Laderman发现了一个只用23次乘法就能计算两个矩阵乘积的方案。从那时起，又提出了一些这样的方案，但没有人知道有多少这样的方案，以及是否存在少于23次乘法的方案。在本文中，我们提出了两个独立的SAT为基础的方法，寻找新的计划，使用23乘法。这两种方法都可以单独计算几百个新方案，组合起来可以计算数千个。本地搜索SAT求解器在此应用中始终优于CDCL求解器。
Laderman discovered a scheme for computing the product of twomatrices using only 23 multiplications in 1976. Since then, some more such schemes were proposed, but nobody knows how many such schemes there are and whether there exist schemes with fewer than 23 multiplications. In this paper we present two independent SAT-based methods for finding new schemes using 23 multiplications. Both methods allow computing a few hundred new schemes individually, and many thousands when combined. Local search SAT solvers outperform CDCL solvers consistently in this application.
登录
查看更多内容
几何与复杂性理论
DOI：
--
发表时间：
2017
期刊：
影响因子：
--
作者：
J. Landsberg
通讯作者：
J. Landsberg
双线性映射计算的多种优化算法Ⅰ.双线性映射的各向同性群
影响因子：
1.1
作者：
H. F. D. Groote
通讯作者：
H. F. D. Groote
DOI：
--
发表时间：
1970
期刊：
影响因子：
--
作者：
R. Brent
通讯作者：
R. Brent
非线性随机微分方程的均方收敛数值方法
DOI：
--
发表时间：
2010
期刊：
IFIP International Conference on Theoretical Computer Science
影响因子：
--
作者：
J. Cortés;L. Jódar;R. Villanueva;L. Villafuerte
通讯作者：
L. Villafuerte