作为一种基本的数学运算，矩阵乘法在计算机科学领域有着非常广泛的应用。矩阵乘法的快速算法对科学计算具有重要意义。自1969年Strassen算法出现后，人们就意识到了快速算法的存在，并开始了数十年的探索和研究。当你有两个相同大小的矩阵时，你可以将它们相乘得到第三个矩阵。例如，一对2×2矩阵的乘积也将是具有4个元素的2×2矩阵。也就是说，一对n×n矩阵的乘积是另一个具有n^2个元素的n×n矩阵。因此，矩阵乘法至少需要n^2步，人们理想的计算复杂度是O(n^2)。2020年10月，哈佛大学和麻省理工学院的两位研究人员发表了一篇论文，他们在论文中创建了史上最快的矩阵乘法算法。与之前最快的算法相比，计算复杂度下降了十万分之一。其中，论文第一作者JoshAlman是哈佛大学博士后，主要研究算法设计和复杂性理论。第二作者VassilevskaWilliams是麻省理工学院计算机科学与人工智能实验室(CSAIL)的副教授，致力于将组合和图论工具应用于计算。图为（左）JoshAlman；图为（右）VirginiaVassilevskaWilliams。论文地址：https://arxiv.org/pdf/2010.05846.pdf矩阵相乘法为了理解这个过程以及如何改进它，我们首先来看一对2x2的矩阵，矩阵A和矩阵B。在计算它们的时候产品，矩阵A的相应行和矩阵B的相应列被使用。具体运算方法如下图所示：上述运算称为矩阵的内积，乘积矩阵中其他元素的值可以按照上图所示的方法计算。对于上述情况，这种方法需要8次乘法和一些加法。一般来说，两个nxn矩阵相乘总共需要n^3次乘法运算。随着矩阵变大，矩阵乘法所需的乘法运算次数比加法运算增长得更快。通常，研究人员仅根据所需的乘法次数来衡量矩阵乘法的运算速度。几个世纪以来，人们一直认为n^3是执行矩阵乘法的最快方法。Strassen提出了一组复杂的关系，其中上述8次乘法中的一次被14次加法代替。1981年，ArnoldSch?nhage用这种方法证明了矩阵乘法的计算复杂度可以降低到O(n^2.522)，Strassen后来将这种方法称为激光法。几十年来矩阵乘法的每一次加速都来自激光方法的改进，因为研究人员找到了在两类问题之间切换的有效方法。Alman和VassilevskaWilliams的新方法也是如此。在矩阵乘法中，两个nxn矩阵的计算复杂度可以表示为，其中之前最快的记录是由Fran?oisLeGall在2014年创造的，其中：而在Alman和VassilevskaWilliams的新方法中：具体而言，它们的复杂度为减少到O(n^2.3728596)，创造了最快矩阵乘法的新记录。值得一提的是，2012年VassilevskaWilliams将这个数字降到了n^2.372873，但是在2014年被Fran?oisLeGall的n^2.3728639打破了。不过这种做法虽然带来了一些矩阵乘法速度的提升，但是可以看出改进越来越小。Fran?oisLeGall，日本名古屋大学数学研究生院副教授。事实上，Alman和VassilevskaWilliams的改进可能已经达到了激光方法的极限，但离最终的理论目标还很远。“使用本研究中的方法不太可能将复杂性降低到O(n^2)，”加州理工学院计算机科学教授ChrisUmans说。如果要实现，就需要寻找新的方法。
