#23978 closed enhancement (fixed)
Rich comparison for Modules
Reported by:  sbrandhorst  Owned by:  

Priority:  major  Milestone:  sage8.2 
Component:  linear algebra  Keywords:  
Cc:  Merged in:  
Authors:  Simon Brandhorst, Paolo Menegatti  Reviewers:  Travis Scrimshaw 
Report Upstream:  N/A  Work issues:  
Branch:  45c8b46 (Commits, GitHub, GitLab)  Commit:  
Dependencies:  Stopgaps: 
Description (last modified by )
Currently, there is an absolute ordering forced onto free modules. Mathematically this ordering has only little meaning.
This ticket is to order free modules by inclusion. This is a partial order. More precisely:
 Ambient spaces/modules compare equal iff their basering, rank, and inner_product_matrix are equal.
 Two ambient modules compare
A <= B
if their rank and inner_product matrix are equal andA.base_ring()
is a subring ofB.base_ring()
 Two submodules
S1
,S2
compare only if they lie in the same ambient (space/module). Here same means they compare equal with==
as defined above.
Also see the related issue: #11579
Change History (53)
comment:1 Changed 5 years ago by
 Branch set to u/sbrandhorst/rich_comparison_for_modules
comment:2 Changed 5 years ago by
 Commit set to a48e875a017f8449ea1b220aebf8f11421c06be9
comment:3 Changed 5 years ago by
 Branch changed from u/sbrandhorst/rich_comparison_for_modules to u/pmenegat/rich_comparison_for_modules
comment:4 Changed 5 years ago by
 Branch changed from u/pmenegat/rich_comparison_for_modules to u/sbrandhorst/rich_comparison_for_modules
comment:5 Changed 5 years ago by
 Commit changed from a48e875a017f8449ea1b220aebf8f11421c06be9 to ea965e8b12e0013132ec03f4d8a25d3c0a8a05d2
comment:6 Changed 5 years ago by
 Commit changed from ea965e8b12e0013132ec03f4d8a25d3c0a8a05d2 to 7c4e4ca1cc2e2d486eb389dc660fabfc8b3ad432
Branch pushed to git repo; I updated commit sha1. New commits:
7c4e4ca  Cleanup a leftover __eq__

comment:7 Changed 5 years ago by
 Commit changed from 7c4e4ca1cc2e2d486eb389dc660fabfc8b3ad432 to e9153afc644475368f8912d8afb6ea6fad1f1b14
Branch pushed to git repo; I updated commit sha1. New commits:
e9153af  Merge branch 'develop' into t/23978/rich_comparison_for_modules

comment:8 Changed 5 years ago by
 Reviewers set to Simon Brandhorst
 Status changed from new to needs_review
Please put your full name in the author field.
comment:9 Changed 5 years ago by
 Status changed from needs_review to needs_work
A bunch of doctests in the module folder fail. Check them out please.
comment:10 Changed 5 years ago by
Also use the inner product matrix for comparison of ambient modules.
#23703. There was a merge conflict there.
That is a reason for some of the doctest failures.
Make sure to doctest also exotic rings like
ZZ[x]/x^2
, QQ[x,y]/(xy)
, Number fields, GF(p)[x]
etc. all these guys are used!
comment:11 Changed 5 years ago by
a not implemented error is okay there  but no false results!
comment:12 Changed 5 years ago by
 Branch changed from u/sbrandhorst/rich_comparison_for_modules to u/pmenegat/rich_comparison_for_modules
comment:13 Changed 5 years ago by
 Branch changed from u/pmenegat/rich_comparison_for_modules to u/sbrandhorst/rich_comparison_for_modules
comment:14 Changed 5 years ago by
 Branch changed from u/sbrandhorst/rich_comparison_for_modules to u/pmenegat/rich_comparison_for_modules
comment:15 Changed 5 years ago by
 Commit changed from e9153afc644475368f8912d8afb6ea6fad1f1b14 to 02a3458c6ddc64b225239f46b4c01ec7393d6527
Branch pushed to git repo; I updated commit sha1. New commits:
02a3458  added method `is_contained` and some bug corected

comment:16 Changed 5 years ago by
Some of the old doctests are missing. We should never loose doctests. For example I did not find
We test that :trac:`5525` is fixed:: sage: A = (QQ^1).span([[1/3]],ZZ); B = (QQ^1).span([[1]],ZZ); sage: A.intersection(B) Free module of degree 1 and rank 1 over Integer Ring Echelon basis matrix: [1]
Or
Comparison with a quotient module (see :trac:`10513`):: sage: M = QQ^3 / [[1,2,3]] sage: V = QQ^2 sage: V == M False sage: M == V False
Check if other doctests are missing as well.
comment:17 Changed 5 years ago by
 Commit changed from 02a3458c6ddc64b225239f46b4c01ec7393d6527 to c689609651f7e466461262f25f9da483b781ecb7
