On the Geometry of Border Rank Algorithms for n × 2 by 2 × 2 Matrix Multiplication

ABSTRACT

We make an in-depth study of the known border rank (i.e., approximate) algorithms for the matrix multiplication tensor encoding the multiplication of an n × 2 matrix by a 2 × 2 matrix.

KEYWORDS:

• approximate algorithms
• border rank
• matrix multiplication
• Segre variety

2000 AMS SUBJECT CLASSIFICATION:

• 68Q17
• 68Q25
• 15A99

Acknowledgments

We thank F. Gesmundo for calculating the Lie algebra of the stabilizer of T_BCLR and the limiting 5- and 10-planes in the BCLR algorithms. This article is the result of a project associated to a course at UC Berkeley fall 2014 given by the first author and attended by the second as part of a semester long program Algorithms and Complexity in Algebraic Geometry at the Simons Institute for the Theory of Computing. The authors thank the Institute for making this article possible. We also thank B. Liu for corrections and clarifying the role of base points in second order algorithms.

Funding

Landsberg was partially supported by NSF grant DMS-1405348.