Matrix multiplication over GF(2) and the M4RI library
We will present and discuss our implementation of a hierarchy of matrix multiplication algorithms for dense matrices over the field with two elements (GF(2)). In particular we will discuss our implementation – in the M4RI library – of Strassen-Winograd matrix multiplication and the “Method of the Four Russians” (M4RM) multiplication on x86_64 CPUs and compare this implementation against other available dedicated implementations for GF(2). We will also present some preliminary results for parallel matrix multiplication on SMP machines. The presented work is joint work with Gregory Bard and Bill Hart.