Opened 14 years ago
Closed 13 years ago
#174 closed enhancement (fixed)
[with patch; positive review] Implement a modular Hermite Normal Form algorithm
Reported by: | was | Owned by: | was |
---|---|---|---|
Priority: | major | Milestone: | sage-2.10.2 |
Component: | linear algebra | Keywords: | |
Cc: | burcin | Merged in: | |
Authors: | Reviewers: | ||
Report Upstream: | Work issues: | ||
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description
Hermite Normal form is the analogue of echelon form over the integers. It's crucial for almost all efficient computations with Z-modules (infinite abelian groups, finite abelian groups, lattices, modular abelian varieties via lattices, etc).
MAGMA is 50 times faster even for small examples, and asymptotically much faster than GAP, PARI, and NTL.
See this page http://magma.maths.usyd.edu.au/users/allan/mat/hermite.html which is mirrored here: http://sage.math.washington.edu/sage/misc/hermite.html
Attachments (5)
Change History (16)
Changed 14 years ago by
comment:1 Changed 14 years ago by
- Type changed from defect to enhancement
comment:2 Changed 14 years ago by
- Summary changed from all existing open source Hermite Normal Form implementations totally SUCK. to Implement a modular Hermite Normal Form algorithm
The attached paper by students describes the super-fast algorithm in MAGMA, and should be reasonably easy to implement in SAGE given what we now have.
comment:3 Changed 13 years ago by
- Milestone set to sage-wishlist
comment:4 Changed 13 years ago by
- Cc burcin added
Changed 13 years ago by
Changed 13 years ago by
Changed 13 years ago by
Changed 13 years ago by
comment:5 Changed 13 years ago by
I've put the final hnf.hg bundle here:
This is a bundle that I made by cleanly applying all my relevant patches to 2.10.2.alpha0, then do hg_sage.send(...).
The code is well documented, works well (very well tested with automated testing and doctstrings), but has a HUGE MEMORY LEAK somewhere:
sage: a = random_matrix(ZZ,200,x=0,y=9) sage: a._clear_cache(); e = a.hermite_form(proof=False); get_memory_usage() '234M+' sage: a._clear_cache(); e = a.hermite_form(proof=False); get_memory_usage() '239M+' sage: a._clear_cache(); e = a.hermite_form(proof=False); get_memory_usage() '244M+' sage: a._clear_cache(); e = a.hermite_form(proof=False); get_memory_usage() '249M+'
I suspect the memleak is in the optimized GMP code I added to matrix_integer_dense, and will find out soon...
comment:6 Changed 13 years ago by
- Milestone changed from sage-wishlist to sage-2.10.2
Here's a big leak:
sage: a = random_matrix(ZZ,200,x=0,y=9); e = a.hermite_form(proof=False); p = a.pivots() sage: get_memory_usage() '192M+' sage: w = e._add_row_and_maintain_echelon_form(random_matrix(ZZ,1,200), p) sage: get_memory_usage() '210M+'
comment:7 Changed 13 years ago by
- Summary changed from Implement a modular Hermite Normal Form algorithm to [with patch; needs review] Implement a modular Hermite Normal Form algorithm
ok, the file at http://sage.math.washington.edu/home/was/patches/hnf.hg has all the HNF stuff all working with no known issues.
finally!
comment:8 Changed 13 years ago by
Ok, running the final bundle under valgrind with
sage: a = random_matrix(ZZ,200,x=0,y=9) sage: a._clear_cache(); e = a.hermite_form(proof=False); get_memory_usage() sage: a._clear_cache(); e = a.hermite_form(proof=False); get_memory_usage() sage: a._clear_cache(); e = a.hermite_form(proof=False); get_memory_usage()
doesn't leak at all. Excellent. So positive review on memory leak issues.
Cheers,
Michael
comment:9 Changed 13 years ago by
FYI: The code has been merged, but still needs "official" review by a third party.
Cheers,
Michael
comment:10 Changed 13 years ago by
- Summary changed from [with patch; needs review] Implement a modular Hermite Normal Form algorithm to [with patch; positive review] Implement a modular Hermite Normal Form algorithm
The bundle has been extensively tested and I have verified via valgrind that it doesn't leak memory. While nobody external ever did a formal review I am giving this a positive review due to the excessive amount of testing. Feel free to do a formal review, but please open another ticket in case you come up with any issues.
Cheers,
Michael
comment:11 Changed 13 years ago by
- Resolution set to fixed
- Status changed from new to closed
Merged in Sage 2.10.2.alpha1
a student paper on fast HNF algorithms (and there are other papers out there)