Efficient dense Gaussian elimination over the finite field with two elements. available at http://arxiv.org/abs/1111.6549

In this work we describe an efficient implementation of a hierarchy of algorithms for Gaussian elimination upon dense matrices over the field with two elements (F2). We discuss both well-known and new algorithms as well as our implementations in the M4RI library, which has been adopted into SAGE. The focus of our discussion is a block iterative algorithm for PLE decom-position which is inspired by the M4RI algorithm. The implementation presented in this work provides considerable performance gains in practice when compared to the previously fastest im-plementation. We provide performance figures on x86 64 CPUs to demonstrate the alacrity of our approach