Last week, DeepMind announced their new AlphaEvolve software along with a number of new results improving optimization problems in a number of areas. One of those results is a new, smaller, tensor decomposition for multiplying two 4 × 4 matrices in 48 scalar multiplications, improving on the previous best decomposition which needed 49 multiplications (Strassen 1969). While the DeepMind paper was mostly careful about stating this, when writing the introduction, the authors mistakenly/confusingly wrote:

For 56 years, designing an algorithm with rank less than 49 over any field with characteristic 0 was an open problem. AlphaEvolve is the first method to find a rank-48 algorithm to multiply two 4 × 4 complex-valued matrices

This gives the impression that this new result is the way to multiply 4 × 4 matrices over a field with the fewest number of field multiplications. However, it's not even the case that Strassen's 1969 paper gave a faster way to multiply 4 × 4 matrices. In fact, Winograd's 1968 paper on computing inner products faster could be applied to 4 × 4 matrix multiplication to get a formula using only 48 multiplications. Winograd uses a trick 

which changes two multiplications of ab's into one multiplication of ab's and two multiplications involving only a's or only b's. The latter multiplications can be pre-computed and saved when calculating all the innerproducts in a matrix multiplication

    # i=1..4, 4*2 = 8 multiplications
    p[i] := -A[i, 1]*A[i, 2] - A[i, 3]*A[i, 4];
    # 4*2 = 8 multiplications
    q[i] := -B[1, i]*B[2, i] - B[3, i]*B[4, i];

    # i=1..4, j=1..4, 4*4*2 = 32 multiplications
    C[i,j] = p[i] + q[j] 
            + (A[i,1]+B[2,j])*(A[i,2]+B[1,j])
            + (A[i,3]+B[4,j])*(A[i,4]+B[3,j])

It is simple to verify that C[i,j] = A[i,..] . B[..,j] and that the above formula calculates all of the entries of C=A.B with 8+8+32=48 multiplications.

So, if Winograd achieved a formula of 48 multiplications in 1968, why is the DeepMind result still interesting? Well, the relative shortcoming of Winograd's method is that it only works if the entries of A and B commute, while tensor decomposition formulas for matrix multiplication work even over noncommutative rings. That seems very esoteric, but everyone's favorite noncommutative ring is the ring of n × n matrices. So if a formula applies to a matrix of matrices, that means it gives a recursive formula for matrix multiplication - an tensor decomposition formulas do just that.

The original 1969 Strassen result gave a tensor decomposition of 2 × 2 matrix multiplication using only 7 scalar multiplications (rather than the 8 required by the inner product method) and leads to a recursive matrix multiplication algorithm using O(N^log[2](7)) scalar multiplications. Since then, it has been proved that 7 is the smallest rank tensor decompostion for the 2 × 2 case and so researchers have been interested in the 3x3 and larger cases. Alexandre Sedoglavic at the University of Lille catalogs the best tensor decompositions at https://fmm.univ-lille.fr/ with links to a Maple file with an evaluation formula for each.

