Strassen’s 2 × 2 matrix multiplication algorithm: a conceptual perspective
Publikation: Bidrag til tidsskrift › Tidsskriftartikel › Forskning › fagfællebedømt
Standard
Strassen’s 2 × 2 matrix multiplication algorithm : a conceptual perspective. / Ikenmeyer, Christian; Lysikov, Vladimir.
I: Annali dell'Universita di Ferrara, Bind 65, Nr. 2, 01.11.2019, s. 241-248.Publikation: Bidrag til tidsskrift › Tidsskriftartikel › Forskning › fagfællebedømt
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
TY - JOUR
T1 - Strassen’s 2 × 2 matrix multiplication algorithm
T2 - a conceptual perspective
AU - Ikenmeyer, Christian
AU - Lysikov, Vladimir
PY - 2019/11/1
Y1 - 2019/11/1
N2 - The main purpose of this paper is pedagogical. Despite its importance, all proofs of the correctness of Strassen’s famous 1969 algorithm to multiply two 2 × 2 matrices with only seven multiplications involve some basis-dependent calculations such as explicitly multiplying specific 2 × 2 matrices, expanding expressions to cancel terms with opposing signs, or expanding tensors over the standard basis, sometimes involving clever simplifications using the sparsity of tensor summands. This makes the proof nontrivial to memorize and many presentations of the proof avoid showing all the details and leave a significant amount of verifications to the reader. In this note we give a short, self-contained, basis-independent proof of the existence of Strassen’s algorithm that avoids these types of calculations. We achieve this by focusing on symmetries and algebraic properties. Our proof can be seen as a coordinate-free version of the construction of Clausen from 1988, combined with recent work on the geometry of Strassen’s algorithm by Chiantini, Ikenmeyer, Landsberg, and Ottaviani from 2016.
AB - The main purpose of this paper is pedagogical. Despite its importance, all proofs of the correctness of Strassen’s famous 1969 algorithm to multiply two 2 × 2 matrices with only seven multiplications involve some basis-dependent calculations such as explicitly multiplying specific 2 × 2 matrices, expanding expressions to cancel terms with opposing signs, or expanding tensors over the standard basis, sometimes involving clever simplifications using the sparsity of tensor summands. This makes the proof nontrivial to memorize and many presentations of the proof avoid showing all the details and leave a significant amount of verifications to the reader. In this note we give a short, self-contained, basis-independent proof of the existence of Strassen’s algorithm that avoids these types of calculations. We achieve this by focusing on symmetries and algebraic properties. Our proof can be seen as a coordinate-free version of the construction of Clausen from 1988, combined with recent work on the geometry of Strassen’s algorithm by Chiantini, Ikenmeyer, Landsberg, and Ottaviani from 2016.
KW - Coordinate-free
KW - Elementary
KW - Matrix multiplication
KW - Strassen’s algorithm
UR - http://www.scopus.com/inward/record.url?scp=85067808056&partnerID=8YFLogxK
UR - https://arxiv.org/abs/1708.08083
U2 - 10.1007/s11565-019-00318-1
DO - 10.1007/s11565-019-00318-1
M3 - Journal article
AN - SCOPUS:85067808056
VL - 65
SP - 241
EP - 248
JO - Annali dell'Universita di Ferrara
JF - Annali dell'Universita di Ferrara
SN - 0430-3202
IS - 2
ER -
ID: 232711356