Opened 15 years ago

Closed 14 years ago

# [with patch; positive review] Implement a modular Hermite Normal Form algorithm

Reported by: Owned by: was was major sage-2.10.2 linear algebra burcin

### 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.

### Changed 15 years ago by was

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

### comment:1 Changed 15 years ago by was

• Type changed from defect to enhancement

### comment:2 Changed 15 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 14 years ago by mabshoff

• Milestone set to sage-wishlist

### comment:5 Changed 14 years ago by was

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 14 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: get_memory_usage()
'210M+'
```

### comment:7 Changed 14 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 14 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 14 years ago by mabshoff

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

Cheers,

Michael

### comment:10 Changed 14 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 14 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.