我试图弄清楚在哪个维度上使用Strassen 算法而不是标准乘法更好。我知道 Strassen 算法中有 18 个加法和减法,但我不知道我必须如何计算它。这是一个家庭作业,所以我不想直接回答没有任何解释。任何帮助表示赞赏。
strassen 算法与矩阵的标准乘法
计算科学
线性代数
矩阵
2021-12-13 17:10:51
1个回答
这个问题的答案很大程度上取决于您使用的计算机的特定细节。
在现代实现中,传统的矩阵乘法实现(以 BLAS xGEMM 函数的高度优化版本的形式)使用经过仔细调整以匹配处理器缓存大小的阻塞算法。相比之下,Strassen 的算法对缓存非常不友好,这使得在当代处理器上很难获得良好的性能。
最近的一份 Arxiv 预印本声称,在基于英特尔处理器的系统上,
奥斯汀 R. 本森和格雷巴拉德。实用并行快速矩阵乘法的框架。http://arxiv.org/pdf/1409.2908.pdf
这里还有另一个需要考虑的重要问题——类似 Strassen 的算法在数值上不如传统的块矩阵-矩阵乘法准确。在某些应用程序中,不准确可能会导致应用程序级别出现问题。正因为如此,而且对于合理大小的矩阵而言,性能改进并不是那么大,因此在实践中很少有人使用类似 Strassen 的算法。
其它你可能感兴趣的问题