Slow hnf for integer matrices

[tornaria]

Is there an existing issue for this?

• I have searched the existing issues for a bug report that matches the one I want to file, without success.

Did you read the documentation and troubleshoot guide?

• I have read the documentation and troubleshoot guide

Environment

- **OS**: void linux
- **Sage Version**: 9.8

Steps To Reproduce

sage: import sage.matrix.matrix_integer_dense_hnf as hnf
sage: hnf.benchmark_hnf([50,100],32)
('sage', 50, 32, 1.9906130000000104),
('sage', 100, 32, 19.642045000000003),

Expected Behavior

hnf is fast

Actual Behavior

hnf is slow

Additional Information

Compare with

sage: hnf.benchmark_magma_hnf([50,100],32)
('magma', 50, 32, 0.02),
('magma', 100, 32, 0.06),

This is taken verbatim from the doctest of sage.matrix.matrix_integer_dense_hnf.benchmark_hnf which thus takes 20+ seconds (on a fast box) which is too long even for "long time" IMO. I'm not sure what this doctest is actually testing here. I want to believe that this used to be much faster, if so this is a speed regression.

I'll make a PR to change the doctest so it doesn't take that much time, while keeping this issue open so the speed regression is not lost.

[tornaria]

Note this:

sage: hnf.benchmark_hnf(range(20,30),32)
('sage', 20, 32, 0.04139000000000692),
('sage', 21, 32, 0.03343599999999469),
('sage', 22, 32, 0.0327039999999954),
('sage', 23, 32, 0.03619700000001558),
('sage', 24, 32, 0.03216000000000463),
('sage', 25, 32, 0.030913999999995667),
('sage', 26, 32, 0.03236599999999612),
('sage', 27, 32, 0.31043500000001245),
('sage', 28, 32, 0.3401110000000074),
('sage', 29, 32, 0.3684499999999957),

Something changes starting at dimension 27.

[tornaria]

Weird:

sage: a = random_matrix(ZZ, 100, x=-2**30, y=2**30)
sage: %time h,_ = hnf.hnf(a, proof=True)
CPU times: user 8.83 s, sys: 7.2 ms, total: 8.83 s
Wall time: 8.86 s
sage: %time h,_ = hnf.hnf(a, proof=False)
CPU times: user 21.3 s, sys: 20.3 ms, total: 21.4 s
Wall time: 21.5 s

[tornaria]

Once this issue is fixed, consider reverting the commit in PR #35162.

[alexjbest]

While this is certainly weird I don't think the code in this file is really used by Sage anymore (or at least I hope not!). Sage should be calling external libraries for the hnf, so speeding up Sage native code (which seems mostly historical) shouldn't be a priority vs ensuring that this code just isn't used.

[mezzarobba]

Something changes starting at dimension 27.

src/sage/matrix/matrix_rational_dense.pyx:1572

        if algorithm is None:
            if self._nrows <= 25 or self._ncols <= 25:
                algorithm = 'flint'
            else:
                algorithm = 'multimodular'

[mezzarobba]

It looks like this logic is there do deal with weaknesses of old versions of flint (see #22970, #23026, flintlib/flint#335) and flint should be consistently faster now. @videlec, how hard would it be to dig up the benchmarks you ran back then?

[videlec]

I have no idea where these are (ie on which computer). If I dig it, I would like such benchmarks to be part of regression testing :-)