Hi Simon, wow, I am impressed.
If the cutoff-parameter is determined by the benchmark: Yes, submit it! In the other case I see the problem of how to define the cutoff in a good way. In this case the method could be significantly slower. I look forward to review your patch. Best wishes from Halle to Jena, Ivo Am 18.07.2011 um 18:22 schrieb Simon King: > Hi Ivo, > > On 18 Jul., 16:44, Ivo Hedtke <hed...@me.com> wrote: >> what would be a nice piece of work. Good luck and have fun ;-) > > Thank you! I had fun... > >> Please test the following if your implementation is ready: Try to use your >> Strassen implementation only with 1 step of recursion (in the next step only >> the naive algorithm). And a second version with only 3 steps of recursion. >> This will bound the memory requirements and give a speed up. This is a known >> heuristic (to stop the recursion early). > > Concerning memory: Since the memory is used only temporarily, I don't > see how I could determine the exact memory requirements without > inserting get_memory_usage() statements into the code. Below, I > determine the memory consumption by staring at "top" while running the > computation. > > Concerning iterations: The algorithm does not count the number of > iterations, but uses a next iteration step only if *all* current > matrix dimensions exceed a given cutoff parameter. > > 1st test: Multiplication of a 64x83 matrix by a 83x101 matrix over the > integers modulo 2^65 (that is a doc test example). > cutoff=20 seems to be a rather good choice (which amounts to two > iterations for these matrix dimensions). > Default multiplication in Sage: 365 ms. > New Strassen implementation, cutoff=20: 291 ms. > Old Strassen implementation, cutoff=20: 288 ms. > > 2nd test: Multiplication of two 1000x1000 matrices over GF(125). > Default multiplication in Sage: 102.13 seconds, using 3.9% of my > computer's memory. > New Strassen implementation, cutoff=20: 61.16 seconds using 4.1% of my > computer's memory. > Old Strassen implementation, cutoff=20: 61.78 seconds using 4.7% of my > computer's memory. > > 3rd test: Multiplication of two 2000x2000 matrices over GF(125). > Default multiplication takes ages. > New Strassen implementation, cutoff=20: 427 seconds using 6.9% of my > computer's memory. > Old Strassen implementation, cutoff=20: 431 seconds using 9.3% of my > computer's memory. > > > I don't know if it is worth it. Shall I open a ticket and post my > patch? > > Best regards, > Simon > > -- > To post to this group, send an email to sage-devel@googlegroups.com > To unsubscribe from this group, send an email to > sage-devel+unsubscr...@googlegroups.com > For more options, visit this group at > http://groups.google.com/group/sage-devel > URL: http://www.sagemath.org -- To post to this group, send an email to sage-devel@googlegroups.com To unsubscribe from this group, send an email to sage-devel+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URL: http://www.sagemath.org
