Suboptimal choice of algorithm by Matrix(QQ).solve_right()

[user202729]

Steps To Reproduce

set_random_seed(1)
n=26
entry_size = 100
A = matrix.block([
        [matrix([[randint(0, 2^entry_size) for col in range(n)] for row in range(n*2)])],
        ])
x = vector([randint(0, 2^entry_size) for i in range(n)])
b = A*x

%time x1 = A.solve_right(b)
# more than a second

%time x1 = A._solve_right_general(b.column(), check=True).column(0)
# instant

Expected Behavior

both are fast

Actual Behavior

Additional Information

No response

Environment

• OS: Linux
• Sage Version: latest develop

Checklist

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

[user202729]

set_verbose(5) gives some interesting information.

• first, somehow the cached pivot value is not reused in the first case.
• second, there's a bunch of echelon multi-modular possibly not converging in the slow case, but not the fast case.

[user202729]

Looks like the cause is the fact that the ring is changed to QQ somehow.

Which boils down to…

A = matrix(ZZ, [[randint(0, 2^entry_size) for col in range(n*2)] for row in range(n)])
A.pivots()  # fast

A = matrix(QQ, [[randint(0, 2^entry_size) for col in range(n*2)] for row in range(n)])
A.pivots()  # slow

In matrix_rational_dense.pyx:

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

Introduced by #22970 . Looks like multimodular clears denominator then runs multimodular algorithm.

[user202729]

Looks like the problem is that the initial guess for the height is way too low.

sage: set_random_seed(1)
sage: num_col = 60
sage: num_row = 30
sage: entry_size = 100
sage: A = matrix(QQ, [[randint(1, 2^entry_size) for col in range(num_col)] for row in range(num_row)])
sage: A.height()
1267283060447949307261369136578
sage: %time A.echelonize(algorithm="multimodular", height_guess=10^2000)
CPU times: user 422 ms, sys: 55 μs, total: 422 ms
Wall time: 425 ms
sage: RR(A.height())
1.92386909048248e904