is_invertible() too slow comparing to rank() over GF(2^k)

[a.simpl...@gmail.com]

I am running Sagemath 9.1 on macOS 10.15.17

but I think this issue is more about math.

Consider the following code

G = GL(2^8, GF(2^8))

A = G.random_element()

B = Matrix(A)

%time B.is_invertible()

C = Matrix(A)

%time C.nrows() == C.ncols() == C.rank()

The first timer returns 9s while the second timer returns 2ms.

I believe that this is because

• is_invertible() computes charpoly and read off the det.
  This is a detour when the base ring is a field.
• rank() uses m4rie, which uses asymptotically fast algorithm for rref.

Perhaps we can add one more if-brach in is_invertible() that exploits fast rref?

[dmo...@deductivepress.ca]

Speeding up by a factor of 4500 in a common use case sounds like a good idea. Please open a ticket. (Or do you want me to do it?)

[Travis Scrimshaw]

It would be good to implement this directly in the Matrix_gf2e_dense class rather than do anything in the generic implementation. However, you have to be a little careful for the case when it is a 0x0 matrix.

Best,

Travis

[Samuel Lelievre]

A ticket was opened for this:

- (re)implement is_invertible() for GF(2^e)
  https://trac.sagemath.org/ticket/31274