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. We did wrap linbox, but your/my/Robert's implementation of strassen in Sage (which is what we use), seems to be a bit better whenever I do timings: sage: m1 = random_matrix(GF(10007), 800) sage: m2 = random_matrix(GF(10007), 800) sage: time c = m1*m2 CPU times: user 0.82 s, sys: 0.03 s, total: 0.85 s Wall time: 0.85 sage: time d = m1._multiply_linbox(m2) CPU times: user 1.14 s, sys: 0.02 s, total: 1.16 s Wall time: 1.17 sage: c == d True sage: time e = m1._multiply_classical(m2) CPU times: user 3.44 s, sys: 0.00 s, total: 3.44 s Wall time: 3.44 Hopefully when Clement gets here in January, I can show him this and he'll get so annoyed he'll show us how to "use linbox correctly", and we'll switch to using linbox for multiplication. It's very important to keep in mind that the above timing is really Sage using Linbox which means there is data conversion going on, along with issues involving us possibly not optimally building Linbox yet. Also, very often we have chosen using only functions from Linbox that demonstrably work very reliably on all Sage supported platforms. I think the main use of linbox from Sage now is for charpoly and det computation. Though both are unfortunately nonoptimal right now because of regressions in Linbox (we found bugs, they temporarily fixed them by making some things slower...), which I think might have been resolved very recently. William --~--~---------~--~----~------------~-------~--~----~ 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/ -~----------~----~----~----~------~----~------~--~---
