Opened 4 years ago

Last modified 4 years ago

#19345 needs_work enhancement

Fast lexicographic iterator for module over ZZ/nZZ

Reported by: vdelecroix Owned by:
Priority: major Milestone: sage-6.10
Component: coding theory Keywords:
Cc: jsrn, dlucas Merged in:
Authors: Vincent Delecroix Reviewers:
Report Upstream: N/A Work issues:
Branch: u/vdelecroix/19345 (Commits) Commit: 5773c780ccd2b6084dff464da084df12ade378f0
Dependencies: #6452 Stopgaps:

Description (last modified by slelievre)

We implement a reasonably fast lexicographic iterator for modules over ZZ/nZZ. We integrate a minimum_weight method that could be used as an alternative to GAP in some part of sage.codings.

Setup 

sage: R = IntegerModRing(6)
sage: M = FreeModule(R, 4)
sage: U = M.span([M((1,1,0,2)), M((2,2,3,0))])

Before 

sage: timeit('for u in M: pass')
25 loops, best of 3: 9.11 ms per loop

sage: timeit('for u in U: pass')
625 loops, best of 3: 641 µs per loop

After 

sage: timeit('for u in M: pass')
625 loops, best of 3: 283 µs per loop

sage: timeit('for u in U: pass')
625 loops, best of 3: 41.5 µs per loop

Change History (6)

comment:1 Changed 4 years ago by vdelecroix

  • Dependencies set to u/vdelecroix/19345
  • Status changed from new to needs_review

comment:2 Changed 4 years ago by vdelecroix

  • Branch changed from #6452 to u/vdelecroix/19345
  • Commit set to 9d7a2cd4ac10a2dc9a633308d2a07bf547b29cc9
  • Dependencies changed from u/vdelecroix/19345 to #6452

New commits:

​708863fTrac 6452: free module over ZZ/nZZ and submodules
​ebb2092Trac 6452: adapt some tests to facade
​a5e3d23Trac 6452: fix a doctest
​acd707cTrac 6452: cleaner code + more doc
​ffbd6e8Trac 6452: simplification + more tests
​9d7a2cdTrac 19345: iterator for vector_modn_dense

comment:3 Changed 4 years ago by git

  • Commit changed from 9d7a2cd4ac10a2dc9a633308d2a07bf547b29cc9 to 5773c780ccd2b6084dff464da084df12ade378f0

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

​59ab945Trac 6452: free modules over ZZ/nZZ and submodules
​96ead16Trac 6452: fix a doctest
​5773c78Trac 19345: iterator for vector_modn_dense

comment:4 Changed 4 years ago by vdelecroix

rebased on #6452

comment:5 Changed 4 years ago by slelievre

  • Description modified (diff)

comment:6 Changed 4 years ago by vdelecroix

  • Status changed from needs_review to needs_work

Apparently not ready...

Note: See TracTickets for help on using tickets.