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)

HermiteNormalForm_1.tex (5.0 KB) - added by was 14 years ago.
a student paper on fast HNF algorithms (and there are other papers out there)
trac-174.patch (6.2 KB) - added by was 13 years ago.
hnfrow.sage (7.2 KB) - added by was 13 years ago.
trac-174-part2.patch (1.3 KB) - added by was 13 years ago.
trac-174-part3.patch (1.8 KB) - added by was 13 years ago.

Download all attachments as: .zip

Change History (16)

Changed 14 years ago by was

a student paper on fast HNF algorithms (and there are other papers out there)

comment:1 Changed 14 years ago by was

  • Type changed from defect to enhancement

comment:2 Changed 14 years ago by was

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

  • Milestone set to sage-wishlist

comment:4 Changed 13 years ago by burcin

  • Cc burcin added

Changed 13 years ago by was

Changed 13 years ago by was

Changed 13 years ago by was

Changed 13 years ago by was

comment:5 Changed 13 years ago by was

I've put the final hnf.hg bundle here:

http://sage.math.washington.edu/home/was/patches/hnf.hg

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 was

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

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

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 mabshoff

FYI: The code has been merged, but still needs "official" review by a third party.

Cheers,

Michael

comment:10 Changed 13 years ago by mabshoff

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

  • Resolution set to fixed
  • Status changed from new to closed

Merged in Sage 2.10.2.alpha1

Note: See TracTickets for help on using tickets.