Opened 6 years ago

Last modified 3 years ago

#16893 needs_work defect

Free modules over PIDs

Reported by: aly.deines Owned by:
Priority: major Milestone: sage-7.4
Component: linear algebra Keywords: free modules, PID
Cc: jakobkroeker Merged in:
Authors: Aly Deines Reviewers: Vincent Delecroix
Report Upstream: N/A Work issues:
Branch: u/aly.deines/ticket/16893 (Commits) Commit: ac769b20202a7942804f8c29c4e6aefdf3efb0cc
Dependencies: Stopgaps:

Description (last modified by aly.deines)

sage: F.<a> = NumberField(x^2-x-1)
sage: ZF = F.ring_of_integers()
sage: A = matrix(ZF,[[1,0,0,0],[0,-1,0,0],[0,0,1,0],[0,0,0,1]])
sage: B = identity_matrix(ZF,4)
sage: VA = (ZF^4).span(A)
sage: VB = (ZF^4).span(B)
sage: VB == VA
False

This should return true. As Sage is only checking the echelon form, it is not catching this.

To fix this I used the wrapped pseudo basis nfhnf and compute the Hermite normal form and the pseudo basis ideal list as _pseudo_hermite_matrix.

Change History (24)

comment:1 Changed 6 years ago by aly.deines

  • Branch set to u/aly.deines/free_modules_over_pids

comment:2 Changed 6 years ago by aly.deines

  • Authors set to aly.deines
  • Commit set to 867b1507389a0b3f3c4be024bffb0c8a1f1a2cb8
  • Component changed from PLEASE CHANGE to linear algebra
  • Description modified (diff)
  • Keywords free modules PID added
  • Status changed from new to needs_review
  • Type changed from PLEASE CHANGE to defect

New commits:

5b40230Added _pseudo_hermite_matrix so we can check equality of free modules over rings of integers of number fields.
867b150Added a _pseudo_basis_matrix method to modules/free_module.py and

comment:3 Changed 6 years ago by vdelecroix

  • Status changed from needs_review to needs_work

Hi,

There are (trivial) rebase to do on top of sage-6.7.beta2.

Apart that, in your commit there are a lot of trailing whitespaces (i.e. space before end of line) and you should get rid of them.

I did not check much about the code yet but I am currently doing it. Would be cool to have this integrated into Sage.

Vincent

comment:4 Changed 6 years ago by vdelecroix

After a first lecture:

  • self should not be mentioned in the INPUT section.
  • in your example [ideal(ZZ(p)) for p in ...] you could remove the ZZ. The output of prime_range are already integers.
  • ValueError("gens and ideal_list must have the same lenghth") chane lenghth into length
  • it is better to use ZZ is ZF rather than ZZ == ZF. The reason is that it does not involve Python comparisons (which might be tedious). Similarly, you can safely replace ideal_list == None with ideal_list is None
  • instead of pari(F) use F._pari_(). Doing that way you can remove pari from the imported modules. You can also go from pari to sage using .sage()
    sage: m = matrix([[2,1],[1,1]])
    sage: p = m._pari_()
    sage: p
    [2, 1; 1, 1]
    sage: p.sage()
    [2 1]
    [1 1]
    
    copying the entries one by one will be rather slow (it will not necessarily works well with number field elements).
  • you can replace [F.ideal(1) for id in range(len(self.gens()))] with [F.ideal(1)] * len(self.gens()).

Vincent

comment:5 Changed 4 years ago by chapoton

  • Authors changed from aly.deines to Aly Deines

comment:6 Changed 4 years ago by aly.deines

  • Branch changed from u/aly.deines/free_modules_over_pids to u/aly.deines/ticket/16893
  • Commit changed from 867b1507389a0b3f3c4be024bffb0c8a1f1a2cb8 to 79794d25857b10cb67d3d8a9c4776fe7bac57a20

comment:7 Changed 4 years ago by git

  • Commit changed from 79794d25857b10cb67d3d8a9c4776fe7bac57a20 to ea492287634dc0e2bc56c6eec50143b601082906

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

535ae3eCleaning up code.
ea49228Cleaning up code.

comment:8 Changed 4 years ago by aly.deines

  • Status changed from needs_work to needs_review

Cleaned up and rebased.

comment:9 Changed 4 years ago by vdelecroix

You should not use assert to check a test that may fail. You would better raise a NotImplementedError. In other words use the following template

if ZF is sage.rings.integer_ring.ZZ and ideal_list is None:
    ... case1 ...
