矩阵乘法
散列函数
施特拉森演算法
乘法(音乐)
上下界
指数
张量(固有定义)
数学
欧米茄
基质(化学分析)
离散数学
组合数学
计算机科学
量子
纯数学
物理
量子力学
数学分析
语言学
哲学
材料科学
计算机安全
复合材料
作者
Ran Duan,Hongxun Wu,Renfei Zhou
标识
DOI:10.1109/focs57990.2023.00130
摘要
Fast matrix multiplication is one of the most fundamental problems in algorithm research. The exponent of the optimal time complexity of matrix multiplication is usually denoted by $\omega$. This paper discusses new ideas for improving the laser method for fast matrix multiplication. We observe that the analysis of higher powers of the Coppersmith-Winograd tensor [Coppersmith & Winograd 1990] incurs a “combination loss”, and we partially compensate for it using an asymmetric version of CW’s hashing method. By analyzing the eighth power of the CW tensor, we give a new bound of $\omega/\lt2.371866$, which improves the previous best bound of $\omega/\lt2.372860$ [Alman & Vassilevska Williams 2020]. Our result breaks the lower bound of 2.3725 in [Ambainis, Filmus & Le Gall 2015] because of the new method for analyzing component (constituent) tensors.
科研通智能强力驱动
Strongly Powered by AbleSci AI