Fix and upgrade double dense matrix QR decomposition #10795

rbeezer · 2011-02-17T22:24:40Z

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:

CC: @jasongrout @dandrake

Component: linear algebra

Keywords: sd40.5

Author: Rob Beezer

Reviewer: Martin Raum, Dan Drake

Merged: sage-5.2.beta1

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

The text was updated successfully, but these errors were encountered:

rbeezer · 2011-02-17T23:03:42Z

Author: Rob Beezer

rbeezer · 2011-02-17T23:03:42Z

comment:1

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.

sagetrac-mraum · 2011-08-06T16:36:30Z

Reviewer: Martin Raum

sagetrac-mraum · 2011-08-06T16:36:30Z

comment:2

Everything is OK with this patch.

jdemeyer · 2011-08-18T22:02:50Z

Merged: sage-4.7.2.alpha2

jdemeyer · 2011-08-24T08:22:17Z

Changed merged from sage-4.7.2.alpha2 to none

jdemeyer · 2011-08-24T08:22:17Z

comment:5

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]
**********************************************************************

jdemeyer · 2011-08-24T21:55:45Z

comment:6

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]
**********************************************************************

rbeezer · 2011-09-19T03:23:36Z

comment:8

"numerical" patch applies accumulated techniques for these numerical computations and should address the doctest failures.

rbeezer · 2012-05-28T02:43:58Z

Changed keywords from none to sd40.5

sagetrac-mraum · 2012-05-28T08:24:21Z

comment:21

This looks good, and I think it is reasonable to use the Q as it is.

Could you please go over the patch and correct the Q and Q to Q (and I think in some places R is missing the quotes also). Then I can give this a positive review.

rbeezer · 2012-05-28T16:14:26Z

Attachment: trac_10795-QR-decomposition-formatting.patch.gz

rbeezer · 2012-05-28T16:20:51Z

comment:22

Dear Martin,

Thanks for participating remotely in Sage Days 40.5. ;-)

"formatting" patch is an add-on, so you can see the changes. I did the "OUTPUT" section entirely with math quotes, other than the result objects. The rest is in code quotes.

Updated the output description, which needed work. Added some left kernel explanation for Dan Drake, who was also looking at this here at SD 40.5.

Thanks again,
Rob

dandrake · 2012-05-28T17:02:29Z

Changed reviewer from Martin Raum to Martin Raum, Dan Drake

dandrake · 2012-05-28T17:02:29Z

comment:23

This is a big improvement over what we previously had. Positive review.

Just for the patchbot: apply
trac_10795-QR-decomposition-double-dense-v2.patch
trac_10795-QR-decomposition-formatting.patch

jdemeyer · 2012-06-18T10:22:26Z

Merged: sage-5.1.beta5

jdemeyer · 2012-06-20T06:50:06Z

comment:25

As reported on sage-devel, this gives doctest failures on OS X Lion, see #13140.

jdemeyer · 2012-06-26T06:50:15Z

Changed merged from sage-5.1.beta5 to none

jdemeyer · 2012-06-26T06:50:15Z

comment:26

Unmerging due to #13140.

jhpalmieri · 2012-07-11T13:53:57Z

comment:27

Should this be marked "positive review" again, since #13140 is ready?

dandrake · 2012-07-11T14:26:12Z

comment:28

Replying to @jhpalmieri:

Should this be marked "positive review" again, since #13140 is ready?

I think so. If that was the only reason this got unmerged, and that ticket is now fixed, this should again be ready.

jdemeyer · 2012-07-13T11:43:27Z

Merged: sage-5.2.beta1

rbeezer mannequin added this to the sage-4.7.1 milestone Feb 17, 2011

rbeezer mannequin added c: linear algebra labels Feb 17, 2011

rbeezer mannequin assigned jasongrout and williamstein Feb 17, 2011

rbeezer mannequin added the s: needs review label Feb 17, 2011

