Strassen's 2x2 Matrix Multiplication Algorithm: A Conceptual Perspective

Ikenmeyer, Christian; Lysikov, Vladimir

アイテム詳細

登録内容を編集ファイル形式で保存

一時保存へ追加

タグ情報を表示リリース履歴を表示詳細要約

公開

成果報告書

Strassen's 2x2 Matrix Multiplication Algorithm: A Conceptual Perspective

MPS-Authors

/persons/resource/persons202366

Ikenmeyer, Christian
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource

There are no locators available

Fulltext (restricted access)

There are currently no full texts shared for your IP range.

フルテキスト (公開)

arXiv:1708.08083.pdf
(プレプリント), 110KB

付随資料 (公開)

There is no public supplementary material available

引用

Ikenmeyer, C., & Lysikov, V. (2017). Strassen's 2x2 Matrix Multiplication Algorithm: A Conceptual Perspective. Retrieved from http://arxiv.org/abs/1708.08083.

引用: https://hdl.handle.net/21.11116/0000-0000-3F1F-9

要旨

Despite its importance, all proofs of the correctness of Strassen's famous 1969 algorithm to multiply two 2x2 matrices with only seven multiplications involve some more or less tedious calculations such as explicitly multiplying specific 2x2 matrices, expanding expressions to cancel terms with opposing signs, or expanding tensors over the standard basis. This is why the proof is nontrivial to memorize and why 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, easy to memorize, and elegant 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 combines the classical theory of M-pairs, which was initiated by B\"uchi and Clausen in 1985, with recent work on the geometry of Strassen's algorithm by Chiantini, Ikenmeyer, Landsberg, and Ottaviani from 2016.