Opened 5 years ago

Closed 5 years ago

Last modified 4 years ago

#23978 closed enhancement (fixed)

Rich comparison for Modules

Reported by: sbrandhorst Owned by:
Priority: major Milestone: sage-8.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:

Status badges

Description (last modified by sbrandhorst)

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 and A.base_ring() is a subring of B.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 sbrandhorst

  • Branch set to u/sbrandhorst/rich_comparison_for_modules

comment:2 Changed 5 years ago by git

  • Commit set to a48e875a017f8449ea1b220aebf8f11421c06be9

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

a48e875Removed the @richcmp_method decorator.

comment:3 Changed 5 years ago by pmenegat

  • Branch changed from u/sbrandhorst/rich_comparison_for_modules to u/pmenegat/rich_comparison_for_modules

comment:4 Changed 5 years ago by sbrandhorst

  • Branch changed from u/pmenegat/rich_comparison_for_modules to u/sbrandhorst/rich_comparison_for_modules

comment:5 Changed 5 years ago by sbrandhorst

  • Commit changed from a48e875a017f8449ea1b220aebf8f11421c06be9 to ea965e8b12e0013132ec03f4d8a25d3c0a8a05d2

...


New commits:

51e7afaReplaced `__richcmp__` operator by comparison methods (`__le__`,`__lt__`, etc.) using `is_submodule`
ea965e8Merge branch 'u/sbrandhorst/rich_comparison_for_modules' of git://trac.sagemath.org/sage into t/23978/rich_comparison_for_modules

comment:6 Changed 5 years ago by git

  • Commit changed from ea965e8b12e0013132ec03f4d8a25d3c0a8a05d2 to 7c4e4ca1cc2e2d486eb389dc660fabfc8b3ad432

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

7c4e4caCleanup a leftover __eq__

comment:7 Changed 5 years ago by git

  • Commit changed from 7c4e4ca1cc2e2d486eb389dc660fabfc8b3ad432 to e9153afc644475368f8912d8afb6ea6fad1f1b14

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

e9153afMerge branch 'develop' into t/23978/rich_comparison_for_modules

comment:8 Changed 5 years ago by sbrandhorst

  • 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 sbrandhorst

  • 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 sbrandhorst

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!

Last edited 5 years ago by sbrandhorst (previous) (diff)

comment:11 Changed 5 years ago by sbrandhorst

a not implemented error is okay there - but no false results!

comment:12 Changed 5 years ago by pmenegat

  • Branch changed from u/sbrandhorst/rich_comparison_for_modules to u/pmenegat/rich_comparison_for_modules

comment:13 Changed 5 years ago by sbrandhorst

  • Branch changed from u/pmenegat/rich_comparison_for_modules to u/sbrandhorst/rich_comparison_for_modules

comment:14 Changed 5 years ago by pmenegat

  • Branch changed from u/sbrandhorst/rich_comparison_for_modules to u/pmenegat/rich_comparison_for_modules

comment:15 Changed 5 years ago by git

  • Commit changed from e9153afc644475368f8912d8afb6ea6fad1f1b14 to 02a3458c6ddc64b225239f46b4c01ec7393d6527

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

02a3458added method `is_contained` and some bug corected

comment:16 Changed 5 years ago by sbrandhorst

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 git

  • Commit changed from 02a3458c6ddc64b225239f46b4c01ec7393d6527 to c689609651f7e466461262f25f9da483b781ecb7

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

c689609Doctest added and some correction relative quotient module

comment:18 Changed 5 years ago by git

  • Commit changed from c689609651f7e466461262f25f9da483b781ecb7 to 1b52cd873a2cb5f7d897036e786b80f16c01f7dd

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

1b52cd8Added method `is_contained`, used for comparing, for free_quadratic_modules

comment:19 Changed 5 years ago by pmenegat

  • 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 sbrandhorst

  • Description modified (diff)

comment:21 Changed 5 years ago by sbrandhorst

  • Description modified (diff)

comment:22 Changed 5 years ago by sbrandhorst

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 sbrandhorst

  • Status changed from needs_review to needs_work

comment:24 Changed 5 years ago by pmenegat

  • 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 by is_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
Last edited 5 years ago by pmenegat (previous) (diff)

comment:25 Changed 5 years ago by sbrandhorst

  • Branch changed from u/pmenegat/rich_comparison_for_modules to u/sbrandhorst/rich_comparison_for_modules

comment:26 Changed 5 years ago by git

  • Commit changed from 1b52cd873a2cb5f7d897036e786b80f16c01f7dd to d357e794bc35bacde5a009ae7bee788bfced3f2e

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

d357e79Removed unnecessary imports

comment:27 Changed 5 years ago by sbrandhorst

  • 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:

b590625A first version with richcmp_by_eq_and_lt ... doctests explode...
c30ab64Replaced richcmp_by_eq_and_lt by __eq__ __lt__ __neq__ __geq__ etc. doctests pass now.
d357e79Removed unnecessary imports

comment:28 Changed 5 years ago by git

  • Commit changed from d357e794bc35bacde5a009ae7bee788bfced3f2e to 4407c8a0670abf12af0622dbc31d348b35ee9b0c

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

0b5fe5eMerge branch 'develop' into t/23978/rich_comparison_for_modules
4407c8aFixed comparison with FreeQuotient modules

comment:29 Changed 5 years ago by git

  • Commit changed from 4407c8a0670abf12af0622dbc31d348b35ee9b0c to 97e2324619344ab6f4b2034c3aba003953f64aab

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

97e2324Removed __eq__ from quotient_module.py. The comparison is all done in free_modules

comment:30 Changed 5 years ago by sbrandhorst

  • Authors set to Simon Brandhorst, Paolo Menegatti
  • Reviewers Simon Brandhorst deleted

