一种计算矩阵乘法的快速算法

Question

在c ++代码eclipse的中间,我需要计算矩阵A和B的乘法,大小为2400*3600(所以尺寸不一样).矩阵存储在浮点二维数组中.它们不稀疏,没有限制.

每次乘法需要很长时间(几分钟),我真的需要减少它,因为我有一个重复5000万次的循环.每次新的A和B应该相乘.欢迎任何类型的建议以减少时间复杂性.(甚至改变存储数据的结构,如果你认为这可能有帮助).例如,如果我将数据存储到一维数组中该怎么办？或者使用向量而不是数组？

在一种特定情况下,第一列始终为1,值为1,-1或0.这个案子有什么想法吗？
在其他情况下,值可以是任何东西.**这些乘法中的一个是X乘以其转置.这个特定的建议有什么建议吗？

Answer 1

我不会愚弄我自己写的:Google for LAPACK或BLAS,两个经过时间考验的数值计算软件包,都优化到了N度.两者都有可以使用的C API.

Answer 2

它肯定有助于存储您的第二个矩阵转置,以便列与缓存行而不是行匹配.L2缓存和主存储器之间的访问时间差异大约为10倍.

@Pegah:如果你看一下矩阵乘法算法,你会发现内部循环看起来像:`sum = 0; for(int k = 0; k <n; ++ k)sum + = a [i] [k]*b [k] [j]; c [i] [j] = sum;`.连续迭代访问`a [i] [0]`,`a [i] [1]`,`a [i] [2]`,这很好,因为它们在内存中彼此相邻存储,所以缓存可以一次从主内存中读取一大块.但你也可以访问`b [0] [j]`,`b [1] [j]`,`b [2] [j]`,它的局部性非常差,并且缓存必须执行许多单独的传输主记忆,非常浪费. (2认同)