Strassen's Laser Method Technique AND Tensors in matrix multiplication algorithms

Question

1. I understand the first algorithm presented by Strassen in 1968, for fast matrix multiplication. This was the first improvement to the naive approach of multiplying matrices. Thereafter, he went on to introduce the 'Laser Method' technique. What is this technique exactly? How do we really go about using this approach?

I have been referring to a lot of papers for this. But, no paper exactly describes the technique appropriately. Some of the papers are referred to are:

http://www.maths.ed.ac.uk/assets/files/pgrexternalfiles/theses/probability/stothers.pdf

2. I also don't well understand the use of Border rank in the matrix multiplication algorithms (both Strassen's and Winograd's via Arithmetic progressions) Can anyone help me with this as well?

http://www.cs.umd.edu/~gasarch/TOPICS/ramsey/matrixmult.pdf

Thanks!

Answer 1

Maybe try this paper? Fast Matrix Multiplication: Limitations of the Laser Method

It goes into enough detail for me to think I understand what's going on. I think the laser method is figuring out answers for N values with less rounding errors than what occurs using Strassen's method using some differential equation or numerical method. In recent years computers have advanced enough for the task to be automated which has resulted in higher order (of precision) solutions.

That pdf has a link to some code for their results - maybe that could help? If you get an answer or already have, then please post back.

You can also check the book "Introduct to algorithms" from the MIT press, chapter 4 - divide-and-conquer. The end notes to the chapter proved insightful for me at least.

Answer 2

The laser method (introduced in Strassen, Crelle 1987) and border rank and its uses (introduced in Bini, Capovani, Lotti, & Romani, Inform. Proc. Lett. 1979) are very nicely explained in Bläser's graduate survey.