@Article{Albrecht:2009:AEM,
  author =       "Martin Albrecht and Gregory Bard and William Hart",
  title =        "Algorithm xxx: Efficient Multiplication of Dense Matrices over
                  $GF(2)$",
  journal =      "{ACM} Transactions on Mathematical Software",
  volume =       "37",
  number =       "1",
  accepted =     "7 August 2009",
  upcoming =     "true", 
  abstract =     "
                  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 for Multiplication'' (M4RM) and
                  compare it against other available implementations. Good
                  performance is demonstrated on AMD's Opteron processor
                  and particulary good performance on Intel's Core 2 Duo
                  processor. The open-source M4RI library is available
                  as a stand-alone package as well as part of the \Sage
                  mathematics system.

                  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.",
}