The Library
Algorithm 898 : efficient multiplication of dense matrices over GF(2)
Tools
Albrecht, Martin, Bard, Gregory and Hart, William B.. (2010) Algorithm 898 : efficient multiplication of dense matrices over GF(2). ACM Transactions on Mathematical Software, Volume 37 (Number 1). Article: 9. ISSN 00983500

Text
WRAP_Hart_0584144ma270913mat_mult_gf2.pdf  Accepted Version Download (473Kb)  Preview 
Official URL: http://dx.doi.org/10.1145/1644001.1644010
Abstract
We describe an efficient implementation of a hierarchy of algorithms for multiplication of dense matrices over the field with two elements (F2). In particular we present our implementation in the M4RI libraryof StrassenWinograd 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 opensource M4RI library is available as a standalone package as well as part of the Sage mathematics system.
In machine terms, addition in F2 is logicalXOR, and multiplication is logicalAND, thus a machine word of 64 bits allows one to operate on 64 elements of F2 in parallel: at most one CPU cycle for 64 parallel additions or multiplications. As such, elementwise operations over F2 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.
Item Type:  Journal Article 

Alternative Title:  Algorithm XXX: efficient multiplication of dense matrices over GF(2) 
Subjects:  Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software Q Science > QA Mathematics 
Divisions:  Faculty of Science > Mathematics 
Library of Congress Subject Headings (LCSH):  Algorithms, Computer science  Mathematics 
Journal or Publication Title:  ACM Transactions on Mathematical Software 
Publisher:  Association for Computing Machinery, Inc. 
ISSN:  00983500 
Official Date:  January 2010 
Volume:  Volume 37 
Number:  Number 1 
Number of Pages:  14 
Page Range:  Article: 9 
Identification Number:  10.1145/1644001.1644010 
Status:  Peer Reviewed 
Publication Status:  Published 
Access rights to Published version:  Restricted or Subscription Access 
Funder:  Royal Holloway Valerie Myerscough Scholarship, Engineering and Physical Sciences Research Council (EPSRC) 
Grant number:  EP/D079543/1 (EPSRC) 
References:  Aho, A., Hopcroft, J., and Ullman., J. 1974. The Design and Analysis of Computer Algo 
URI:  http://wrap.warwick.ac.uk/id/eprint/6535 
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Actions (login required)
View Item 
Downloads
Downloads per month over past year