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 0098-3500

Preview

Text
WRAP_Hart_0584144-ma-270913-mat_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 (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

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:

0098-3500

Official Date:

January 2010

Dates:

Date	Event
January 2010	Published

Volume:

Volume 37

Number:

Number 1

Number of Pages:

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-
rithms. Addison-Wesley.
Arlazarov, V., Dinic, E., Kronrod, M., and Faradzev, I. 1970. On economical construction
of the transitive closure of a directed graph. Dokl. Akad. Nauk. 194, 11. (in Russian), English
Translation in Soviet Math Dokl.
Bard, G. 2008. Matrix inversion (or LUP-factorization) via the Method of Four Russians, in
�(n3= log n) time. In Submission.
Bard, G. V. 2006. Accelerating Cryptanalysis with the Method of Four Russians. Cryptology
ePrint Archive, Report 2006/251. Available at http://eprint.iacr.org/2006/251.pdf.
Bard, G. V. 2007. Algorithms for solving linear and polynomial systems of equations over �nite
�elds with applications to cryptanalysis. Ph.D. thesis, University of Maryland.
Bosma, W., Cannon, J., and Playoust, C. 1997. The MAGMA Algebra System I: The User
Language. In Journal of Symbolic Computation 24. Academic Press, 235{265.
Brickenstein, M. and Dreyer, A. 2007. PolyBoRi: A framework for Gr�obner basis computations
with Boolean polynomials. In Electronic Proceedings of MEGA 2007. Available at http:
//www.ricam.oeaw.ac.at/mega2007/electronic/26.pdf.
Dumas, J.-G. and Pernet, C. 2007. Memory e�cient scheduling of Strassen-Winograd's
matrix multiplication algorithm. Available at http://www.citebase.org/abstract?id=oai:
arXiv.org:0707.2347.
Fog, A. 2008. Optimizing software in C++. Available at http://www.agner.org/optimize.
Gray, F. 1953. Pulse code communication. US Patent No. 2,632,058.
Higham, N. 2002. Accuracy and Stability of Numerical Algorithms, second ed. Society for
Industrial and Applied Mathematics.
Huss-Lederman, S., Jacobson, E. M., Johnson, J. R., Tsao, A., and Turnbull, T. 1996.
Implementation of Strassen's algorithm for matrix multiplication. In Proceedings of Supercom-
puting '96.
Pernet, C. 2001. Implementation of Winograd's algorithm over �nite Fields using ATLAS Level3
Blas. Tech. rep., ID-Laboratory.
Ringe, M. 2007. Meataxe 2.4.8. Available at http://www.math.rwth-aachen.de/~MTX/.
Steel, A. 2009. Private communication.
Stein, W. et al. 2008. SAGE Mathematics Software (Version 3.3). The Sage Development
Team. Available at http://www.sagemath.org.
Strassen, V. 1969. Gaussian elimination is not optimal. Nummerische Mathematik 13, 354{256.
The GAP Group 2007. GAP { Groups, Algorithms, and Programming, Version 4.4.10. The
GAP Group.
Warren, H. S. 2002. Hacker's Delight. Addison-Wesley Longman Publishing Co., Inc., Boston,
MA, USA.
Winograd, S. 1971. On multiplication of 2 x 2 matrices. Linear Algebra and Application 4,
381{388.