Opened 23 months ago

Last modified 3 months ago

#31274 new enhancement

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

Reported by: gh-Symbol1 Owned by:
Priority: major Milestone: sage-9.8
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 (5)

comment:1 Changed 20 months ago by Matthias Köppe

Milestone: sage-9.3sage-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 16 months ago by Matthias Köppe

Milestone: sage-9.4sage-9.5

comment:3 Changed 11 months ago by Matthias Köppe

Milestone: sage-9.5sage-9.6

comment:4 Changed 8 months ago by Matthias Köppe

Milestone: sage-9.6sage-9.7

comment:5 Changed 3 months ago by Matthias Köppe

Milestone: sage-9.7sage-9.8
Note: See TracTickets for help on using tickets.