On Oct 23, 2007, at 6:51 PM, David Harvey wrote: > 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).
I don't think there is any special code for matrix_mod_n for n larger than a word (or perhaps even half a word). For the classical, it delays doing reductions when computing the dot product until the last moment. - Robert --~--~---------~--~----~------------~-------~--~----~ 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/ -~----------~----~----~----~------~----~------~--~---
