The Library
Algorithm 898 : efficient multiplication of dense matrices over GF(2)
Tools
Tools
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, Vol.37 (No.1). Article: 9. ISSN 0098-3500
Full text not available from this repository.
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 (F-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 F2 is logical-XOR, and multiplication is logical-AND, 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, element-wise 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 |
|---|---|
| Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software Q Science > QA Mathematics |
| Divisions: | Faculty of Science > Mathematics |
| Journal or Publication Title: | ACM Transactions on Mathematical Software |
| Publisher: | Association for Computing Machinery, Inc. |
| ISSN: | 0098-3500 |
| Date: | January 2010 |
| Volume: | Vol.37 |
| Number: | No.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 Scholership, Engineering and Physical Sciences Research Council (EPSRC) |
| Grant number: | EP/D079543/1 (EPSRC) |
| URI: | http://wrap.warwick.ac.uk/id/eprint/6535 |
Data sourced from Thomson Reuters' Web of Knowledge
Actions (login required)
 |
View Item |
