Memory efficient scheduling of Strassen-Winograd's matrix multiplication algorithm

Brice Boyer (1) , Jean-Guillaume Dumas (1) , Clément Pernet (2) , Wei Zhou (3)

1 LJK - Laboratoire Jean Kuntzmann
2 MOAIS - PrograMming and scheduling design fOr Applications in Interactive Simulation
3 SCG - Symbolic Computation Group

Strassen's algorithm was the first sub-cubic algorithm for matrix multiplication. Its improvement by Winograd led to a highly practicable algorithm. In this report, we propose new schedules of the algorithm, that reduce of the extra memory allocation, by two differents means : either by introducing a few pre-additions, or by overwritting the input matrices.

Domaines: Logiciel mathématique [cs.MS]

Brice Boyer, Jean-Guillaume Dumas, Clément Pernet, Wei Zhou. Memory efficient scheduling of Strassen-Winograd's matrix multiplication algorithm. (International Symposium on Symbolic and Algebraic Computation 2009), Jul 2009, Séoul, South Korea. pp.8. ⟨hal-00163141v4⟩