科学家发现运算速度更快的矩阵乘法算法

　　作为算法领域最基础的问题之一，矩阵乘法算法的重要性不言而喻。不但许多矩阵运算都能被归约到矩阵乘法，而且很多组合问题也可以通过矩阵乘法算法进行加速。

　　不过，目前计算复杂度 最快的矩阵乘法算法都非常复杂，很难在实际中获得应用。（编者注： 通常用来表示矩阵乘法最优时间复杂度的指数。）

　　因此，改进矩阵乘法的计算复杂度，对于算法领域的发展大有裨益。例如，既有可能推动此类算法中的新技术转化为实用算法，又能助力证伪相关领域一些猜想的边界，数学意义重大。

　　近期，清华大学交叉信息研究院段然副教授带领团队，采用非对称哈希弥补组合损失的方法，通过对 CW 张量的八次幂进行分析，打破矩阵乘法最优时间复杂度的指数界限，成功给出了 <2.371866 的新的上界。

　　这里的“上界”指的是矩阵乘法更快的算法，即矩阵乘法最终的计算复杂度的上界。

　　图丨段然（来源：段然）

　　近日，相关论文以《通过非对称哈希算法加快矩阵乘法运算速度》（Faster Matrix Multiplication via Asymmetric Hashing）为题在理论计算机的顶级会议 FOCS 2023 上发表。段然是本文的第一作者。

　　图丨相关论文（来源：FOCS 2023）

　　从矩阵乘法计算复杂度的发展历史说起

　　如上所说，一直以来，矩阵乘法的计算复杂度都非常高。并且，其复杂度 O(n ) 的上界也一直处于“不稳定”状态。

　　其中，需要说明的是，O(n ) 表示两个 n×n 矩阵乘法的时间复杂度。

　　按照定义计算，两个 n×n 矩阵相乘需要O(n 3 ) 的时间，所以 ≤3。同时，又因为计算结果也是一个 n×n 矩阵，有 n 2 个元素，所以矩阵乘法至少需要 O(n 2 ) 的时间，即 ≥2。

　　1969 年，德国数学家沃尔克·施特拉森（Volker Strassen）提出利用分治法改进矩阵乘法，通过构造 7 次乘法计算 2×2 的矩阵乘法的方法，得到 ≤log 7/log 2<2.808。

　　自 Strassen 算法开始，该领域的研究者便想知道 的真正数值。=2，则是很多科研人员都认同的猜想。

　　1982 年，美国计算机科学家维克多·潘（Victor Pan）给出 36133 次乘法计算 44×44 的矩阵乘法的方法，得到

　　此后，如何寻找其他的构造方法以获得更快的算法，就成为该领域一项极具趣味和挑战性的难题。

　　不过，直接寻找更优的分块法非常困难，所以科学家们尝试采用其他的数学方法去构造复杂的分块。

　　据了解，目前最快的方法是基于美国数学家唐·科珀史密斯（Don Coppersmith）和计算机科学家什穆埃尔·维诺格拉德（Shmuel Winograd）于 1990 年提出的 Coppersmith-Winograd 方法，即基于 CW 张量的激光法。

　　基本的 CW 张量算法的复杂度为 <2.38719。不过，上述两位科学家在同一篇论文里又对二阶 CW 张量合并后的算法进行了分析，将复杂度改进到了 <2.375477。

　　2021 年，美国麻省理工学院弗吉尼亚·瓦西列夫斯卡·威廉姆斯（Virginia Vassilevska Williams）教授与合作者通过改进哈希方法，部分弥补了在 4 阶以上边际分布不能完全确定联合分布的问题，从而将复杂度改进到 <2.372860。

　　图丨矩阵乘法计算复杂度的发展历史（来源：段然）

　　作为长期从事算法理论研究的科研人员之一，段然此前的研究成果包括多个新的利用矩阵乘法加速的算法，比如目前最快的瓶颈路和非递减路径算法、单调矩阵的(min,+)- 乘法算法等。

　　“所以，如果改进了矩阵乘法复杂度 ，这些问题的复杂度就都能够迎来进一步改进。”段然表示。

　　利用非对称哈希算法改进矩阵乘法计算复杂度上界

　　但其实，从矩阵乘法计算复杂度的发展历史可以看出，近 30 多年以来，科学家们在改进矩阵乘法计算复杂度方面，并没有找到太多新的突破口。

　　并且，哈希损失本身非常小，又只针对 4 阶以上的张量，所以弥补它对于改进复杂度来说效果不大。

　　据段然介绍，在该研究初期，他曾试图直接改变 CW 张量，但通过计算发现复杂度并未得到真实的改进。

　　“理论研究中的大部分新想法都无法成为实质性的成果，所以需要不断提出新想法并且更加深入地理解问题。”段然说。

　　与此同时，他也邀请了当时就读于“清华学堂计算机科学实验班”（姚班）的大四学生武弘勋和大二学生周任飞一同加入讨论。

　　直到 2022 年春节前，段然尝试将 4 阶 CW 张量方法隔列合并，并写了简单的 C++ 程序来计算复杂度是否得到改进。

　　“结果不但是否定的，复杂度竟然还变差了。在经过反复的程序检查、并确认无误之后，我才发现高阶算法其实存在组合损失。”段然说。

