On Oct 23, 2007, at 9:47 PM, William Stein wrote:
> > On 10/23/07, David Harvey <[EMAIL PROTECTED]> wrote: >>> For huge Z, I wonder if it's still trying to do multi-modular? That >>> would probably be bad. I'm also not sure how much of the dispatching >>> is done in Linbox vs. Sage. >> >> Multimodular would be terrible. You don't get any of the benefits of >> strassen, since the tiny multiplies are way below the strassen >> cutoff. So basically it would end up looking like doing *integer* >> multiplication with a multi-modular algorithm, which isn't such a >> good idea :-) > > It's not doing multi-modular unless that matrix is at least 21 x 21 > *and* the coefficients are relatively small compared to the size > of the matrix. I at least did some tiny amount of tuning for > this function (at the airport in Calgary, now that I think about it). > Vastly more could be done. > > I just looked at the code in matrix_modn_dense.pyx for matrix > multiply, > and we don't use linbox there either yet. We just use strassen > for big matrices and classical multiplication for small matrices. Actually, soon I will be doing matrix multiply over Z/p^N for some large N, so the matrix_modn_dense thing is relevant. Another question: for large moduli like this, does it delay the reduction until after the adds/subs, either in classical or strassen? This would mean only O(n^2) reductions instead of O(n^3). david --~--~---------~--~----~------------~-------~--~----~ 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://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/ -~----------~----~----~----~------~----~------~--~---
