Maplesoft Blogger Profile: John May

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.

With the 2024 Maple Conference coming up this week, I imagine one of two of you have noticed something missing. We chose not to have a Conference Art Gallery this year, because we have been working to launch new section of MaplePrimes:  The MaplePrimes Art Gallery. This new section of MaplePrimes is designed for showing off your Maple related images, in a gallery format that puts the images up front, like Instagram but for Math.

To get the ball rolling on the gallery, I have populated it with many of the works from past years' Maple Art Galleries, so you can now browse them all in one place, and maybe give "Thumbs Ups" to art pieces that you felt should have won the coveted "People's Choice Award".

Once you are inspired by past entries, we welcome you to submit your new artwork!  Just like the conference galleries, we are looking for all sorts of mathematical art ranging from computer graphics and animations, to photos of needlework, geometrical sculptures, or almost anything!  Art Gallery posts are very similar to regular MaplePrimes posts except that you are asked to supply an Image File and a Caption that will displayed on the main Gallery Page, the post itself can include a longer description, Maple commands, additional images, and whatever else you like.  See for example this Art Gallery post describing Paul DeMarco's sculpture from the 2021 Maple Conference Gallery - it includes an embedded worksheet as well as additional images.

I can't wait to see what new works of art our MaplePrimes community creates!

we have recieved lots of great sumissions, but we want your great submission and now you have more time.

The deadline for submissions to the Art Gallery and Showcase for the 2023 Maple Conference is rapidly approaching. We really want to see your art! It doesn't have to be incredibly impressive or sophisticated, we just want to see what our community can create! If you've been working on something or have a great idea, you still have a few days to get it together to submit.

Submission can be made by email to gallery@maplesoft.com but be sure to visit the visit our Call for Creative Works for details on the format of the submission.

If you've seen Paulina's announcement then you know that we are once again holding a virtual Maple Conference this year.  As well, we are once again going to have a virtual gallery featuring artwork and creative projects submitted by the Maple community!

Last year we had a number of great submissions to our Maple Art Gallery and our Maple Learn Creative Showcase.  These were our excellent prize winners.

From left to right we have A visualization of all the primitive roots of 10037 created by Simon Plouffe, winner of the Judge’s Choice, Mother’s Day Rose created with Maple plots by Greg Wheaton, winner of the People’s Choice, and Mona Lisa in Maple Learn created by Paul DeMarco (with help from Leonardo DaVinci), the winner of the People’s Choice for the Maple Learn Showcase.

This year we are expanding the Gallery into two collections to encourage more people to submit.  They are

• The Art Gallery - A small gallery to highlight high effort, mathematically interesting works (with stricter criteria)

• The Creative Works Showcase - A larger showcase for nearly any interesting visual works created with Maplesoft products like Maple Learn and Maple

Feel free to submit nearly anything cool for the Creative Works Showcase, if we find it particularly impressive we might even ask you to let us consider it for the gallery.  Also, do not be intimidated by the title "Art Gallery" we're looking for anything that has taken some artistic effort and tells a mathematical story.

For more information on critera and how to submit, please visit our Call for Creative Works.  The important deadline to know is the September 14th deadline for submission of works with virtual gallery reception and awards ceremony durring the conference October 26-27.

I look forward to seeing all the submissions for the Maple community again this year!

This is a friendly reminder that the deadline for submissions for this year's Maple Conference Creative Works Exhibit is fast approaching!

If you are looking for inspiration, you can take a look at the writeup of the works that were featured last year in this write up in the most recent issue of Maple Transations.

Also, don't forget that you can also submit art made in Maple Learn for a special exhibit alongside the main gallery.

Hi Maple Users

As I hope you have already heard, Maplesoft is having our Maple Conference again this fall. And that means that

Last year we had many great submissions and you can still read about them in detail on the 2021 conference site. Some of the featured works were excellent Maple visualizations, including a special prize for a student contribution by Avek Dongol (center).

But we also featured a number of impressive physical works, including the people's choice winning wood carving by Paul DeMarco (left), and the judges' choice winning cross stitch by Bridjet Lee and Curtis Bright (right).

This year, we are again looking to fill our virtual exhibition with all types of mathematical art, ranging from computer graphics and animations, to needlework, geometrical sculptures, or almost anything you can come up with. Surprise us!

The full announcement can be found at the Maple Conference Art Gallery page. We would like to have all submissions by September 22nd so that we can review and finalize the gallery before the conference begins November 2nd.

I can't wait to see what everyone sends in this year!

