Hi!
When working on improving matrix multiplication, I found that over
finite fields, there is a gigantic overhead:
sage: def test(m):
....: for i in xrange(10^5):
....: m*=m
....:
sage: m = matrix(GF(5),[[0,1],[-1,0]])
sage: %prun test(m)
Ordered by: internal time
ncalls tottime percall cumtime percall
filename:lineno(function)
300005 2.763 0.000 3.519 0.000 function_mangling.py:
205(fix_to_pos)
1 1.989 1.989 13.070 13.070 <ipython console>:
1(test)
100002 0.904 0.000 3.651 0.000 category.py:
667(is_subcategory)
100000 0.729 0.000 0.977 0.000 {method '__copy__' of
'sage.matrix.matrix_modn_dense.Matrix_modn_dense' objects}
100000 0.576 0.000 7.170 0.000 matrix_space.py:
109(MatrixSpace)
300005 0.465 0.000 3.984 0.000 cachefunc.py:
188(get_key)
....
The problems with function_mangling (fix_to_pos), category
(is_subcategory) and cachefunc (get_key) are fixed in #8611 (merged in
sage-4.6.2.alpha2).
The problem with matrix_space (MatrixSpace) is solved in #10763 (needs
review, hint-hint)
There remains the problem with the __copy__ method of matrices. It
turns out that it is used when creating a new zero matrix of the right
dimension that will eventually contain the product.
I have a question: In MatrixSpace.__call__, one can see
if entries is None or entries == 0:
if self.__is_sparse: # faster to create a new one than
copy.
return self.__matrix_class(self, {}, coerce=coerce,
copy=copy)
else:
return self.zero_matrix().__copy__()
By some tests, I found that copying (i.e., reading and writing data) a
dense zero matrix over a finite field really is a little faster than
initializing a zero matrix (i.e., just writing data):
sage: MS = MatrixSpace(GF(2),500,500)
sage: C = MS._MatrixSpace_generic__matrix_class
sage: M0 = C(MS, 0, False, False)
sage: timeit("M0.__copy__()")
625 loops, best of 3: 454 µs per loop
sage: timeit("C(MS, 0, False, False)")
625 loops, best of 3: 480 µs per loop
Over the integers, creating a dense zero matrix seems faster than
copying:
sage: MS = MatrixSpace(ZZ,500,500)
sage: C = MS._MatrixSpace_generic__matrix_class
sage: M0 = C(MS,0,False,False)
sage: timeit("M0.__copy__()")
25 loops, best of 3: 17.9 ms per loop
sage: timeit("C(MS,0,False,False)")
25 loops, best of 3: 15.6 ms per loop
My question: Why is copying zero data not much slower than writing
zero data?
Best regards,
Simon
--
To post to this group, send an email to [email protected]
To unsubscribe from this group, send an email to
[email protected]
For more options, visit this group at http://groups.google.com/group/sage-devel
URL: http://www.sagemath.org
