Fast matrix multiplication can be described as searching for low-rank decompositions of the matrix--multiplication tensor. We design a neural architecture, StrassenNet, which reproduces the Strassen algorithm for 2×2 multiplication. Across many independent runs the network always converges to a rank-7 tensor, thus numerically recovering Strassen's optimal algorithm. We then train the same architecture on 3×3 multiplication with rank r∈{19,…,23}. Our experiments reveal a clear numerical threshold: models with r=23 attain significantly lower validation error than those with r≤22, suggesting that r=23 could actually be the smallest effective rank of the matrix multiplication tensor 3×3. We also sketch an extension of the method to border-rank decompositions via an ε--parametrisation and report preliminary results consistent with the known bounds for the border rank of the 3×3 matrix--multiplication tensor.
Figures & tables
Figure 1. Tensor neural network which computes the row by product matrix multiplication with the classical algorithm.
Figure 2. Tensor neural network which computes the row by product matrix multiplication with the Strassen algorithm.
Figure 3. Final sub-network which computes the Strassen algorithm.
Hyperparameter
Value
Matrix size
n=3 (i.e., 3×3 matrices)
Rank
r
Training samples per epoch
10,000
Validation samples
10,000
Batch size
32
Epochs
60
Table 1. Summary of training hyperparameters.
Figure 4. Plot of the training (a) and validation (b) losses of a batch of experiments for matrices with entries clamped in [−1,1] and values of rank r between 19 and 23 . In blue, orange, red, green and yellow the mean and standard deviation of the losses for r=23,22,21,20,19 , respectively.
Figure 5. Histogram showing the mean μ and standard deviation σ of validation losses for matrices with entries limited to [−1,1] and rank values r between 19 and 23 . The value μ for r=23 , in blue, is 0,0025802 , while σ is 0,0050602 ; for r=22 , in orange, μ=0,012773 and σ=0,007641 ; for r=21 , in red, μ=0,029102 and σ=0,0056912 ; for r=20 , in green, μ=0,034695 and σ=0,0054031 ; for r=19 , in yellow, μ=0,047196 and σ=0,0085363 .