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