　　这也就是说，高阶的 CW 张量之所以能得到更好的结果，是因为高阶张量能够将低阶张量的矩阵合并成更大的矩阵。

　　但由于各部分分别优化带来的分裂分布不平衡等原因，实际上高阶的 CW 张量中所计算的矩阵总大小要小于低阶，即“组合损失”。

　　段然指出：“在之前的方法中，因为这个损失小于高阶合并带来的收益，所以大家并没有发现它。而在得到这一发现以后，我立即结合之前的非对称哈希想法，最终得到了弥补部分损失的方法。”

　　图丨二阶 CW 张量中分裂分布不平衡造成的组合损失（来源：段然）

　　该团队在经过多次讨论以后，认为用非对称哈希弥补组合损失的方法基本可行，但相较于之前的算法，还存在许多需要进一步处理的理论细节。

　　比如，该方法中多个高阶乘积必须共用一个高阶张量，尽管能保证高阶张量中大部分低阶项都只在一个低阶乘积中出现，但仍然无法避免少部分的低阶项出现在多个乘积中。

　　“所以我们需要删除这样的‘冲突项’，而这却会造成算法所计算的矩阵乘积中含有空洞。”段然说。

　　不过，即使是像 Z=XY 这样的矩阵计算，其中的 X、Y 和 Z 都含有一定比例的空洞。研究人员可以采用随机方法，通过多次操作计算出没有空洞的矩阵乘法。

　　在这种情况下，为了更简便地解决该问题，周任飞提出直接在张量上修复空洞，而非转化为矩阵后再进行修复，这样就只需要修复 Z 上的空洞，从而简化了算法逻辑。自此，该课题组正式确认上述方法能够实现 的改进。

　　如何计算出 新的上界，也就成为了接下来需要攻克的核心问题。

　　“从高阶到 2 阶中很多子张量都可以用非对称的方法处理，然后再旋转 6 次就能够得到对称的解，但这会使需要优化的参数数量远大于之前的算法。”段然解释道。

　　好在武弘勋和周任飞均因为获得全国计算机竞赛一等奖而被保送进入清华大学，后在姚班也依然名列前茅，他们对于算法优化方面非常熟悉。

　　最终，该团队通过上千行的 MATLAB 优化程序，得到了 <2.371866 的上界。

　　目前正联合美国学者进一步改进算法复杂度

　　值得注意的是，拉脱维亚大学安德里斯·安拜尼斯（Andris Ambainis）教授、以色列理工学院尤瓦尔·菲穆斯（Yuval Filmus）助理教授和日本名古屋大学弗朗索瓦·勒加尔（François Le Gall）教授曾于 2015 年给出过一个基于高阶 CW 张量算法无法突破的下界，即 2.3725。

　　很显然，段然团队的结果打破了这个下界。

　　那么，这之中的原因何在？

　　“之前的结果都是直接通过高阶张量合并来得到更优解，并且只有高阶含零张量才会带来优势。但是随着阶数的提高，含零张量的比例呈指数级减小， 改进的幅度也呈指数级减少。这意味着仅通过高阶合并的方法得到的最好结果不会低于 2.3725。”段然解释道。

　　而该课题组之所以能够打破这个下界，是因为他们改变了高阶 CW 张量内部低阶张量的计算方式。

　　“这也说明，很多算法问题中有条件的下界，并不会成为算法发展的限制。”段然表示。

　　不过，该课题组的成果仅仅弥补了组合损失中非常小的一部分。

　　“我们想到的其他方法都无法去除干扰项，进而得到独立的矩阵乘法。我还尝试过改变二阶 CW 张量本身来避免干扰项，但也没有成功。

　　事实上，基于 CW 张量的激光法无法实现 =2，在很大程度上也是因为该方法只利用了张量积中的一小部分变量。”段然指出。

　　另外，值得一提的是，当前矩阵乘法计算复杂度最好的上界是 <2.37155，这一数值是周任飞同学于 2023 年在麻省理工学院访问期间，与威廉姆斯及团队基于非对称哈希方法合作的成果。

　　而目前段然和周任飞正与麻省理工学院和美国哥伦比亚大学的研究人员合作，以进一步改进算法的复杂度，相关研究已经取得一定进展。

　　参考资料：

　　1.R., Duan,H., W, R.,Zhou. et al. Faster Matrix Multiplication via Asymmetric Hashing. In 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), pages 2129–2138, Los Alamitos, CA, USA, Nov 2023. IEEE Computer Society. arXiv:2210.10173v5 https://doi.org/10.48550/arXiv.2210.10173

　　运营/排版：何晨龙

　　01/ 科学家研发新型核酸检测系统，无需依赖昂贵蛋白质酶，单次材料成本低至约0.02美元

　　02/科学家提出固态聚合物电解质新设计，能耐受4.5V的高压，有望成为高能锂金属电池的首选电解质

　　03/科学家解决飞秒激光成丝抖动难题，生成高强度超连续光源，可用于高精度的光学测量

　　04/科学家制备2英寸二硫化钼单晶薄膜，开关比接近10的9次方，推动亚纳米芯片走向实际应用

　　05/科学家研发锂离子导体，结合机器学习与结构预测，为下一代固态电解质提供新可能性