English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

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

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

Item is

Files

show Files
hide Files
:
arXiv:1708.08083.pdf (Preprint), 110KB
Name:
arXiv:1708.08083.pdf
Description:
File downloaded from arXiv at 2018-01-31 10:19
OA-Status:
Visibility:
Public
MIME-Type / Checksum:
application/pdf / [MD5]
Technical Metadata:
Copyright Date:
-
Copyright Info:
-

Locators

show

Creators

show
hide
 Creators:
Ikenmeyer, Christian1, Author           
Lysikov, Vladimir2, Author
Affiliations:
1Algorithms and Complexity, MPI for Informatics, Max Planck Society, ou_24019              
2External Organizations, ou_persistent22              

Content

show
hide
Free keywords: Computer Science, Data Structures and Algorithms, cs.DS,Computer Science, Symbolic Computation, cs.SC
 Abstract: 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.

Details

show
hide
Language(s): eng - English
 Dates: 2017-08-272017
 Publication Status: Published online
 Pages: 5 pages
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: arXiv: 1708.08083
URI: http://arxiv.org/abs/1708.08083
BibTex Citekey: Ikenmeyer_Lysikov2017
 Degree: -

Event

show

Legal Case

show

Project information

show

Source

show