Hi Simon and Martin, I know Strassen-Winograd. Strassen uses 18 additions, Strassen-Winograd only 15, which is optimal for 7 multiplications ;-)
With the in-memory variant I mean: "Boyer, Dumans, Pernet and Zhou: Memory efficient scheduling of Strassen-Winograd's matrix multiplication algorithm. International Symposium on Symbolic and Algebraic Computation 2009." This needs only a constant number of auxiliary variables, i think. OK. If you work on finite fields, there is no stability issue. Loop Unrolling or Tilling doesn't change the asymptotic complexity. But we can use Knowledge about the computer architecture (L1 Cache, etc), to speed up the computations by a factor of 2. Please remember that the parameters for Strassens algorightm from his original paper are far away from optimal. I mean that the original method only was build for matrices of the size m*2^k. Strassen said something like: If you ant to calculate the product of two n x n matrices for an arbitrary n, choose m=f(n) and k=g(n) for some f and g (see his paper from 1969). These f and g are NOT a good choice. There are better ones from R. Probert and others. Best wishes, Ivo. Am 18. Jul 2011 um 12:46 schrieb Simon King <simon.k...@uni-jena.de>:
PS: On 18 Jul., 12:44, Simon King <simon.k...@uni-jena.de> wrote: > > Usually, when people talk about Strassen they mean Strassen-Winograd, is that > > what you mean? It just reduces the number of additions. > > My guess is that Ivo refers to Coppersmith-Winograd, which, according > to Wikipedia, *is* faster than Strassen-Winograd: n^2.376 versus > n^2.807. ... but only pays off for matrix sizes too big to be practical. I guess that's why it is not in Sage. -- 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
