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

Question

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

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

Answer 1

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

是的，施特拉森比四个俄罗斯人快。直到对数因子，四个俄罗斯人仍然是 Õ(n^3)，而施特拉森是 Õ(n^log2(7))。

但是，由于 big-O 常数和对数因子在实践中很重要，因此您可能应该使用四个俄罗斯人。