On 16 May, 23:05, Martin Albrecht <[EMAIL PROTECTED]>
wrote:
> On Friday 16 May 2008, Bill Hart wrote:
> > The other possibility is that Magma combines the two algorithms so
> > that there is even greater usage of the Gray code tables. This would
> > be an ugly hack, but could work.
>
> Are you suggesting Magma uses M4RM too? I'd doubt that, since they don't state
> that anyway. Probably I'm just misunderstanding you.
Well, the thing is, Allan Steel may not have ever read a paper on the
Method of the 4 Russians. He may consider it to just be a highly
optimised classical algorithm and may have just rediscovered it, or
something similar. It is very similar to a "window" method that is
used for polynomials over GF2, so I could easily imagine this
happening.
Then again, Magma does seem a lot slower for very small matrix
multiplications, which makes me wonder if they aren't just using a
highly efficiently implemented classical routine. I suppose it is
vaguely possible that you could order operations in such a way as to
effectively mix the classical and Strassen-Winograd algorithms for the
purpose of getting better cache efficiency. I don't know if it is
likely, but if someone went to the trouble of optimising a classical
routine down to one cycle per 64 by 64 bit pair, they are sure serious
about squeezing absolutely everything out.
Bill.
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---