The previous best 4 × 4 tensor decomposition was based on using the 2 × 2 Strassen decomposition recursively (2 × 2 matrix of 2 × 2 matrices) which led to 7 2 × 2 matrix multiplications each requiring 7 scalar multiplications, for a total of 49. The new DeepMind result reduces that to 48 scalar multiplications, which leads to a recursive algorithm using O(N^log[4](48)) scalar multiplications: O(N^2.7925) vs. O(N^2.8074) for Strassen. This is a theoretical improvment over Strassen but in 2024 the best known multiplication algorithm has much lower complexity: O(N^2.3713) (see https://arxiv.org/abs/2404.16349). Now, there might be some chance that the DeepMind result could be used in practical implementations, but its reduction in the number of multiplications comes at the cost of many more additions. Before doing any optimizations I counted 1264 additions in the DeepMind tensor, compared to 318 in the unoptimized 4×4 Strassen tensor (which can be optimized to 12*7+4*12=132). Finally, the DeepMind tensor decomposition involves 1/2 and sqrt(-1), so it cannot be used for fields of characteristic 2, or fields without sqrt(-1). Of course, the restriction on characteristic 2 is not a big deal, since the DeepMind team found a 4 × 4 tensor decomposition of rank 47 over GF2 in 2023 (see https://github.com/google-deepmind/alphatensor).

Now if one is only interested in 4 × 4 matrices over a commutative ring, the Winograd result isn't even the best possible. In 1970, Waksman https://ieeexplore.ieee.org/document/1671519 demonstrated an improvement of Winograd's method that used only 46 multiplications as long as the ring allowed division by 2. Waksman's method has since been improved by Rosowski to remove the divisions see https://arxiv.org/abs/1904.07683. Here's that nice compact straight-line program that computes C = A · B in 46 multiplications.

And, here attached are five Maple worksheets that create the explicit formulas for the 4 × 4 matrix methods mentioned in this post, and verify their operation count, and that they are correct.

Strassen_444.mw  Winograd.mw  DM_444.mw Waksman.mw Rosowski.mw

If you are interested in some of the 2022 results, I posted some code to my GitHub account for creating formulas from tensor decompositions, and verifying them on symbolic matrix multiplications: https://github.com/johnpmay/MapleSnippets/tree/main/FastMatrixMultiplication

The clear followup question to all of this is:  does Maple use any of these fast multiplication schemes?  And the answer to that is mostly hidden in low level BLAS code, but generally the answer is: No, the straightforward inner-product scheme for multiplying matrices optimized memory access thus usually ends up being the fastest choice in most cases.

As a university-level math student, I am constantly working through practice problems. An issue I constantly face is that when I get a problem wrong, it can be challenging to find out which line I did wrong. Even if I use Maple Calculator or Maple Learn to get the full steps for a solution, it can be tedious to compare my answer to the steps to see where I went wrong.

This is why Check My Work is one of the most popular features in Maple Learn. Check My Work will check all the lines in your solution and give you feedback showing you exactly where you went wrong. I honestly didn’t know that something like this existed until I started here at Maplesoft, and it is now easy to see why this has been one of our most successful features in Maple Learn.

Students have been loving it, but the only real complaint is that it’s only available in Maple Learn. So, if you were working on paper, you'd either have to retype your work into Maple Learn or take a picture of your steps using Maple Calculator and then access it in Maple Learn. Something I immediately thought was, if I’m already on my phone to take a picture, I’d much rather be able to stay on my phone.

And now you can! Check My Work is now fully available within Maple Calculator!

To use Check My Work, all you need to do is take a picture of your solution to a math problem.

Check My Work will recognize poor handwriting, so there is no need to worry about getting it perfect. After taking the picture, select the Check My Work dropdown in the results screen to see if your solution is correct or where you made a mistake.

Check My Work will go through your solution line-by-line giving you valuable feedback along the way! Additionally, if you make a mistake, Maple Calculator will point out the line with the error and then proceed with checking the remainder of the solution given this context.  

For students, Check My Work is the perfect tool to help you understand and master concepts from class. As a student myself, I’ll for sure be using this feature in my future courses to double-check my work.

What makes Check My Work great for learning a technique is that it doesn’t tell you what mistake you made, but rather where the mistake has been made. This is helpful since as a student you don’t have to worry about the time-consuming task of finding the step with an error, but rather you can focus on the learning aspect of actually figuring out what you did wrong.

Once you have made corrections to your work on paper, take a new picture and repeat the process. You can also make changes to your solution in-app by clicking the “Check my work in editor” button in the bottom right, which runs Check My Work in the editor where you can modify your solution.

No other math tool has a Check My Work feature, and we are very proud to bring this very useful tool to students. By bringing it fully into Maple Calculator, we continue working towards our goal of helping students learn and understand math.

View the GIF below for a brief demonstration of how to use Check My Work!

We hope you enjoy Check My Work in Maple Calculator and let us know what you think!