矩阵乘法 - 分治算法 vs Strassen算法，分治算法更快吗？

Question

矩阵乘法 - 分治算法 vs Strassen算法，分治算法更快吗？

performancealgorithmmatrixmatrix-multiplicationdivide-and-conquer

3

据我所知，Strassen矩阵乘法应该是最快的...但分治法在我的测试中显然是最快的...我做错了什么吗？还是这样正确？

指令是：“总耗时然后除以算法执行次数得到解决给定实例所需的时间”

因此，我只需要在每个方法中使用一个“counter ++”，并将时间“recorded/ counter ++”相除。

到目前为止，这是我的时间：（按顺序从上到下：classic、分治、strassen）（大小=矩阵大小）

大小2

经过的时间：8660纳秒

经过的时间：3849纳秒

经过的时间：5377纳秒

大小4

经过的时间：24864纳秒

经过的时间：3080纳秒

经过的时间：5229纳秒

大小8

经过的时间：125435纳秒

经过的时间：2920纳秒

经过的时间：5196纳秒

大小16

经过的时间：867149纳秒

经过的时间：1559纳秒

经过的时间：2853纳秒

大小32

经过的时间：5191721纳秒

经过的时间：972纳秒

经过的时间：1722纳秒

大小64

经过的时间：8155785纳秒

经过的时间：874纳秒

经过的时间：1696纳秒

示例输出以下是我输出4阶矩阵的示例：

第1个随机生成的矩阵： 10 57 33 70 6 12 38 70 20 41 65 98 83 0 31 73 第2个随机生成的矩阵： 11 70 54 79 2 51 38 71 27 53 37 86 48 87 20 41 经典乘法矩阵： 4475 11446 5327 10545 4476 9136 3586 7464 6761 15462 7003 14099 5254 13804 7089 12216 经过的时间：21232纳秒

分治法矩阵乘法： 4475 11446 5327 10545
4476 9136 3586 7464
6761 15462 7003 14099
5254 13804 7089 12216
时间消耗：3042纳秒

Strassen矩阵乘法： 4475 11446 5327 10545
4476 9136 3586 7464
6761 15462 7003 14099
5254 13804 7089 12216
时间消耗：5303纳秒

- user1189352

1

你确定你的分治算法能够给出正确的结果吗？Strassen本质上是一种分治算法；他们采用多次加法和乘法肯定有其原因。 - pad

我实际上会将所有计算出来的矩阵打印到控制台，并确保它们都是相同的。 - user1189352

我同意pad的观点，确保你正在比较结果。不要手动比较。计算并打印均方误差。 - Ben Voigt

我保证我做过了。我会复制粘贴我的输出示例（编辑OP）。 - user1189352

计算并打印均方误差。我不确定如何做到这一点，或者这实际上意味着什么。 - user1189352

分治算法是斯特拉森算法。 - Chris

5个回答

3

只是一个想法：不要只运行一次，运行100次。

实际上，先运行100次而不记录时间，然后再运行100次并记录时间。如果你有时间，甚至可以运行数千次，运行次数越多越好。

System.nanoTime()有时可能非常不准确，特别是在现代计算机上同时运行许多进程的情况下。运行次数越多，这种不准确性对结果的影响就越小。最初的非计时尝试是为了“升级”Java VM，确保每个类都被加载，内存分配和垃圾收集以稳定的节奏进行等等。

另一个改变可以提高测试的准确性，即从实际计算代码中删除所有类型的System.out调用（或任何输出），因为这只会给两个函数添加一个恒定的开销，并扭曲结果。

- biziclop

0

Strassen算法的时间复杂度为 $O(n^{log(7)})$ ，但分治算法的时间复杂度为 $O(n^3)$ （你知道， $log(7)$ 几乎等于 $2.8074$ ）。

当我们使用O（或theta）函数比较一些算法时，我们意味着它们在输入大小趋近于无穷大时更快（或更慢）。

正如您所看到的，对于小的n值，时间复杂度为 $O(n^n)$ 的算法可能比时间复杂度为 $O(1)$ 的算法更慢。这是因为常数因子（只在输入大小较小时才显示其效果）。

因此，如果您的输入大小较小，请使用您知道的最快算法。但是，如果您的输入大小非常大，请使用具有最小渐近时间复杂度的算法。

- Erfan Alimohammadi

0

斯特拉森算法因为不友好缓存而变慢，它只是“理论上”最快的。像您的分治算法这样的“缓存无感知”算法通常更快。

- Feng Shi

0

你的“经典”实现有问题。它不应该慢那么多。在矩阵比较大之前，“经典”应该更快。当然，使用标准矩阵乘法时，4x4的矩阵应该快得多。

- japreiss

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Oleksi · Accepted Answer

Strassen算法的常数因子非常高，因此对于大多数输入，分治算法会更快。尝试使用更大的矩阵（成千上万个元素）运行您的测试，以查看Strassen是否超过了分治算法。