Opened 6 years ago

Closed 6 years ago

#17583 closed enhancement (fixed)

Clean up free module elements

Reported by: jdemeyer Owned by:
Priority: major Milestone: sage-6.5
Component: linear algebra Keywords:
Cc: Merged in:
Authors: Jeroen Demeyer Reviewers: Marc Mezzarobba
Report Upstream: N/A Work issues:
Branch: dcbf770 (Commits) Commit: dcbf770938972358639fc637dc0bf99ddf2489d6
Dependencies: #17561, #10779 Stopgaps:

Description (last modified by jdemeyer)

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

No changes in functionality (except perhaps details).

Change History (16)

comment:1 Changed 6 years ago by jdemeyer

  • Description modified (diff)

comment:2 Changed 6 years ago by jdemeyer

  • Branch set to u/jdemeyer/ticket/17583
  • Created changed from 01/05/15 13:26:20 to 01/05/15 13:26:20
  • Modified changed from 01/05/15 14:31:23 to 01/05/15 14:31:23

comment:3 Changed 6 years ago by git

  • Commit set to 66d2f76d685f654f18b77f0051ae85235a4f846f

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

5d011f4Merge commit '106f5d41398794b13a6a683236cf219d49602312' into HEAD
66d2f76Clean up free module elements

comment:4 Changed 6 years ago by jdemeyer

  • Dependencies changed from #10513, #17561 to #17561
  • Status changed from new to needs_review

comment:5 follow-up: Changed 6 years ago by mmezzarobba

  • Reviewers set to Marc Mezzarobba
  • Status changed from needs_review to needs_info

_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.

comment:6 in reply to: ↑ 5 ; follow-up: Changed 6 years ago by 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.

comment:7 Changed 6 years ago by git

  • Commit changed from 66d2f76d685f654f18b77f0051ae85235a4f846f to a6d357a8b2874aaec970aa0d2afc3fa14d60969e

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

4c99ae2Improve dot products
c84246e#10779: Improve coverage test for structure/element.pyx
db023d4Merge branch 'u/chapoton/10779' of ssh://trac.sagemath.org:22/sage into 10779
2e30025trac #10779 corrected 3 doctests
9d72c81Merge branch 'u/chapoton/10779' of ssh://trac.sagemath.org:22/sage into 10779
9531937trac #10779 correct failing doctest + more doc changes
54396cdMerge branch 'u/chapoton/10779' into 6.4
dbf722eRemove gcd, lcm, xgcd from element.pyx
a6d357aMerge ticket/10779 into ticket/17583

comment:8 Changed 6 years ago by jdemeyer

  • Status changed from needs_info to needs_review

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

4c99ae2Improve dot products

comment:9 in reply to: ↑ 6 ; follow-ups: Changed 6 years ago by 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)

comment:10 in reply to: ↑ 9 ; follow-up: Changed 6 years ago by 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.

comment:11 in reply to: ↑ 9 Changed 6 years ago by 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.

comment:12 Changed 6 years ago by git

  • Commit changed from a6d357a8b2874aaec970aa0d2afc3fa14d60969e to dcbf770938972358639fc637dc0bf99ddf2489d6

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

dcbf770Fix zero-dimensional dot product

comment:13 Changed 6 years ago by jdemeyer

  • Dependencies changed from #17561 to #17561, #10779

comment:14 Changed 6 years ago by jdemeyer

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

comment:15 in reply to: ↑ 10 Changed 6 years ago by mmezzarobba

  • Status changed from needs_review to positive_review

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!

comment:16 Changed 6 years ago by vbraun

  • Branch changed from u/jdemeyer/ticket/17583 to dcbf770938972358639fc637dc0bf99ddf2489d6
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.