On Mon, Feb 14, 2011 at 6:04 AM, Simon King <[email protected]> wrote: > 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?
For some rings, copy might be able to use memcpy, where as zeroing it out might be a big loop. Really, there should be a method for getting a new empty matrix (which may or may not be all zeros) in the fastest way possible. - Robert -- 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
