Clean up free module elements

[jdemeyer]

General clean-up using modern Cython code in preparation for follow-up tickets.

No changes in functionality (except perhaps details).

[git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

​5d011f4	Merge commit '106f5d41398794b13a6a683236cf219d49602312' into HEAD
​66d2f76	Clean up free module elements

[mmezzarobba]

_sparse_dot_product() (which you didn't touch) appears not to be used anywhere and could probably be deleted.

By the way, is there a reason to special-case the vectors of length zero in FreeModuleElement.dot_product()?

Otherwise lgtm.

[jdemeyer]

Replying to mmezzarobba:

By the way, is there a reason to special-case the vectors of length zero in FreeModuleElement.dot_product()?

Yes, to apply the following optimization: instead of starting with zero and a[i]*b[i], we start with a[0] * b[0] and add a[i]*b[i] for i >= 1.

I'm actually preparing a commit which refactors dot products, since the logic was a bit strange. With the new commit (still testing), there will be a cpdef method _dot_product_ for equal parents and _dot_product_coerce_ for parents which might be different.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​4c99ae2	Improve dot products
​c84246e	#10779: Improve coverage test for structure/element.pyx
​db023d4	Merge branch 'u/chapoton/10779' of ssh://trac.sagemath.org:22/sage into 10779
​2e30025	trac #10779 corrected 3 doctests
​9d72c81	Merge branch 'u/chapoton/10779' of ssh://trac.sagemath.org:22/sage into 10779
​9531937	trac #10779 correct failing doctest + more doc changes
​54396cd	Merge branch 'u/chapoton/10779' into 6.4
​dbf722e	Remove gcd, lcm, xgcd from element.pyx
​a6d357a	Merge ticket/10779 into ticket/17583

[jdemeyer]

I also merged #10779 to avoid a small merge conflict. The only relevant new commit is

​4c99ae2

Improve dot products

[mmezzarobba]

Replying to jdemeyer:

Yes, to apply the following optimization: instead of starting with zero and a[i]*b[i], we start with a[0] * b[0] and add a[i]*b[i] for i >= 1.

Fine. (I was not sure that it would be faster...)

Regarding your last commit, I agree with the changes, but I don't understand why dot_product is defined in FreeModuleElement rather than in Vector. Actually I don't understand the point of the distinction between Vector and FreeModuleElement at all.

Also, I think we can do two additional simplifications related to dot_product:

diff --git a/src/sage/matrix/matrix_generic_sparse.pyx b/src/sage/matrix/matrix_generic_sparse.pyx
index b2ff48a..a4cf07c 100644
--- a/src/sage/matrix/matrix_generic_sparse.pyx
+++ b/src/sage/matrix/matrix_generic_sparse.pyx
@@ -495,17 +495,6 @@ def Matrix_sparse_from_rows(X):
     return M(entries, coerce=False, copy=False)
 
 
-## def _sparse_dot_product(v, w):
-##     """
-##     INPUT:
-##         v and w are dictionaries with integer keys.
-##     """
-##     x = set(v.keys()).intersection(set(w.keys()))
-##     a = 0
-##     for k in x:
-##         a = a + v[k]*w[k]
-##     return a
-
 cdef _convert_sparse_entries_to_dict(entries):
     e = {}
     for i in xrange(len(entries)):
diff --git a/src/sage/modules/vector_double_dense.pyx b/src/sage/modules/vector_double_dense.pyx
index 9efe536..279ce58 100644
--- a/src/sage/modules/vector_double_dense.pyx
+++ b/src/sage/modules/vector_double_dense.pyx
@@ -389,8 +389,6 @@ cdef class Vector_double_dense(free_module_element.FreeModuleElement):
             sage: w*v
             1.0
         """
-        if not right.parent() == self.parent():
-            right = self.parent().ambient_module()(right)
         if self._degree == 0:
             from copy import copy
             return copy(self)

[jdemeyer]

Replying to mmezzarobba:

Replying to jdemeyer:

Yes, to apply the following optimization: instead of starting with zero and a[i]*b[i], we start with a[0] * b[0] and add a[i]*b[i] for i >= 1.

Fine. (I was not sure that it would be faster...)

It's always going to be somewhat faster and it avoids extra work in case the parents are not equal.

Regarding your last commit, I agree with the changes, but I don't understand why dot_product is defined in FreeModuleElement rather than in Vector.

I could easily move it...

Actually I don't understand the point of the distinction between Vector and FreeModuleElement at all.

Currently in Sage, the only Vectors are also FreeModuleElements. But one could envision a parent which is not a free module...

Also, I think we can do two additional simplifications related to dot_product:

diff --git a/src/sage/matrix/matrix_generic_sparse.pyx b/src/sage/matrix/matrix_generic_sparse.pyx
index b2ff48a..a4cf07c 100644
--- a/src/sage/matrix/matrix_generic_sparse.pyx
+++ b/src/sage/matrix/matrix_generic_sparse.pyx
@@ -495,17 +495,6 @@ def Matrix_sparse_from_rows(X):
     return M(entries, coerce=False, copy=False)
 
 
-## def _sparse_dot_product(v, w):
-##     """
-##     INPUT:
-##         v and w are dictionaries with integer keys.
-##     """
-##     x = set(v.keys()).intersection(set(w.keys()))
-##     a = 0
-##     for k in x:
-##         a = a + v[k]*w[k]
-##     return a
-
 cdef _convert_sparse_entries_to_dict(entries):
     e = {}
     for i in xrange(len(entries)):

Absolutely not on this ticket, but see #17663.

[jdemeyer]

Replying to mmezzarobba:

Regarding your last commit, I agree with the changes, but I don't understand why dot_product is defined in FreeModuleElement rather than in Vector.

For consistency, I would prefer to keep dot_product in FreeModuleElement. For pairwise_product() (which I didn't change), we also have pairwise_product on the level of FreeModuleElement but _pairwise_product_ on the level of Vector. Further refactoring would need to involve all kinds of products (dot, cross and pairwise) and I would prefer not to do this now.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​dcbf770

Fix zero-dimensional dot product

[jdemeyer]

Despite the fact that "Trac's automerging failed", the branch actually merges when using git.

[mmezzarobba]

Replying to jdemeyer:

Currently in Sage, the only Vectors are also FreeModuleElements. But one could envision a parent which is not a free module...

Sure, but either its elements would derive direclty from ModuleElement, or (I'd say) much of what FreeModuleElement currently does would need to be moved to Vector. Anyway, if you feel that dot_product should stay in FreeModuleElement until someone does this kind of refactoring, I'm fine with that.

Thanks for you work on this ticket!