Opened 14 years ago

Closed 14 years ago

#769 closed defect (fixed)

Matrix_mod2_dense._echelon_strassen gives false results sometimes

Reported by: malb Owned by: was
Priority: critical Milestone: sage-2.8.6
Component: linear algebra Keywords:
Cc: Merged in:
Authors: Reviewers:
Report Upstream: Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description

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

Attachments (1)

strassen-fix.patch (3.9 KB) - added by robertwb 14 years ago.

Download all attachments as: .zip

Change History (5)

comment:1 Changed 14 years ago by mabshoff

  • Summary changed from Matrix_mod2_dense._echelon_strassen gives fals results sometimes to Matrix_mod2_dense._echelon_strassen gives false results sometimes

comment:2 Changed 14 years ago by was

  • Resolution set to fixed
  • Status changed from new to closed

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

comment:3 Changed 14 years ago by robertwb

  • Priority changed from minor to critical
  • Resolution fixed deleted
  • Status changed from closed to reopened

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.

Changed 14 years ago by robertwb

comment:4 Changed 14 years ago by was

  • Component changed from algebraic geometry to linear algebra
  • Resolution set to fixed
  • Status changed from reopened to closed
Note: See TracTickets for help on using tickets.