On Monday 18 July 2011, Ivo Hedtke wrote: > Hi, Hi Ivo,
> I am new to sage-devel. Sorry if I asked questions that you perhaps > discussed in the the past. > > Why do you wan't to use Strassen for Matrix Multiplication? This algorithms > is not as stable as naive algorithm (if one uses floating point numbers, > if you use it for symbol computations that is no problem). We are discussing using it over finite fields and hence there is no stability issue. > It is also not very fast for small matrices. That's why one usually implements a cutoff: below a certain dimension naive or or some other multiplication is used: both when the input matrix is small and when the recursion reaches the small dimension. > And if you don't use the in-memory version > of the algorithm it has extremly memory requirements. The memory overhead is 2/3 n^2 if you set it up right. > Why not Winograd's method. Usually, when people talk about Strassen they mean Strassen-Winograd, is that what you mean? It just reduces the number of additions. > Or something like Tiling or Loop-Unrolling? Of course, one implements the base case as efficiently as possible. In LinBox's case it's outsourced to ATLAS, in other cases there are dedicated implementations. While these implementation tricks are crucial for good performance, they won't beat Strassen-Winograd since they are asymptotically slower: n^3 vs. n^2.807. Cheers, Martin -- name: Martin Albrecht _pgp: http://pgp.mit.edu:11371/pks/lookup?op=get&search=0x8EF0DC99 _otr: 47F43D1A 5D68C36F 468BAEBA 640E8856 D7951CCF _www: http://martinralbrecht.wordpress.com/ _jab: martinralbre...@jabber.ccc.de -- 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
