Mat*_*att 9 algorithm complexity-theory linear-algebra matrix-multiplication
对于一个班级,我的老师提出的问题是将矩阵乘以其转置的算法成本.使用标准的3循环矩阵乘法算法,效率为O(N ^ 3),我想知道是否有办法操纵或利用矩阵*矩阵转置来获得更快的算法.我知道当你将矩阵乘以它的转置时,你必须计算较少的矩阵,因为它是对称的,但我想不出如何操作一个可能小于O(n ^ 3)的算法.
我知道像Coppensmith和Straussen这样的算法是更快的通用矩阵乘法算法,但任何人都可以提供有关如何计算利用转置的任何提示或见解？
谢谢
截至目前，这种特定乘法尚不存在任何渐近屏障破坏特性。
明显的优化是利用产品的对称性。也就是说，第[i][j]th条目等于第[j][i]th条目。
对于特定于实现的优化，您可以执行大量缓存。在大型矩阵乘法中，大量时间花费在内存和 CPU 之间的数据传输上。因此，CPU 设计者实现了一种智能缓存系统，将最近使用的内存存储在称为缓存的小内存部分中。除此之外，他们还使得附近的内存也被缓存。这是因为大量内存 IO 是由于从数组读取/写入数组而产生的，而数组是顺序存储的。
由于矩阵的转置只是索引交换的同一矩阵，因此在矩阵中缓存值可能会产生两倍以上的影响。