Efficient Multiplication of Dense Matrices over GF(2)

Details Efficient Multiplication of Dense Matrices over GF(2) Efficient Multiplication of Dense Matrices over GF(2)

2008-11-11

arxiv.org/abs/0811.1714v1

Computer Science

Mathematical Software

Scientific paper

10.1145/1644001.1644010

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.

Affiliated with

Also associated with

No associations

Rating

Efficient Multiplication of Dense Matrices over GF(2) does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Efficient Multiplication of Dense Matrices over GF(2), we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficient Multiplication of Dense Matrices over GF(2) will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-543843