Branch pushed to git repo; I updated commit sha1. New commits:
c689609  Doctest added and some correction relative quotient module

comment:18 Changed 5 years ago by
 Commit changed from c689609651f7e466461262f25f9da483b781ecb7 to 1b52cd873a2cb5f7d897036e786b80f16c01f7dd
Branch pushed to git repo; I updated commit sha1. New commits:
1b52cd8  Added method `is_contained`, used for comparing, for free_quadratic_modules

comment:19 Changed 5 years ago by
 Status changed from needs_work to needs_review
Now comparing operators use the is_contained
method. It is just is_submodule
for free modules, but it ask also that the inner product is preserved for free quadratic modules.
Further comparing for other classes could be implemented overriding the method is_contained
, asking for different criteria
comment:20 Changed 5 years ago by
 Description modified (diff)
comment:21 Changed 5 years ago by
 Description modified (diff)
comment:22 Changed 5 years ago by
the is_contained method is a good idea. Though I am unsure about the name. Here are a few comments:
 We compare modules A and B. Module B has more structure than A.
If we can give A the the same type of extra structure as B in a canonical way then
A and B should be compared as modules with extra structure. I would expect the user to care about the extra structure.
Or short: compare everything that you can as long as it makes sense.
Example:
sage: A = ZZ^2 sage: B = FreeQuadraticModule(ZZ,2,matrix.identity(2)*2) sage: A == B False
 Module equality should use
echelonized_basis_matrix()
where possible for example over Fields and ZZ. (I think over general PIDs the echelon for is not yet unique.)
I would expect it to be much faster for modules of large rank and it was used before. So if you want to change that, you have to prove that your implementation is consistently faster.
 if possible use
from sage.structure.richcmp import richcmp_by_eq_and_lt
this results in less lines of code. In particular the code is easier maintainable then.
if self.inner_product_matrix()==other.inner_product_matrix() and self.is_submodule(other): return True else: return False
but this is equivalent to the shorter
a = self.inner_product_matrix()==other.inner_product_matrix() b = self.is_submodule(other) return a and b
Sry my pc at work is not really working at the moment.
comment:23 Changed 5 years ago by
 Status changed from needs_review to needs_work
comment:24 Changed 5 years ago by
 Extra structure is given by
