Algorithm 898 : efficient multiplication of dense matrices over GF(2)

Article English OPEN
Albrecht, Martin ; Bard, Gregory ; Hart, William B. (2010)

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.\ud \ud 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.\ud
  • References (20)
    20 references, page 1 of 2

    Aho, A., Hopcroft, J., and Ullman., J. 1974. The Design and Analysis of Computer Algorithms. 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 Grobner 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.

  • Similar Research Results (1)
  • Metrics
    0
    views in OpenAIRE
    0
    views in local repository
    32
    downloads in local repository

    The information is available from the following content providers:

    From Number Of Views Number Of Downloads
    Warwick Research Archives Portal Repository - IRUS-UK 0 32
Share - Bookmark