sagetrac-mraum mannequin added s: positive review and removed s: needs review labels Aug 6, 2011

jdemeyer modified the milestones: sage-4.7.1, sage-4.7.2 Aug 11, 2011

jdemeyer removed the s: positive review label Aug 18, 2011

jdemeyer closed this as completed Aug 18, 2011

jdemeyer reopened this Aug 24, 2011

jdemeyer added s: needs review and removed s: needs review labels Aug 24, 2011

This comment has been minimized.

Sign in to view

rbeezer mannequin removed good first issue labels Sep 19, 2011

rbeezer mannequin added s: needs review and removed s: needs work labels May 28, 2012

This comment has been minimized.

Sign in to view

dandrake added s: positive review and removed s: needs review labels May 28, 2012

jdemeyer removed the s: positive review label Jun 18, 2012

jdemeyer closed this as completed Jun 18, 2012

jdemeyer modified the milestones: sage-5.1, sage-5.2 Jun 26, 2012

jdemeyer reopened this Jun 26, 2012

dandrake added s: needs review and removed s: needs review labels Jul 11, 2012

jdemeyer removed the s: positive review label Jul 13, 2012

jdemeyer closed this as completed Jul 13, 2012

jdemeyer mentioned this issue Jul 13, 2012

OS X Lion doctest failures for double dense QR decomposition #13140

Closed

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Fix and upgrade double dense matrix QR decomposition #10795

Fix and upgrade double dense matrix QR decomposition #10795

rbeezer mannequin commented Feb 17, 2011

rbeezer mannequin commented Feb 17, 2011

rbeezer mannequin commented Feb 17, 2011

sagetrac-mraum mannequin commented Aug 6, 2011

sagetrac-mraum mannequin commented Aug 6, 2011

jdemeyer commented Aug 18, 2011

jdemeyer commented Aug 24, 2011

jdemeyer commented Aug 24, 2011

jdemeyer commented Aug 24, 2011

This comment has been minimized.

rbeezer mannequin commented Sep 19, 2011

rbeezer mannequin commented May 28, 2012

This comment has been minimized.

sagetrac-mraum mannequin commented May 28, 2012

rbeezer mannequin commented May 28, 2012

rbeezer mannequin commented May 28, 2012

This comment has been minimized.

dandrake commented May 28, 2012

dandrake commented May 28, 2012

jdemeyer commented Jun 18, 2012

jdemeyer commented Jun 20, 2012

jdemeyer commented Jun 26, 2012

jdemeyer commented Jun 26, 2012

jhpalmieri commented Jul 11, 2012

dandrake commented Jul 11, 2012

jdemeyer commented Jul 13, 2012

Fix and upgrade double dense matrix QR decomposition #10795

Fix and upgrade double dense matrix QR decomposition #10795

Comments

rbeezer mannequin commented Feb 17, 2011

rbeezer mannequin commented Feb 17, 2011

rbeezer mannequin commented Feb 17, 2011

sagetrac-mraum mannequin commented Aug 6, 2011

sagetrac-mraum mannequin commented Aug 6, 2011

jdemeyer commented Aug 18, 2011

jdemeyer commented Aug 24, 2011

jdemeyer commented Aug 24, 2011

jdemeyer commented Aug 24, 2011

This comment has been minimized.

rbeezer mannequin commented Sep 19, 2011

rbeezer mannequin commented May 28, 2012

This comment has been minimized.

sagetrac-mraum mannequin commented May 28, 2012

rbeezer mannequin commented May 28, 2012

rbeezer mannequin commented May 28, 2012

This comment has been minimized.

dandrake commented May 28, 2012

dandrake commented May 28, 2012

jdemeyer commented Jun 18, 2012

jdemeyer commented Jun 20, 2012

jdemeyer commented Jun 26, 2012

jdemeyer commented Jun 26, 2012

jhpalmieri commented Jul 11, 2012

dandrake commented Jul 11, 2012

jdemeyer commented Jul 13, 2012