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:  sage6.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: 
Description (last modified by )
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("14506echelon_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("14506echelon_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)
Change History (14)
Changed 8 years ago by
comment:1 Changed 8 years ago by
 Description modified (diff)
comment:2 Changed 8 years ago by
 Cc rbeezer added
comment:3 Changed 8 years ago by
 Milestone changed from sage5.11 to sage5.12
comment:4 Changed 7 years ago by
 Milestone changed from sage6.1 to sage6.2
comment:5 Changed 7 years ago by
 Milestone changed from sage6.2 to sage6.3
comment:6 Changed 7 years ago by
 Milestone changed from sage6.3 to sage6.4
comment:7 Changed 7 years ago by
 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
comment:8 Changed 7 years ago by
 Commit changed from 5d90155e113f8ce3530568345d1b0415cf215cc6 to 5c6bf1ceabd0bc326b08d0c9dd0a74faab1f1d9a
Branch pushed to git repo; I updated commit sha1. New commits:
5c6bf1c  hardening doctest against random order of dict keys

comment:9 Changed 7 years ago by
Actually, maybe I should have added that self._clear_cache()
to the underscored methods?
comment:10 Changed 7 years ago by
 Commit changed from 5c6bf1ceabd0bc326b08d0c9dd0a74faab1f1d9a to ba950d58e47f53f0b9213b6096f1990adb437ab8
Branch pushed to git repo; I updated commit sha1. New commits:
ba950d5  moved self._clear_cache() into the underscored methods as someone may want to use them

comment:11 Changed 7 years ago by
 Reviewers set to Travis Scrimshaw
 Status changed from needs_review to positive_review
LGTM.
comment:12 Changed 7 years ago by
Thank you!!
comment:13 Changed 7 years ago by
 Branch changed from public/linalg/echelonize_clear_cache to ba950d58e47f53f0b9213b6096f1990adb437ab8
 Resolution set to fixed
 Status changed from positive_review to closed
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 lowlevel parts of the code).New commits:
clear cache upon echelonization of rational dense matrices