Computing echelon form of smaller matrix takes longer than larger matrix? #2129
Description
Use flint's algorithm through SageMath's interface (which uses fmpq_mat_rref under the hood).
sage: entry_size = 10000
....: num_col = 20
....: num_row = 20
....: A = matrix(QQ, [[randint(1, 2^entry_size) for col in range(num_col)] for row in range(num_row)
....: ])
....: t = walltime()
....: A.echelonize(algorithm="flint")
....: t = walltime(t)
....: t
1.3925843238830566
sage: entry_size = 10000
....: num_col = 40
....: num_row = 40
....: A = matrix(QQ, [[randint(1, 2^entry_size) for col in range(num_col)] for row in range(num_row)
....: ])
....: t = walltime()
....: A.echelonize(algorithm="flint")
....: t = walltime(t)
....: t
0.022356271743774414
Why is it that in the first case with a 20 × 20 matrix it takes >1 second while in the second case it is instant?
In both cases the matrix is invertible, thus the echelon form is identity.
(larger context: sagemath/sage#39197 , if flint is the fastest in all cases it would be easiest to just switch to flint, but this is not the case at the moment)