Matrix_mod2_dense._echelon_strassen gives false results sometimes

[malb]

Even though this method is probably not be used anyway, it is worth noticing that it gives False results from time to time:

sage: for i in range(10): 
....:   A = random_matrix(GF(2),20,20);
....:   B = A.echelon_form();
....:   A._clear_cache(); 
....:   A._echelon_strassen(cutoff=10); 
....:   A == B
False
True
True
False
True
False
True
True
True
False

sage: for i in range(10): 
....:   A = random_matrix(GF(7),20,20);
....:   B = A.echelon_form();
....:   A._clear_cache(); 
....:   A._echelon_strassen(cutoff=10); 
....:   A == B
True
True
True
False
True
True
True
True
True
True

Component: linear algebra

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

[williamstein]

comment:2

I tested 1000 STrassen echelons over QQ with no problems. I tested 100 over GF(389), i.e., a fairly big
prime, and even there it fails. It must be that either:
(1) matrix windows are buggy mod p, or
(2) the echelon algorithm itself is wrong mod p.

I just tested with generic windows, and the algorithm is buggy, not the implementation of windows.

---

I have modified

William

[robertwb]

comment:3

I fixed the algorithm, it was forgetting to clear some pivots in some cases on full rank (where it was jumping to the end 'cause it knew it everything but the diagonal was 0's)

I have tested this on 1000's of matrices of varying sizes and primes.

[williamstein]

comment:4

Attachment: strassen-fix.patch.gz