[racket] Everything type-checks; on to benchmarking and optimization

From: Stephen Bloch (bloch at adelphi.edu)
Date: Mon Feb 17 10:42:27 EST 2014

On Feb 17, 2014, at 8:27 AM, Matthias Felleisen <matthias at ccs.neu.edu> wrote:

> That is odd. Do share the code so others can inspect it. 

Will do.

> (The trick with this assignment is to make the two matrixes large enough so that they fit, barely fit, don't fit in certain levels of the memory hierarchy. This is perhaps 10-year old thinking but I am sure it hasn't gotten much better.) 

Yes, I suspect it has something to do with memory hierarchies.

One of the algorithms in question is Strassen’s, which is most straightforwardly applied to power-of-2 matrix sizes, so I’ve been running on sizes 4, 8, 16, 32, 64, 128, 256, 512, 1024, and 2048.  Somewhere around 128 Strassen’s algorithm beat out the naive O(n^3)  divide-and-conquer algorithm, and I extrapolate that around 4096 it will beat out the straightforward O(n^3) nested-for-loops matrix-multiplication algorithm… but even size 2048 has been taking hours or days to run.

Stephen Bloch
sbloch at adelphi.edu

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 496 bytes
Desc: Message signed with OpenPGP using GPGMail
URL: <http://lists.racket-lang.org/users/archive/attachments/20140217/d9f8fb69/attachment.sig>

Posted on the users mailing list.