Here is the graph of Magma times: http://sage.math.washington.edu/home/wbhart/flint-trunk/graphing/gf2.png
The crossover is not clear. The change from a smooth curve to a squiggly line is about 3600. So presumably that is it, but the graph also seems to change character at about 6200 or 7000 as well. One of these changes may be cache related. At 3600, the total data for all three matrices is almost 5mb and the cache on my machine is 1024kb. But if Magma is using classical multiplication, then this is pretty much irrelevant anyway, since you can keep the working data within the cache for quite a while during the algorithm. Bill. On 15 May, 22:41, Bill Hart <[EMAIL PROTECTED]> wrote: > Oh, actually I have no idea where Magma's crossover is. I'll wager it > is somewhere between 4000x4000 and 6000x6000, but let's not speculate. > I'll try and work it out with some timings. > > Bill. > > On 15 May, 22:23, Martin Albrecht <[EMAIL PROTECTED]> > wrote: > > > On Thursday 15 May 2008, Bill Hart wrote: > > > > Martin, > > > > Do you think Magma uses naive multiplication for its base case? This > > > can be ridicoulously fast, especially over GF2. I note for example > > > that Magma's base case is about 6 times faster than M4RI at 1000x1000. > > > Is it possible that the naive multiplication can just be optimised > > > with a far better constant and that the crossover with m4r is above > > > the crossover with Strassen-Winograd? > > > > I also note that the M4RI SSE2 code doesn't seem faster than the > > > generic C code on the Opteron, in fact it seems the other way around. > > > Very strange. > > > I observed the same behaviour but have no explanation besides stuff like > > this: > > >http://www.theinquirer.net/en/inquirer/news/2003/05/02/sse2-makes-opt... > > > How do you know what the Magma base case is, can you tell Magma somehow to > > print its crossover? I'll look into plugging in naive multiplication as the > > base case (after optimisation) to see if your idea is right, though I doubt > > that the crossover to M4RM is beyond the crossover to Strassen-Winograd. > > > Martin > > > -- > > name: Martin Albrecht > > _pgp:http://pgp.mit.edu:11371/pks/lookup?op=get&search=0x8EF0DC99 > > _www:http://www.informatik.uni-bremen.de/~malb > > _jab: [EMAIL PROTECTED] --~--~---------~--~----~------------~-------~--~----~ To post to this group, send email to sage-devel@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/sage-devel URLs: http://www.sagemath.org -~----------~----~----~----~------~----~------~--~---
