行动算法鸿沟最基础的问题之一，矩阵乘法算法的进攻性显而易见。不但许多矩阵运算齐能被归约到矩阵乘法，而且好多组合问题也不错通过矩阵乘法算法进行加速。
不外，面前计较复杂度 最快的矩阵乘法算法齐出奇复杂，很难在试验中得到应用。（编者注： 时常用来暗意矩阵乘法最优时期复杂度的指数。）
因此，修订矩阵乘法的计较复杂度，关于算法鸿沟的发展大有裨益。举例，既有可能股东此类算法中的新技能改动为实用算法，又能助力证伪联系鸿沟一些猜念念的鸿沟，数学真谛舛错。
近期，清华大学交叉信息琢磨院段然副教师请示团队，经受非对称哈希弥补组合吃亏的步调，通过对 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/科学家研发锂离子导体，结合机器学习与结构瞻望，为下一代固态电解质提供新可能性