Clever Geek Handbook

Can Strassen's algorithm be used to multiply a boolean matrix?

I'm wondering if Strassen's algorithm can be used to multiply a boolean matrix? I know it is used for regular matrix multiplication, but not too sure about Boolean.

Also, if so, is it faster asymptotically than using the four Russians method and which should be used for boolean multiplication in general?

+3


source to share


1 answer


Yes, Strassen can be used to multiply a Boolean matrix. You just do the multiplication on integers and then convert> 0 records of the result to 1.

Yes, Strassen is asymptotically faster than four Russians. Before logarithmic factors, the four Russians are still & Otilde; (n ^ 3) whereas Strassen is & Otilde; (n ^ log2 (7)).



Since big O constants and log factors are important in practice, you should probably use four Russians.

+2


source






More articles:


All Articles