is_contained
, elsewhere the two modules are compared by their greatest common structure.
 I think (but I'm not sure) that
solve_left
(used byis_submodule
) it is already optimized for fields and ZZ, isn't it?
 Personally I found that the if structure is more readable, but I'm not really an expert in that, so you are free to modify that
comment:25 Changed 5 years ago by
 Branch changed from u/pmenegat/rich_comparison_for_modules to u/sbrandhorst/rich_comparison_for_modules
comment:26 Changed 5 years ago by
 Commit changed from 1b52cd873a2cb5f7d897036e786b80f16c01f7dd to d357e794bc35bacde5a009ae7bee788bfced3f2e
Branch pushed to git repo; I updated commit sha1. New commits:
d357e79  Removed unnecessary imports

comment:27 Changed 5 years ago by
 Status changed from needs_work to needs_review
Major rewrite.
Decided to abandon the is_contained
method.
Reason is that overwriting can result in "==" and other operators not being symmetric anymore.
Decided to use echelonized basis matrix for equality. My reason is that it is cached often anyways.
New commits:
b590625  A first version with richcmp_by_eq_and_lt ... doctests explode...

c30ab64  Replaced richcmp_by_eq_and_lt by __eq__ __lt__ __neq__ __geq__ etc. doctests pass now.

d357e79  Removed unnecessary imports

comment:28 Changed 5 years ago by
 Commit changed from d357e794bc35bacde5a009ae7bee788bfced3f2e to 4407c8a0670abf12af0622dbc31d348b35ee9b0c
comment:29 Changed 5 years ago by
 Commit changed from 4407c8a0670abf12af0622dbc31d348b35ee9b0c to 97e2324619344ab6f4b2034c3aba003953f64aab
Branch pushed to git repo; I updated commit sha1. New commits:
97e2324  Removed __eq__ from quotient_module.py. The comparison is all done in free_modules

comment:30 Changed 5 years ago by
 Reviewers Simon Brandhorst deleted
comment:31 Changed 5 years ago by
 Commit changed from 97e2324619344ab6f4b2034c3aba003953f64aab to 17655fd0c08f69032a7caaa57b43595945064b8e
comment:32 Changed 5 years ago by
The ordering of free modules is used in the comparison of sage/modular and causes a bunch of doctest failures.
comment:33 Changed 5 years ago by
 Status changed from needs_review to needs_work
comment:34 Changed 5 years ago by
 Commit changed from 17655fd0c08f69032a7caaa57b43595945064b8e to b0f6fc434453ca23961060c9bc73c508e2574af5
comment:35 Changed 5 years ago by
Following the discussion
https://groups.google.com/forum/#!topic/sagedevel/DtpvPrwRi4s
I have moved the total ordering to a helper class total_module_order
Still needs some documentation.
comment:36 Changed 5 years ago by
 Commit changed from b0f6fc434453ca23961060c9bc73c508e2574af5 to 219478c836dce0c8a40c84ab35ff1492eb2ec090
comment:37 Changed 5 years ago by
 Commit changed from 219478c836dce0c8a40c84ab35ff1492eb2ec090 to d54fcfaaf3fa488b594723eeb91bb0ac96bb5a18
Branch pushed to git repo; I updated commit sha1. New commits:
d54fcfa  Total ordering works for quotient modules now.

comment:38 Changed 5 years ago by
 Commit changed from d54fcfaaf3fa488b594723eeb91bb0ac96bb5a18 to 800e98b16e583a070f8d90b44ae89f99d54e1bc3
Branch pushed to git repo; I updated commit sha1. New commits:
800e98b  Added a few doctests

comment:39 Changed 5 years ago by
 Status changed from needs_work to needs_review
comment:40 Changed 5 years ago by
 Commit changed from 800e98b16e583a070f8d90b44ae89f99d54e1bc3 to 4362007dd7178a82128e66ce6ffec61ec381aafc
Branch pushed to git repo; I updated commit sha1. New commits:
4362007  Merge branch 'develop' into t/23978/rich_comparison_for_modules

comment:41 Changed 5 years ago by
 Milestone changed from sage8.1 to sage8.2
New commits:
4362007  Merge branch 'develop' into t/23978/rich_comparison_for_modules

comment:42 followups: ↓ 43 ↓ 45 Changed 5 years ago by
I (finally) have some time to do a review of this. Here are my comments:
_total_order_cmp
is only a total order up to there being a total ordering on the base rings, which there is not. So the name is incorrect IMO.
 We should not call this
cmp
because it does not behave like thecmp
function as it does not return1,0,1
.
 I understand the reasoning why you did the implementation of
total_module_order
the way you did; at least to me it seems like you are mimickingcmp_to_key
. However, it feels overengineered and is cumbersome to use IMO. I would rename_total_order_cmp
to perhaps_echelon_matrix_richcmp
. For the (currently) one case we use it as a key, that is when you use thetotal_module_order
class, which should be called something likeEchelonMatrixKey
. Note that if we really do need to use this key/ordering, then there should be a mathematical reasoning behind this ordering, which would invalidate some of your reasoning.
 You need to provide a deprecation warning to all users when using
<
,<=
,>
,>=
saying the ordering on modules has changes as this is not a bug but a change in convention. This change will almost certainly break code in the wild.
 It looks like you have removed the quick check for if
U.ambient_vector_space() == V
. This is a very quick check and a good optimization.
 These changes are needed:
 ::  + We compare a one dimensional space to a two dimensional  space: + space::
 ::  + We compare a `\ZZ`module to a onedimensional  space. + space::
  :: Comparison with a submodule::
Some more minor comments:
.. note::
>.. NOTE::
 Indentation errors in the doc for
total_module_order
.  Use
``self``
in the docstrings.  Did you move
echelonized_basis_matrix
or is that a byproduct of how git does the diff? Anyways, it might create merge conflicts by how the changes are done, so it is better to keep things in the order they are. Also remove the added bunch of blank lines after; they make the file less consistent.  PEP8 says put a space on both sides of relations, e.g.,
!=
.  Remove trailing whitespace.
comment:43 in reply to: ↑ 42 Changed 5 years ago by
Replying to tscrim:
 I understand the reasoning why you did the implementation of
total_module_order
the way you did; at least to me it seems like you are mimickingcmp_to_key
. However, it feels overengineered and is cumbersome to use IMO. I would rename_total_order_cmp
to perhaps_echelon_matrix_richcmp
. For the (currently) one case we use it as a key, that is when you use thetotal_module_order
class, which should be called something likeEchelonMatrixKey
. Note that if we really do need to use this key/ordering, then there should be a mathematical reasoning behind this ordering, which would invalidate some of your reasoning.
It is horrible indeed. My reason was that the old comparison is still used in the sage/modular folder. And I do not understand the intrinsics there and did not want to break the doctests. Thus I needed an ordering that behaves exactly like the old one. Just mimicking the old one seemed the best way. Feel free to improve it^{}
comment:44 Changed 5 years ago by
 Commit changed from 4362007dd7178a82128e66ce6ffec61ec381aafc to 488f9eec1a61e9adaba813749e9a96546b346264
Branch pushed to git repo; I updated commit sha1. New commits:
488f9ee  Changed name of total_module_order to EchelonMatrixKey and general cleanup

comment:45 in reply to: ↑ 42 Changed 5 years ago by
Replying to tscrim:
 Note that if we really do need to use this key/ordering, then there should be a mathematical reasoning behind this ordering, which would invalidate some of your reasoning.
It seems the reason is for testing purposes. See https://groups.google.com/forum/#!topic/sagedevel/DtpvPrwRi4s
 It looks like you have removed the quick check for if
U.ambient_vector_space() == V
. This is a very quick check and a good optimization.
I suppose you are referring to
 try:  if self.ambient_vector_space() != other.ambient_vector_space():  return False  if other == other.ambient_vector_space():  return True  except AttributeError:  # Not all free modules have an ambient_vector_space.  pass
I expect this code block only speeds up comparison if
self.ambient_vector_space() is other.ambient_vector_space() and other is other.ambient_vector_space()
and else slows it down a bit as then it is checking baserings ranks degrees etc. twice. How about:
try: # optimization for ambient spaces if (self.ambient_vector_space() is other.ambient_vector_space() and other is other.ambient_vector_space()): return True except AttributeError: # Not all free modules have an ambient_vector_space. pass
comment:46 Changed 5 years ago by
See
https://groups.google.com/forum/#!topic/sagedevel/KzWnTl90EAg
for a discussion on whether ZZ^2
is or is not a submodule of CC^2
.
comment:47 Changed 5 years ago by
 Reviewers set to Travis Scrimshaw
I have reverted back to the old behavior of is_submodule
as removing the above "optimization" changes the behavior, and this ticket already touches enough already.
I also moved around some tests, removed duplicate ones, did some general cleanup and simplification, and found a very annoying bug with _eq
that came about because of nonunique parents and that self.base_ring() is IntegerRing
is never going to be true because the RHS is a type, not an instance.
I believe if my changes are good, then positive review (i.e., over the time I was looking at this, I might have forgotten one of my needstobedonebeforepositivereview notes; please check).
comment:48 Changed 5 years ago by
 Branch changed from u/sbrandhorst/rich_comparison_for_modules to public/linear_algebra/richcmp_modules23978
 Commit changed from 488f9eec1a61e9adaba813749e9a96546b346264 to 7a22aa341c8cac36a320e78dbac985c7db06b404
New commits:
736fc26  Merge branch 'u/sbrandhorst/rich_comparison_for_modules' of git://trac.sagemath.org/sage into public/linear_algebra/richcmp_modules23978

dea8675  Merge commit '736fc26' into public/linear_algebra/richcmp_modules23978

7a22aa3  Initial round of reviewer changes and reverting is_submodule behavior.

comment:49 Changed 5 years ago by
Green patchbot as well.
comment:50 Changed 5 years ago by
 Commit changed from 7a22aa341c8cac36a320e78dbac985c7db06b404 to 45c8b46555c3869a21665cb2563c7f866efd20f5
Branch pushed to git repo; I updated commit sha1. New commits:
45c8b46  Fix a latex issue with // and rawstrings

comment:51 Changed 5 years ago by
 Status changed from needs_review to positive_review
Your changes look reasonable. Thank you for the review.
New commits:
45c8b46  Fix a latex issue with // and rawstrings

comment:52 Changed 5 years ago by
 Branch changed from public/linear_algebra/richcmp_modules23978 to 45c8b46555c3869a21665cb2563c7f866efd20f5
 Resolution set to fixed
 Status changed from positive_review to closed
comment:53 Changed 4 years ago by
 Commit 45c8b46555c3869a21665cb2563c7f866efd20f5 deleted
The deprecation warning at line 1272 modules/free_module.py
displays the wrong ticket number (23878
instead of 23987
)!
Branch pushed to git repo; I updated commit sha1. New commits:
Removed the @richcmp_method decorator.