Most Computationally Speedy Algorithm To Multiply Two Matrices (not necessarily square matrices)

Question

I have looked at the Strassen algorithm, but the online resources only show it working for square matrices (with dimensions $2^n {\times} 2^n$ where $n$ is some natural number)? But what if it is two non-square matrices with different dimensional lengths (i.e an $A{\times} B$ matrix by a $B{\times} C$ matrix). What is the fastest algorithm then?

Answer 1

Hopcroft and Kerr and Hopcroft and Musinski found algorithms for $2\times3\times3$, $3\times2\times3$ and $3\times3\times2$ with $15$ rather than $18$ elementary products back in 1969 - 1972.

Example:

P1 := a11*(b11-b31-b12);
P2 := (a11+a21)*(b11-b21-b13);
P3 := a12*(-b21+b22-b32);
P4 := a22*(-b12+b22-b23);
P5 := (a13+a23)*(-b31-b23+b33);
P6 := a23*(-b32-b13+b33);
P7 := (a11+a21+a12+a22)*b21;
P8 := (a11+a21+a22)*(-b21+b12);
P9 := (a21+a22)*(-b12);
P10 := (a12+a22+a13+a23)*b23;
P11 := (a12+a13+a23)*(b32-b23);
P12 := (a12+a13)*(-b32);
P13 := (a11-a23)*(-b31+b13);
P14 := (a21+a23)*(-b13);
P15 := (a11+a13)*b31;

c11 := P1+P7+P8+P9+P15;
c12 := P3+P7+P8+P9-P12;
c13 := P5-P6-P11-P12+P13+P15;
c21 := -P1+P2-P8-P9+P13-P14;
c22 := P4-P9+P10+P11+P12;
c23 := P6+P10+P11+P12-P14;

Probably not the fastest possible solution but the current record in terms of elementary products.

For $2\times2\times3$ the record is $11$ rather than $12$ multiplications. But this is basically a combination of Strassen $2\times2\times2$ and classic $2\times2\times1$ (resulting in $7+4=11$ products). See this paper of Bläser.