ACM Transactions on Mathematical Software · 2010 · 40 citations · 11 references
ComputingComputer EngineeringComputer ScienceAlgorithmsComputer ArchitectureParallel AlgorithmsAlgorithm AnalysisMatrix ComputationMemory Hierarchy OptimizationParallel ArchitecturesParallel Computer ArchitectureParallel Performance AnalysisCpu OptimizationLocality ConstraintsMatrix MultiplicationMemory LocalityParallel Matrix AlgorithmsParallel Matrix MultiplicationStrassen's Matrix MultiplicationStrassen-winograd Algorithm
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 uo 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 F 2 is logical-XOR, and multiplication is logical-AND, thus a machine word of 64 bits allows one to operate on 64 elements of F 2 in parallel: at most one CPU cycle for 64 parallel additions or multiplications. As such, element-wise operations over F 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.
11
The Magma Algebra System I: The User Language
Wieb Bosma, John Cannon, Catherine Playoust · Journal of Symbolic Computation · 1997 · 7.4K citations
Gaussian elimination is not optimal
Volker Strassen · Numerische Mathematik · 1969 · 2.5K citations
Accuracy and stability of numerical algorithms
Choice Reviews Online · 1996 · 2.1K citations
Choice Reviews Online · 2013 · 253 citations
On multiplication of 2 × 2 matrices
S. Winograd · Linear Algebra and its Applications · 1971 · 217 citations