Strassen算法可以用于布尔矩阵乘法吗？

Question

我想知道Strassen算法是否可以用于布尔矩阵乘法？我知道它用于常规矩阵乘法，但对布尔不太确定。

此外，如果可以的话，它是否比使用四个俄罗斯人方法渐近地更快，并且通常应该将其用于布尔乘法？

Answer 1

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

是的，Strassen 比四个俄罗斯人渐进快。根据对数因子，四个俄罗斯人仍然是 Õ(n^3)，而 Strassen 是 Õ(n^log2(7))。

尽管大 O 常量和对数因子在实践中很重要，但您可能应该使用四个俄罗斯人。