Opened 8 years ago

Closed 7 years ago

#14506 closed defect (fixed)

Echelonize leads to wrong multiplication

Reported by: mraum Owned by: jason, was
Priority: critical Milestone: sage-6.4
Component: linear algebra Keywords: linear algebra, echelonize, cache, mutation
Cc: rbeezer, was Merged in:
Authors: Darij Grinberg Reviewers: Travis Scrimshaw
Report Upstream: N/A Work issues:
Branch: ba950d5 (Commits, GitHub, GitLab) Commit: ba950d58e47f53f0b9213b6096f1990adb437ab8
Dependencies: Stopgaps:

Status badges

Description (last modified by mraum)

Load the two matrices that I have attached and run the following code to see that the second row of the second matrix is not updated correctly. 

sage: (a, b) = load("14506-echelon_matrices.sobj")
sage: b.echelonize()
sage: a.transpose() * b
[                        0                         1                        24                       324                      3200                     25650                    176256                   1073720                   5930496                  30178575                 143184000                 639249300                2705114880               10916609264               42224364768              157237849404              565928955336             1975748911989             6712360813296            22258958382384            72248546142576           230126686576596           720999820523680          2226607404115308          6790183423299432         20478994820181329         61157329008540264        181004375431019448        531238661914490832       1546662807633726456       4467428806660680816      12801302700703268916      36384312930487005696     102550540165931773881     286559332427090336280     793661555641170811488    2178228257908531278912    5922967390221653096898   15954542776854757733856   42569726135569471713636  112504969550911913199256  294509000583368778593058  763659353026853825886576 1961586226496587115127844 4991900581029733007609328]
sage: (b.transpose() * a).transpose()
[0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]

The following works correctly. To me this indicates that the internal representation is somehow not updated correctly. 

sage: (a, b) = load("14506-echelon_matrices.sobj")
sage: b.echelonize()
sage: b = copy(b)           
sage: a.transpose() * b
[0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]

I make this a critical ticket. But the actual mistake seems so dangerous and it results from a common operation, so that it is a candidate for a blocker.

Attachments (1)

14506-echelon_matrices.sobj​ (6.3 KB) - added by mraum 8 years ago.

Download all attachments as: .zip

Change History (14)

Changed 8 years ago by mraum

comment:1 Changed 8 years ago by mraum

  • Description modified (diff)

comment:2 Changed 8 years ago by rbeezer

  • Cc rbeezer added

comment:3 Changed 8 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:4 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:5 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:6 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:7 Changed 7 years ago by darij

  • Authors set to Darij Grinberg
  • Branch set to public/linalg/echelonize_clear_cache
  • Cc was added
  • Commit set to 5d90155e113f8ce3530568345d1b0415cf215cc6
  • Keywords linear algebra echelonize cache mutation added
  • Status changed from new to needs_review

The mistake is in the fact that echelonizing a rational matrix in place does not clear the clear_denom value of its cache. Fixed. Experiments seem to suggest that other matrix types don't suffer from this bug, but I'd rather see someone doublecheck this (I don't understand the really low-level parts of the code).

New commits:

​5d90155clear cache upon echelonization of rational dense matrices

comment:8 Changed 7 years ago by git

  • Commit changed from 5d90155e113f8ce3530568345d1b0415cf215cc6 to 5c6bf1ceabd0bc326b08d0c9dd0a74faab1f1d9a

Branch pushed to git repo; I updated commit sha1. New commits:

​5c6bf1chardening doctest against random order of dict keys

comment:9 Changed 7 years ago by darij

Actually, maybe I should have added that self._clear_cache() to the underscored methods?

comment:10 Changed 7 years ago by git

  • Commit changed from 5c6bf1ceabd0bc326b08d0c9dd0a74faab1f1d9a to ba950d58e47f53f0b9213b6096f1990adb437ab8

Branch pushed to git repo; I updated commit sha1. New commits:

​ba950d5moved self._clear_cache() into the underscored methods as someone may want to use them

comment:11 Changed 7 years ago by tscrim

  • Reviewers set to Travis Scrimshaw
  • Status changed from needs_review to positive_review

LGTM.

comment:12 Changed 7 years ago by darij

Thank you!!

comment:13 Changed 7 years ago by vbraun

  • Branch changed from public/linalg/echelonize_clear_cache to ba950d58e47f53f0b9213b6096f1990adb437ab8
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.