comment:31 Changed 5 years ago by git

  • Commit changed from 97e2324619344ab6f4b2034c3aba003953f64aab to 17655fd0c08f69032a7caaa57b43595945064b8e

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

c9979ceMerge branch 'develop' into t/23978/rich_comparison_for_modules
17655fdextra effort if is_subring is not implemented.

comment:32 Changed 5 years ago by sbrandhorst

The ordering of free modules is used in the comparison of sage/modular and causes a bunch of doctest failures.

Last edited 5 years ago by sbrandhorst (previous) (diff)

comment:33 Changed 5 years ago by sbrandhorst

  • Status changed from needs_review to needs_work

comment:34 Changed 5 years ago by git

  • Commit changed from 17655fd0c08f69032a7caaa57b43595945064b8e to b0f6fc434453ca23961060c9bc73c508e2574af5

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

9b0d483Merge branch 'develop' into t/23978/rich_comparison_for_modules
ae0be0bAdded alternative total ordering key function
b0f6fc4Use the old total ordering in /src/sage/modular to fix doctest failures

comment:35 Changed 5 years ago by sbrandhorst

Following the discussion https://groups.google.com/forum/#!topic/sage-devel/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 git

  • Commit changed from b0f6fc434453ca23961060c9bc73c508e2574af5 to 219478c836dce0c8a40c84ab35ff1492eb2ec090

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

11d57fbNow with @richcmp_method decorator
219478cReverting to solve(other.basis_matrix()) which is much faster.

comment:37 Changed 5 years ago by git

  • Commit changed from 219478c836dce0c8a40c84ab35ff1492eb2ec090 to d54fcfaaf3fa488b594723eeb91bb0ac96bb5a18

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

d54fcfaTotal ordering works for quotient modules now.

comment:38 Changed 5 years ago by git

  • Commit changed from d54fcfaaf3fa488b594723eeb91bb0ac96bb5a18 to 800e98b16e583a070f8d90b44ae89f99d54e1bc3

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

800e98bAdded a few doctests

comment:39 Changed 5 years ago by sbrandhorst

  • Status changed from needs_work to needs_review

comment:40 Changed 5 years ago by git

  • Commit changed from 800e98b16e583a070f8d90b44ae89f99d54e1bc3 to 4362007dd7178a82128e66ce6ffec61ec381aafc

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

4362007Merge branch 'develop' into t/23978/rich_comparison_for_modules

comment:41 Changed 5 years ago by sbrandhorst

  • Milestone changed from sage-8.1 to sage-8.2

New commits:

4362007Merge branch 'develop' into t/23978/rich_comparison_for_modules

comment:42 follow-ups: Changed 5 years ago by tscrim

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 the cmp function as it does not return -1,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 mimicking cmp_to_key. However, it feels over-engineered 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 the total_module_order class, which should be called something like EchelonMatrixKey. 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 one-dimensional
    -        space.
    +        space::
    
    -
    -        ::
     
             Comparison with a sub-module::
    

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 by-product 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.
Last edited 5 years ago by tscrim (previous) (diff)

comment:43 in reply to: ↑ 42 Changed 5 years ago by sbrandhorst

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 mimicking cmp_to_key. However, it feels over-engineered 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 the total_module_order class, which should be called something like EchelonMatrixKey. 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 git

  • Commit changed from 4362007dd7178a82128e66ce6ffec61ec381aafc to 488f9eec1a61e9adaba813749e9a96546b346264

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

488f9eeChanged name of total_module_order to EchelonMatrixKey and general cleanup

comment:45 in reply to: ↑ 42 Changed 5 years ago by sbrandhorst

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/sage-devel/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 sbrandhorst

See https://groups.google.com/forum/#!topic/sage-devel/KzWnTl90EAg for a discussion on whether ZZ^2 is or is not a submodule of CC^2.

comment:47 Changed 5 years ago by tscrim

  • 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 non-unique 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 needs-to-be-done-before-positive-review notes; please check).

comment:48 Changed 5 years ago by tscrim

  • Branch changed from u/sbrandhorst/rich_comparison_for_modules to public/linear_algebra/richcmp_modules-23978
  • Commit changed from 488f9eec1a61e9adaba813749e9a96546b346264 to 7a22aa341c8cac36a320e78dbac985c7db06b404

New commits:

736fc26Merge branch 'u/sbrandhorst/rich_comparison_for_modules' of git://trac.sagemath.org/sage into public/linear_algebra/richcmp_modules-23978
dea8675Merge commit '736fc26' into public/linear_algebra/richcmp_modules-23978
7a22aa3Initial round of reviewer changes and reverting is_submodule behavior.

comment:49 Changed 5 years ago by tscrim

Green patchbot as well.

comment:50 Changed 5 years ago by git

  • Commit changed from 7a22aa341c8cac36a320e78dbac985c7db06b404 to 45c8b46555c3869a21665cb2563c7f866efd20f5

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

45c8b46Fix a latex issue with // and rawstrings

comment:51 Changed 5 years ago by sbrandhorst

  • Status changed from needs_review to positive_review

Your changes look reasonable. Thank you for the review.


New commits:

45c8b46Fix a latex issue with // and rawstrings

comment:52 Changed 5 years ago by vbraun

  • Branch changed from public/linear_algebra/richcmp_modules-23978 to 45c8b46555c3869a21665cb2563c7f866efd20f5
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:53 Changed 4 years ago by vdelecroix

  • Commit 45c8b46555c3869a21665cb2563c7f866efd20f5 deleted

The deprecation warning at line 1272 modules/free_module.py displays the wrong ticket number (23878 instead of 23987)!

Note: See TracTickets for help on using tickets.