As most Maple Primes readers have hopefully seen, Maplesoft is having our Maple Conference again this fall. This year we decided to add a space to the conference to showcase creative and artistic work that would be interesting to our Maple Community. The conference organizers asked me if I would coordinate and curate this exhibition of creative uses of Math and Maple, and I agreed. So now, I am asking the Maple community to send us your most creative work related to or using Maple.

The obvious thing to submit would be a beautiful digital plot or animation with an interesting mathematical story and of course, we are really interested to see those. But, we would are especially excited to see some art created with physcial media. I would love to see your knitting or needle point project that is inspired by a mathematical theme or was created with the help of Maple.

The full announcement can be found at the Maple Conference Art Gallery page. We would like to have all submissions by October 12th so that can review and finalize the gallery before the conference begins November 1st.

Oh yeah, there will also be prizes.

I can't wait to see what everyone sends in!

This is Maple:

These are some primes:

22424170499, 106507053661, 193139816479, 210936428939, 329844591829, 386408307611,
395718860549, 396412723027, 412286285849, 427552056871, 454744396991, 694607189303,
730616292977, 736602622363, 750072072203, 773012980121, 800187484471, 842622684461

This is a Maple prime:

In plain text (so you can check it in Maple!) that number is:

111111111111111111111111111111111111111111111111111111111111111111111111111111
111111111111111111111111111111116000808880608061111111111111111111111111111111
111111111111111111111111111866880886008008088868888011111111111111111111111111
111111111111111111111116838888888801111111188006080011111111111111111111111111
111111111111111111110808080811111111111111111111111118860111111111111111111111
111111111111111110086688511111111111111111111111116688888108881111111111111111
111111111111111868338111111111111111111111111111880806086100808811111111111111
111111111111183880811111111111111111100111111888580808086111008881111111111111
111111111111888081111111111111111111885811188805860686088111118338011111111111
111111111188008111111111111111111111888888538888800806506111111158500111111111
111111111883061111111111111111111116580088863600880868583111111118588811111111
111111118688111111111001111111111116880850888608086855358611111111100381111111
111111160831111111110880111111111118080883885568063880505511111111118088111111
111111588811111111110668811111111180806800386888336868380511108011111006811111
111111111088600008888688861111111108888088058008068608083888386111111108301111
111116088088368860808880860311111885308508868888580808088088681111111118008111
111111388068066883685808808331111808088883060606800883665806811111111116800111
111581108058668300008500368880158086883888883888033038660608111111111111088811
111838110833680088080888568608808808555608388853680880658501111111111111108011
118008111186885080806603868808888008000008838085003008868011111111111111186801
110881111110686850800888888886883863508088688508088886800111111111111111118881
183081111111665080050688886656806600886800600858086008831111111111111111118881
186581111111868888655008680368006880363850808888880088811111111111111111110831
168881111118880838688806888806880885088808085888808086111111111111111111118831
188011111008888800380808588808068083868005888800368806111111111111111111118081
185311111111380883883650808658388860008086088088000868866808811111111111118881
168511111111111180088888686580088855665668308888880588888508880800888111118001
188081111111111111508888083688033588663803303686860808866088856886811111115061
180801111111111111006880868608688080668888380580080880880668850088611111110801
188301111111111110000608808088360888888308685380808868388008006088111111116851
118001111111111188080580686868000800008680805008830088080808868008011111105001
116800111111118888803380800830868365880080868666808680088685660038801111180881
111808111111100888880808808660883885083083688883808008888888386880005011168511
111688811111111188858888088808008608880856000805800838080080886088388801188811
111138031111111111111110006500656686688085088088088850860088888530008888811111
111106001111111111111111110606880688086888880306088008088806568000808508611111
111118000111111111111111111133888000508586680858883868000008801111111111111111
111111860311111111111111111108088888588688088036081111860803011111111863311111
111111188881111111111111111100881111160386085000611111111888811111108833111111
111111118888811111111111111608811111111188680866311111111111811111888861111111
111111111688031111111111118808111111111111188860111111111111111118868811111111
111111111118850811111111115861111111111111111888111111111111111080861111111111
111111111111880881111111108051111111111111111136111111111111188608811111111111
111111111111116830581111008011111111111111111118111111111116880601111111111111
111111111111111183508811088111111111111111111111111111111088880111111111111111
111111111111111111600010301111111111111111111111111111688685811111111111111111
111111111111111111111110811801111111111111111111158808806881111111111111111111
111111111111111111111181110888886886338888850880683580011111111111111111111111
111111111111111111111111111008000856888888600886680111111111111111111111111111
111111111111111111111111111111111111111111111111111111111111111111111111111111

