Opened 10 years ago
Last modified 9 years ago
#10795 closed defect
Fix and upgrade double dense matrix QR decomposition — at Version 20
Reported by: | rbeezer | Owned by: | jason, was |
---|---|---|---|
Priority: | minor | Milestone: | sage-5.2 |
Component: | linear algebra | Keywords: | sd40.5 |
Cc: | jason, ddrake | Merged in: | |
Authors: | Rob Beezer | Reviewers: | Martin Raum |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | Stopgaps: |
Description (last modified by )
The Q matrix of a QR decomposition should be unitary, hence invertible. For zero-column trivial cases, this is broken.
sage: A = zero_matrix(CDF, 5, 0) sage: Q, R = A.QR() sage: Q [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]
Besides a bugfix this patch will upgrade the documentation to make it clear how this routine works over the complex numbers. In particular, SciPy
routines are using a Hermitian inner product - documentation upgrade will reflect that.
Apply:
Change History (21)
comment:1 Changed 10 years ago by
- Status changed from new to needs_review
comment:2 Changed 10 years ago by
- Reviewers set to Martin Raum
- Status changed from needs_review to positive_review
Everything is OK with this patch.
comment:3 Changed 10 years ago by
- Milestone changed from sage-4.7.1 to sage-4.7.2
comment:4 Changed 10 years ago by
- Merged in set to sage-4.7.2.alpha2
- Resolution set to fixed
- Status changed from positive_review to closed
comment:5 Changed 10 years ago by
- Merged in sage-4.7.2.alpha2 deleted
- Resolution fixed deleted
- Status changed from closed to new
On various systems, there are doctest failures:
hawk (OpenSolaris? 06/2009 i86pc Xeon W3580):
********************************************************************** File "/export/home/buildbot/build/sage/hawk-1/hawk_full/build/sage-4.7.2.alpha2/devel/sage-main/sage/matrix/matrix_double_dense.pyx", line 1766: sage: Q Expected: [ -0.359210604054 0.569326179705 0.368048420509 0.641385845805] [ 0.179605302027 -0.144590775798 0.925041158846 -0.301884576418] [ 0.179605302027 -0.704880032016 0.0774617736597 0.681825307224] [ 0.898026510134 0.397624633445 -0.0532812182975 0.180566192161] Got: [-0.359210604054 0.569326179705 0.409076682956 0.616028985113] [ 0.179605302027 -0.144590775798 -0.683704756325 0.69237507842] [ 0.179605302027 -0.704880032016 0.575201135981 0.374205463771] [ 0.898026510134 0.397624633445 0.185331397251 0.0330954856071] ********************************************************************** File "/export/home/buildbot/build/sage/hawk-1/hawk_full/build/sage-4.7.2.alpha2/devel/sage-main/sage/matrix/matrix_double_dense.pyx", line 1771: sage: R Expected: [ -5.56776436283 2.6940795304 -2.6940795304] [ 0 -3.56958477752 3.56958477752] [ 0 0 -9.93013661299e-16] [ 0 0 0] Got: [ -5.56776436283 2.6940795304 -2.6940795304] [ 0 -3.56958477752 3.56958477752] [ 0 0 -4.4408920985e-16] [ 0 0 0] **********************************************************************
bsd (OS X 10.8.0 x86_64) 64-bit:
********************************************************************** File "/Users/buildbot/build/sage/bsd-1/bsd_64_full/build/sage-4.7.2.alpha2/devel/sage-main/sage/matrix/matrix_double_dense.pyx", line 1766: sage: Q Expected: [ -0.359210604054 0.569326179705 0.368048420509 0.641385845805] [ 0.179605302027 -0.144590775798 0.925041158846 -0.301884576418] [ 0.179605302027 -0.704880032016 0.0774617736597 0.681825307224] [ 0.898026510134 0.397624633445 -0.0532812182975 0.180566192161] Got: [ -0.359210604054 0.569326179705 0.146337376237 0.724859169325] [ 0.179605302027 -0.144590775798 0.973035382602 0.00613084354877] [ 0.179605302027 -0.704880032016 -0.142125402809 0.671331844787] [ 0.898026510134 0.397624633445 -0.107647045464 0.154451130063] ********************************************************************** File "/Users/buildbot/build/sage/bsd-1/bsd_64_full/build/sage-4.7.2.alpha2/devel/sage-main/sage/matrix/matrix_double_dense.pyx", line 1771: sage: R Expected: [ -5.56776436283 2.6940795304 -2.6940795304] [ 0 -3.56958477752 3.56958477752] [ 0 0 -9.93013661299e-16] [ 0 0 0] Got: [ -5.56776436283 2.6940795304 -2.6940795304] [ 0 -3.56958477752 3.56958477752] [ 0 0 6.28036983474e-16] [ 0 0 0] **********************************************************************
cleo (RHEL 5.3 ia64 Itanium 2):
********************************************************************** File "/home/buildbot/build/sage/cleo-1/cleo_full/build/sage-4.7.2.alpha2/devel/sage-main/sage/matrix/matrix_double_dense.pyx", line 1766: sage: Q Expected: [ -0.359210604054 0.569326179705 0.368048420509 0.641385845805] [ 0.179605302027 -0.144590775798 0.925041158846 -0.301884576418] [ 0.179605302027 -0.704880032016 0.0774617736597 0.681825307224] [ 0.898026510134 0.397624633445 -0.0532812182975 0.180566192161] Got: [ -0.359210604054 0.569326179705 0.146859067236 0.724753652911] [ 0.179605302027 -0.144590775798 0.973039543327 0.00543048428303] [ 0.179605302027 -0.704880032016 -0.141642164231 0.671433967908] [ 0.898026510134 0.397624633445 -0.107535848925 0.154528570726] ********************************************************************** File "/home/buildbot/build/sage/cleo-1/cleo_full/build/sage-4.7.2.alpha2/devel/sage-main/sage/matrix/matrix_double_dense.pyx", line 1771: sage: R Expected: [ -5.56776436283 2.6940795304 -2.6940795304] [ 0 -3.56958477752 3.56958477752] [ 0 0 -9.93013661299e-16] [ 0 0 0] Got: [ -5.56776436283 2.6940795304 -2.6940795304] [ 0 -3.56958477752 3.56958477752] [ 0 0 9.81879219451e-16] [ 0 0 0] **********************************************************************
comment:6 Changed 10 years ago by
- Status changed from new to needs_review
It seems that this patch causes failures in a non-reproducible way. Is there some randomness in the algorithm? For example, I just got this failure on sage.math.washington.edu (a machine on which I remember the test succeeding):
sage -t -long -force_lib devel/sage/sage/matrix/matrix_double_dense.pyx ********************************************************************** File "/mnt/usb1/scratch/buildbot/sage/sage-1/sage_binary/build/sage-4.7.2.alpha2/devel/sage-main/sage/matrix/matrix_double_dense.pyx", line 1766: sage: Q Expected: [ -0.359210604054 0.569326179705 0.368048420509 0.641385845805] [ 0.179605302027 -0.144590775798 0.925041158846 -0.301884576418] [ 0.179605302027 -0.704880032016 0.0774617736597 0.681825307224] [ 0.898026510134 0.397624633445 -0.0532812182975 0.180566192161] Got: [-0.359210604054 0.569326179705 0.616028985113 0.409076682956] [ 0.179605302027 -0.144590775798 0.69237507842 -0.683704756325] [ 0.179605302027 -0.704880032016 0.374205463771 0.575201135981] [ 0.898026510134 0.397624633445 0.0330954856071 0.185331397251] ********************************************************************** File "/mnt/usb1/scratch/buildbot/sage/sage-1/sage_binary/build/sage-4.7.2.alpha2/devel/sage-main/sage/matrix/matrix_double_dense.pyx", line 1771: sage: R Expected: [ -5.56776436283 2.6940795304 -2.6940795304] [ 0 -3.56958477752 3.56958477752] [ 0 0 -9.93013661299e-16] [ 0 0 0] Got: [ -5.56776436283 2.6940795304 -2.6940795304] [ 0 -3.56958477752 3.56958477752] [ 0 0 -4.4408920985e-16] [ 0 0 0] **********************************************************************
comment:7 Changed 10 years ago by
- Status changed from needs_review to needs_work
comment:8 Changed 10 years ago by
- Description modified (diff)
- Keywords beginner removed
- Status changed from needs_work to needs_review
"numerical" patch applies accumulated techniques for these numerical computations and should address the doctest failures.
comment:9 Changed 10 years ago by
- Cc jason added
Same question on here as on #10791 -- is it appropriate to set this back to positive review (assuming the tests still pass on Rob's machine)?
comment:10 Changed 10 years ago by
Applies and passes all tests on 4.8.alpha3.
comment:11 Changed 10 years ago by
- Status changed from needs_review to positive_review
Based on jdmeyer's response to my question on #10791: the fixing patch looks reasonable and Rob tested it. I'd test it as well, except I'm currently building python 2.7 and testing it.
comment:12 Changed 10 years ago by
Sorry, I meant jdemeyer's response...
comment:13 Changed 10 years ago by
- Merged in set to sage-4.8.alpha5
- Resolution set to fixed
- Status changed from positive_review to closed
comment:14 Changed 10 years ago by
- Merged in sage-4.8.alpha5 deleted
- Resolution fixed deleted
- Status changed from closed to new
This sometimes gives a doctest failure:
sage -t -long -force_lib devel/sage/sage/matrix/matrix_double_dense.pyx ********************************************************************** File "/mnt/usb1/scratch/buildbot/sage/sage-1/sage_binary/build/sage-4.8.alpha5/devel/sage-main/sage/matrix/matrix_double_dense.pyx", line 2243: sage: Q.round(6).zero_at(10^-6) Expected: [-0.359211 0.569326 0.368048 0.641386] [ 0.179605 -0.144591 0.925041 -0.301885] [ 0.179605 -0.70488 0.077462 0.681825] [ 0.898027 0.397625 -0.053281 0.180566] Got: [-0.359211 0.569326 -0.631992 -0.383955] [ 0.179605 -0.144591 -0.6643 0.711014] [ 0.179605 -0.70488 -0.39705 -0.559676] [ 0.898027 0.397625 -0.040527 -0.183849] **********************************************************************
It's not clear why it happens. Because on the same machine I have one Sage build where it works, one where it doesn't with the exact same source, but different gcc version.
Does this code use any external libraries (ATLAS comes to mind)?
comment:15 Changed 10 years ago by
- Status changed from new to needs_review
On Fedora 15-64 (flavius):
sage -t -long -force_lib devel/sage/sage/matrix/matrix_double_dense.pyx ********************************************************************** File "/home/buildbot/build/sage/flavius-1/flavius_full/build/sage-4.8.alpha5/devel/sage-main/sage/matrix/matrix_double_dense.pyx", line 2243: sage: Q.round(6).zero_at(10^-6) Expected: [-0.359211 0.569326 0.368048 0.641386] [ 0.179605 -0.144591 0.925041 -0.301885] [ 0.179605 -0.70488 0.077462 0.681825] [ 0.898027 0.397625 -0.053281 0.180566] Got: [-0.359211 0.569326 0.616029 0.409077] [ 0.179605 -0.144591 0.692375 -0.683705] [ 0.179605 -0.70488 0.374205 0.575201] [ 0.898027 0.397625 0.033095 0.185331] **********************************************************************
comment:16 Changed 10 years ago by
- Status changed from needs_review to needs_work
comment:17 Changed 10 years ago by
Thanks, Jeroen. Sorry for the delay in getting back to this one.
Yes, this uses SciPy, which in turn will use ATLAS. It seems a 2-dimensional eigenspace is being returned with different basis vectors.
This is mostly a documentation patch, so I think it would be best to make the tests more functional - checking that returned matrices have the desired properties - and less about the actual entries of the matrices. I'll put that on my list.
Rob
comment:18 Changed 10 years ago by
* bump *
Changed 9 years ago by
comment:19 Changed 9 years ago by
- Cc ddrake added
- Keywords sd40.5 added
- Status changed from needs_work to needs_review
- Jeroen - thanks for the bump.
- Needed a rebase, so did that and also tidied up a few things. Almost entirely documentation, with one code change. Will need a new review since the documentation has changed.
- Doctest failures. Seems different platforms give different bases for the dimension 2 left kernel of the matrix. No harm in just removing it and explaining the situation, along with definitive evidence that the result behaves as expected.
comment:20 Changed 9 years ago by
- Description modified (diff)
Just one change to the code, to return an identity matrix in a trivial case. Everything else is documentation. Unfortunately, this file is not included in the documentation (yet). You can check that it builds without warnings, then look at it in the notebook to verify the contents and appearance.