elif ZF is sage.rings.integer_ring.ZZ:
    ... case2 ...
elif nf_order.is_NumberFieldOrder(ZF):
    ... case3 ...
else:
    raise NotImplementedError("_pseudo_hermite_matrix not implemented for XYZ")

comment:10 Changed 4 years ago by vdelecroix

  • Milestone changed from sage-6.4 to sage-7.4
  • Reviewers set to Vincent Delecroix
  • Status changed from needs_review to needs_work

Doctesting is very good.

  1. The docstring should start with a one line description. Then a linebreak. And then an optional longer description. The comment about the genericity of the code would better be in a NOTE section (see developer guide).
  1. Please fix the spaces in the definition of the function as
    def _pseudo_hermite_matrix(self, ideal_list=None):
    
    and always keep a space after a comma.
  1. typo: pseodo
  1. Would be good to point to a definition of pseudo-Hermite matrix.
  1. This
    +            #if the ideals are the same, compare the matrices
    +            if Ids == OIds:
    +                return cmp(Mat,Omat)
    +            #otherwise, compare the ideals.
    +            else:
    +                return cmp(Ids,OIds)
    
    can be replaced with
    return cmp(Ids, OIds) or cmp(Mat, Omat)
    
  1. Why did you move the position of import sage.misc.latex as latex in the list of imported modules at the top of the file?

comment:11 Changed 4 years ago by git

  • Commit changed from ea492287634dc0e2bc56c6eec50143b601082906 to 858c84326fde0045a737c737be5f28555fe8c310

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

858c843Changed assert to raise ValueError.

comment:12 Changed 4 years ago by git

  • Commit changed from 858c84326fde0045a737c737be5f28555fe8c310 to e64cf7ca7db12c3627f6ad9fabc6d83d7522dd44

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

e64cf7cChanged from ValueError to NotImplementedError.

comment:13 Changed 4 years ago by git

  • Commit changed from e64cf7ca7db12c3627f6ad9fabc6d83d7522dd44 to 092f96e2555ebdd710637afe76f5253fb92b5cc5

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

08fe242Edited to reflect reviewer suggestions.
092f96eWhite space.

comment:14 Changed 4 years ago by aly.deines

  • Status changed from needs_work to needs_review

Thanks!

And the move of import sage.misc.latex as latex was a relic of rebasing, but I've moved that back.

comment:15 Changed 4 years ago by vdelecroix

  • Status changed from needs_review to needs_work

One backquote is for latex and two for displaying code. Hence you should change `ideal_list` to ``ideal_list``.

The examples need to be in an EXAMPLES section.

len(self.gens()) -> self.ngens()

len(HM) -> HM.nrows()

len(HM[0]) -> HM.ncols()

comment:16 Changed 4 years ago by git

  • Commit changed from 092f96e2555ebdd710637afe76f5253fb92b5cc5 to 2cd281fa3f67ff9adb3de579816c1f2ff09e7489

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

e4b0fa2A few more suggested changes.
2cd281fRemoved some unnecessary imports.

comment:17 Changed 4 years ago by aly.deines

  • Status changed from needs_work to needs_review

comment:18 Changed 4 years ago by vdelecroix

Still from comment:15: the examples should be precedeed with EXAMPLES: (in the function _pseudo_hermite_matrix).

comment:19 Changed 4 years ago by git

  • Commit changed from 2cd281fa3f67ff9adb3de579816c1f2ff09e7489 to ac769b20202a7942804f8c29c4e6aefdf3efb0cc

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

ac769b2Added Examples label to the examples in the doctest.

comment:20 Changed 4 years ago by vdelecroix

The equality testing is likely to be broken on other PID too. Isn't it?

comment:21 Changed 4 years ago by vdelecroix

Indeed

sage: R = QQ['x']
sage: A = matrix(R, 3, [1,0,0,0,1,0,0,0,1])
sage: B = matrix(R, 3, [1,0,0,0,-1,0,0,0,1])
sage: (R^3).submodule(A) == (R^3).submodule(B)
False

Would be better to find something to solve other cases (or raise in error in the comparison code if this is hard to implement in general).

comment:22 Changed 4 years ago by vdelecroix

  • Status changed from needs_review to needs_work

comment:23 Changed 4 years ago by jakobkroeker

  • Cc jakobkroeker added

comment:24 Changed 3 years ago by sbrandhorst

Be aware of

  • #24031 Coercion between Matrices over orders and over the number field
  • #23978 Rich comparison for Modules
  • #11579 Free module equality, comparisons
Note: See TracTickets for help on using tickets.