Opened 12 months ago

Last modified 6 weeks ago

#31274 new enhancement

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

Reported by: gh-Symbol1 Owned by:
Priority: major Milestone: sage-9.6
Component: linear algebra Keywords:
Cc: Merged in:
Authors: Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description

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.

Change History (3)

comment:1 Changed 10 months ago by mkoeppe

  • Milestone changed from sage-9.3 to sage-9.4

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.

comment:2 Changed 6 months ago by mkoeppe

  • Milestone changed from sage-9.4 to sage-9.5

comment:3 Changed 6 weeks ago by mkoeppe

  • Milestone changed from sage-9.5 to sage-9.6
Note: See TracTickets for help on using tickets.