This is a 3900 digit prime number. It took me about 400 seconds of computation to find using Maple.  Inspired by the Corpus Christi College Prime, I wanted to make an application in Maple to make my own pictures from primes.

It turns out be be really easy to do because prime numbers are realy quite common.  If you have a piece of ascii art where all the characters are numerals, you could just call on it and get a prime number that is still ascii art with a couple digits in the corner messed up (for a number this size, I expect fewer than 10 of the least significant digits would be altered).  You may notice, however, that my Maple Prime has beautiful corners!  This is possible because I found the prime in a slightly different way.

To get the ascii art in Maple, I started out by using to import ( )  and process the original image.  First then and to get a nice 78 pixel wide image.  Then to make it a pure 1-bit black or white image.

Then, from the image, I create a new Array of the decimal digits of the ascii art and my prime number.  For each of the black pixels I randomly use one of the digits or and for the white pixels (the background) I use 's.  Now I convert the Array to a large integer and test if it is prime using (it probably isn't) so, I just randomly change one of the black pixels to a different digit (there are 4 other choices) and call again. For the Maple Prime I had to do this about 1000 times before I landed on a prime number. That was surprisingly fast to me! It is a great object lesson in how dense the prime numbers really are.

So that you can join the fun without having to replicate my work, here is a small interactive Maple document that you can use to find prime numbers that draw ascii art of your source images. It has a tool that lets you preview both the pixelated image and the initial ascii art before you launch the search for the prime version.

Prime_from_Picture.mw

Another feature added to Maple 15 partially in response to the MaplePrimes forums is the new/improved ?HTTP package.  It provides one-step commands for fetching data from the web: much simpler than using the ?Sockets package directly. In most cases, the command ?HTTP,Get is what you would use:

 (s, page, h) := HTTP:-Get("http://en.wikipedia.org/wiki/List_of_Crayola_crayon_colors"):

The above fetches the HTML source of a page from Wikipedia and stores it as a string 'page'. The other two outputs are 's', and integer HTTP status code and 'h' a table of the headers returned in the HTTP response from the server.  Compare this to the amount of code needed to fetch data in my Baby Names application for Maple 12, for example.

In part due to a large number of requests on MaplePrimes, the command ?plottools,getdata was added to Maple 15. This new command gives programmers a better way to access the internals of plots and do things with the data they contain.

I was trying to come up with something really fun to do with this command, and another recent obsession came to mind: the game Minecraft.  Minecraft is nice, since like Maple it is written in Java and runs on lots of platforms!  For the uninitiated, Minecraft is a a sort of mostly unstructured "sandbox" game. The player starts in alone in a procedurally generated landscape consisting of blocks. They player can collect blocks with their hands or with tools and they use them to build new things. The wide array of things that people create in Minecraft is staggering.

So, I thought I would write some commands to export 3D plots in Maple to block structures in Minecraft.

Now that Maple 15 is out, I thought I should share this little application I made: GoalTracker.mw. It is an application partially inspired by the BMI tracker in Nintendo's WiiFit application; you could easily use it to track a weight loss goal. But it could also be used to track other quantifiable goals. I am posting it here mostly because it takes advantage of two new features in Maple 15.

Back when I was working at the University of Waterloo, I found several copies of a VHS tape sitting on a dusty bookshelf full of old Maple boxes and manuals. The tape's cover had a line drawing of Issac Newton on it and the title "Maple V: The Future of Mathematics".

There was...

The Canadian Lotto649 draws are randomized the old fashioned way, the draws are held using a Ryo-Catteau Tulipe ball machine made by a well respected French Company. The draws are video recorded in a secure studio, and broadcast live.  There is no reason to suspect that these draws might not be random, but let us look at some ways we might detect it if it were not random.

You could look at the Lottery draws as a generator for a binary sequence as I did in my previous post, but as Robert Israel pointed out in the comments, that encoding can hide some non-random behavior (e.g. if the number 25 appeared in every draw, that encoding would not appear less random).

This is not really the next part in my randomness series, but more of an aside.  I used Maple's embedded components to use the Lotto649 drawing data from my last post to create a historical lottery simulator.  Basically, you fill in your prefered numbers, and it simulates you playing the lottery in every draw since 1982.

In this series of blog posts, I have picked on Baseball win-loss records already.  Looking for other sources of things that might or might not be random, I decided to look at lottery draws.  Since I live in Canada, the obvious lottery to look at is the national Lotto 6/49.

A lotto 6/49 draw consists of drawing 6 numbered balls from...