On 10/23/07, Robert Bradshaw <[EMAIL PROTECTED]> wrote:
> Is there a way to get the size of an integer (really fast, like a
> macro getting the number of words)? One could perhaps override
> _strassen_default_cutoff (though I don't know how much overhead this
> would be for matrices with smallish entries).
>
> One can always enforce it by doing M._multiply_strassen(N)
>
> 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.
>
Here is the source code for choosing the matrix multiplication algorithm
over ZZ, from the matrix_integer_dense.pyx file:
cdef sage.structure.element.Matrix _matrix_times_matrix_c_impl(self,
sage.structure.element.Matrix right):
n = max(self._nrows, self._ncols, right._nrows, right._ncols)
if n <= 20:
return self._multiply_classical(right)
a = self.height(); b = right.height()
if float(max(a,b)) / float(n) >= 0.70:
return self._multiply_classical(right)
else:
return self._multiply_multi_modular(right)
---------
We do have A._multiply_linbox(B), but we never
use it by default, since when we first wrapped it sadly turned out
to be slower than using our own multi-modular implementation.
This is the sort of thing that may change someday, I hope...
>By my reckoning, it should only have to do 7*7*7 multiplies, which
>should take < 50s. It looks like it's really doing 8*8*8 multiplies.
Yep, for your small matrices, Sage is just doing classical
matrix multiplication (it's a triply nested for loop later
in that file). As Robert points out, just do M1._multiply_strassen(M2, 1)
to use our implementation of Strassen with a cutoff of 1.
This is indeed faster, as expected:
sage: time b = M1 * M2
CPU times: user 33.10 s, sys: 0.05 s, total: 33.15 s
Wall time: 33.19
sage: time a = M1._multiply_strassen(M2, 1)
CPU times: user 23.86 s, sys: 1.38 s, total: 25.24 s
Wall time: 25.66
sage: time c = M1._multiply_linbox(M2)
CPU times: user 33.35 s, sys: 0.69 s, total: 34.04 s
Wall time: 35.40
---
It could make a lot of sense to make _matrix_times_matrix
use strassen when the heights of the input matrices are
large, instead of using classical O(n^3) multiplication.
Willliam
--~--~---------~--~----~------------~-------~--~----~
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/
-~----------~----~----~----~------~----~------~--~---
