Opened 7 years ago

Last modified 7 years ago

#19345 needs_work enhancement

Fast lexicographic iterator for module over ZZ/nZZ

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

Status badges

Description (last modified by Samuel Lelièvre)

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 7 years ago by Vincent Delecroix

Dependencies: → u/vdelecroix/19345
Status: new → needs_review

comment:2 Changed 7 years ago by Vincent Delecroix

Branch: #6452 → u/vdelecroix/19345
Commit: → 9d7a2cd4ac10a2dc9a633308d2a07bf547b29cc9
Dependencies: u/vdelecroix/19345 → #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 7 years ago by git

Commit: 9d7a2cd4ac10a2dc9a633308d2a07bf547b29cc9 → 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 7 years ago by Vincent Delecroix

rebased on #6452

comment:5 Changed 7 years ago by Samuel Lelièvre

Description: modified (diff)

comment:6 Changed 7 years ago by Vincent Delecroix

Status: needs_review → needs_work

Apparently not ready...

Note: See TracTickets for help on using tickets.