Strassen算法能否用于布尔矩阵乘法？

Question

4

我想知道 Strassen 算法是否适用于布尔矩阵乘法？我知道它适用于普通矩阵乘法，但不确定是否适用于布尔矩阵。

另外，如果可以使用 Strassen 算法，那么在渐近意义下它是否比使用 Four Russians 方法更快？一般来说，应该使用哪种方法进行布尔乘法？

- Gana

看起来这个问题应该属于math.stackexchange.com部分。 - ChatterOne

1个回答

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

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

- David Eisenstat · Accepted Answer

是的，Strassen算法可以用于布尔矩阵乘法。您只需在整数中进行乘法，然后将结果中>0的条目转换为1即可。

是的，与四个俄罗斯人相比，Strassen算法在渐近意义下更快。在对数因子上，四个俄罗斯人仍然是Õ(n^3)，而Strassen是Õ(n^log2(7))。

但是，在实际应用中，大O常数和对数因子是非常重要的，因此您应该使用四个俄罗斯人算法。