4

I am wondering if Strassen's algorithm can be used for Boolean matrix multiplication? I know that it is used for regular matrix multiplication but not too sure about Boolean.

Also, if it can be, is it faster asymptotically than using Four Russians method and which should be used for Boolean multiplication in general?

Gana
  • 75
  • 1
  • 7

1 Answers1

3

Yes, Strassen can be used for Boolean matrix multiplication. You just do the multiplication in integers and then convert >0 entries of the result to 1.

Yes, Strassen is asymptotically faster than Four Russians. Up to log factors, Four Russians is still Õ(n^3), whereas Strassen is Õ(n^log2(7)).

Since big-O constants and log factors matter in practice, though, you should probably use Four Russians.

David Eisenstat
  • 64,237
  • 7
  • 60
  • 120