search

sagemath / sage

Main repository of SageMath
https://www.sagemath.org
Other
1.33k stars 452 forks source link

(re)implement is_invertible() for GF(2^e) #31274

Open Symbol1 opened 3 years ago

Symbol1 commented 3 years ago

Hi, newbie here. This ticket is created per suggestion in the following conversion: https://groups.google.com/g/sage-devel/c/hcYi4jxIN8c/m/XdHVL3DGAAAJ

In the conversion, I observe that the speed of Matrix(GL(2^8, GF(2^8)).random_element()).is_invertible() is too slow comparing to a rather straightforward strategy --- checking the rank against the matrix size A.nrows() == A.ncols() == A.rank().

Travis then suggest to implement is_invertible() in the class Matrix_gf2e_dense. I also want to add that, at least over finite fields, the rref approach feels to be faster, because

  1. there are asymptotically faster algorithm for rref; and
  2. False can be returned as early as a pivot is found missing.

Component: linear algebra

Issue created by migration from https://trac.sagemath.org/ticket/31274

mkoeppe commented 3 years ago
comment:1

Sage development has entered the release candidate phase for 9.3. Setting a new milestone for this ticket based on a cursory review of ticket status, priority, and last modification date.