  We describe an efficient implementation of a hierarchy of algorithms for
multiplication of dense matrices over the field with two elements (GF(2)). In
particular we present our implementation -- in the M4RI library -- of
Strassen-Winograd matrix multiplication and the "Method of the Four Russians"
multiplication (M4RM) and compare it against other available implementations.
Good performance is demonstrated on on AMD's Opteron and particulary good
performance on Intel's Core 2 Duo. The open-source M4RI library is available
stand-alone as well as part of the Sage mathematics software.
  In machine terms, addition in GF(2) is logical-XOR, and multiplication is
logical-AND, thus a machine word of 64-bits allows one to operate on 64
elements of GF(2) in parallel: at most one CPU cycle for 64 parallel additions
or multiplications. As such, element-wise operations over GF(2) are relatively
cheap. In fact, in this paper, we conclude that the actual bottlenecks are
memory reads and writes and issues of data locality. We present our empirical
findings in relation to minimizing these and give an analysis thereof.
