Opened 12 years ago
Closed 11 years ago
#10837 closed enhancement (fixed)
Matrix and vector norms, condition number, over RDF/CDF
Reported by: | Rob Beezer | Owned by: | jason, was |
---|---|---|---|
Priority: | minor | Milestone: | sage-4.7.2 |
Component: | linear algebra | Keywords: | matrix, condition, norm |
Cc: | mhampton, Volker Braun, Harald Schilly, Simon Spicer, Martin Raum | Merged in: | sage-4.7.2.alpha4 |
Authors: | Rob Beezer, Martin Raum | Reviewers: | Simon Spicer, Martin Raum, Rob Beezer, Jeroen Demeyer |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | #10839 | Stopgaps: |
Description (last modified by )
Three new methods for matrices and vectors over RDF/CDF, directly wrapping functions from NumPy/SciPy
.
Apply:
Attachments (9)
Change History (54)
Changed 12 years ago by
Attachment: | trac_10837-norms-condition-CDF.patch added |
---|
comment:1 Changed 12 years ago by
Authors: | → Rob Beezer |
---|---|
Cc: | mhampton Volker Braun added |
Status: | new → needs_info |
comment:2 Changed 12 years ago by
Minor nitpick (really minor): "if not p in [-2,-1,1,2]:" reads better as "if p not in [-2,-1,1,2]:", I think.
In the doctests for norm, shouldn't "Return values are in RDF
. " be followed by a double-colon?
In the OUTPUT docs for the vector norm: "Returned values is a double precision" --> values should be the singular "value". Also, "(or an integer when p=0
." is missing a closing parenthesis.
I've read through the patch and am testing the patch now, so if you attach corrections, please submit them as a separate patch.
comment:3 Changed 12 years ago by
I had some interesting failures on 4.6.1:
% sage -t matrix2.pyx Detected SAGE64 flag Building Sage on OS X in 64-bit mode sage -t "trees/sage-4.6.1/devel/sage-main/sage/matrix/matrix2.pyx" ********************************************************************** File "/Users/grout/sage-trees/sage-4.6.1/devel/sage-main/sage/matrix/matrix2.pyx", line 6726: sage: A = matrix(RR, 2, 3, [3*I,4,1-I,1,2,0]) Exception raised: Traceback (most recent call last): File "/Users/grout/sage/local/bin/ncadoctest.py", line 1231, in run_one_test self.run_one_example(test, example, filename, compileflags) File "/Users/grout/sage/local/bin/sagedoctest.py", line 38, in run_one_example OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags) File "/Users/grout/sage/local/bin/ncadoctest.py", line 1172, in run_one_example compileflags, 1) in test.globs File "<doctest __main__.example_96[11]>", line 1, in <module> A = matrix(RR, Integer(2), Integer(3), [Integer(3)*I,Integer(4),Integer(1)-I,Integer(1),Integer(2),Integer(0)])###line 6726: sage: A = matrix(RR, 2, 3, [3*I,4,1-I,1,2,0]) File "/Users/grout/sage/local/lib/python/site-packages/sage/matrix/constructor.py", line 666, in matrix return matrix_space.MatrixSpace(ring, nrows, ncols, sparse=sparse)(entries) File "/Users/grout/sage/local/lib/python/site-packages/sage/matrix/matrix_space.py", line 405, in __call__ return self.matrix(entries, copy=copy, coerce=coerce, rows=rows) File "/Users/grout/sage/local/lib/python/site-packages/sage/matrix/matrix_space.py", line 1136, in matrix return self.__matrix_class(self, entries=x, copy=copy, coerce=coerce) File "matrix_generic_dense.pyx", line 109, in sage.matrix.matrix_generic_dense.Matrix_generic_dense.__init__ (sage/matrix/matrix_generic_dense.c:2349) self._entries[i] = R(entries[i]) File "parent.pyx", line 882, in sage.structure.parent.Parent.__call__ (sage/structure/parent.c:6462) File "coerce_maps.pyx", line 156, in sage.structure.coerce_maps.NamedConvertMap._call_ (sage/structure/coerce_maps.c:4044) File "expression.pyx", line 836, in sage.symbolic.expression.Expression._mpfr_ (sage/symbolic/expression.cpp:4944) File "expression.pyx", line 766, in sage.symbolic.expression.Expression._eval_self (sage/symbolic/expression.cpp:4712) File "pynac.pyx", line 1010, in sage.symbolic.pynac.py_float (sage/symbolic/pynac.cpp:8911) File "parent.pyx", line 882, in sage.structure.parent.Parent.__call__ (sage/structure/parent.c:6462) File "coerce_maps.pyx", line 156, in sage.structure.coerce_maps.NamedConvertMap._call_ (sage/structure/coerce_maps.c:4044) File "number_field_element.pyx", line 959, in sage.rings.number_field.number_field_element.NumberFieldElement._mpfr_ (sage/rings/number_field/number_field_element.cpp:8538) TypeError: cannot convert 3*I to real number ********************************************************************** File "/Users/grout/sage-trees/sage-4.6.1/devel/sage-main/sage/matrix/matrix2.pyx", line 6727: sage: A.norm('frob') Expected: 5.65685424949 Got: 15.8113883008 ********************************************************************** File "/Users/grout/sage-trees/sage-4.6.1/devel/sage-main/sage/matrix/matrix2.pyx", line 6729: sage: A.norm(2) Expected: 5.47068444321 Got: 15.0 ********************************************************************** File "/Users/grout/sage-trees/sage-4.6.1/devel/sage-main/sage/matrix/matrix2.pyx", line 6731: sage: A.norm(1) Expected: 6.0 Got: 17.0 ********************************************************************** File "/Users/grout/sage-trees/sage-4.6.1/devel/sage-main/sage/matrix/matrix2.pyx", line 6733: sage: A.norm(Infinity) Expected: 8.41421356237 Got: 17.0 ********************************************************************** 1 items had failures: 5 of 19 in __main__.example_96 ***Test Failed*** 5 failures. For whitespace errors, see the file /Users/grout/.sage//tmp/.doctest_matrix2.py [30.5 s] ---------------------------------------------------------------------- The following tests failed: sage -t "trees/sage-4.6.1/devel/sage-main/sage/matrix/matrix2.pyx"
It seems like there was a patch recently that addressed the next error (maybe merged after 4.6.1?)
filename, compileflags) File "/Users/grout/sage/local/bin/sagedoctest.py", line 38, in run_one_example OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags) File "/Users/grout/sage/local/bin/ncadoctest.py", line 1172, in run_one_example compileflags, 1) in test.globs File "<doctest __main__.example_17[29]>", line 1, in <module> A.is_singular()###line 667: sage: A.is_singular() File "element.pyx", line 306, in sage.structure.element.Element.__getattr__ (sage/structure/element.c:2666) File "parent.pyx", line 272, in sage.structure.parent.getattr_from_other_class (sage/structure/parent.c:2840) File "parent.pyx", line 170, in sage.structure.parent.raise_attribute_error (sage/structure/parent.c:2611) AttributeError: 'sage.matrix.matrix_rational_dense.Matrix_rational_dense' object has no attribute 'is_singular' ********************************************************************** 1 items had failures: 1 of 35 in __main__.example_17 ***Test Failed*** 1 failures. For whitespace errors, see the file /Users/grout/.sage//tmp/.doctest_matrix_double_dense.py [2.7 s] ---------------------------------------------------------------------- The following tests failed: sage -t "trees/sage-4.6.1/devel/sage-main/sage/matrix/matrix_double_dense.pyx"
comment:4 Changed 12 years ago by
Status: | needs_info → needs_work |
---|
Hi Jason,
Thanks for the look and the nits. I'll tidy up in the morning, I'm about to call it a day.
The matrix2.pyx
failures are from replacing CDF
by RR
, not CC
. I'd swear those had been tested.
Yes, lots of new stuff in 4.6.2.rc0, including is_singular()
. See the table at http://wiki.sagemath.org/devel/LatexToWorksheet
Rob
comment:5 Changed 12 years ago by
Great. I'm downloading 4.6.2.rc0 now and will compile it overnight.
Changed 12 years ago by
Attachment: | trac_10837-norms-condition-CDF-edits.patch added |
---|
comment:6 Changed 12 years ago by
Status: | needs_work → needs_info |
---|
Jason,
Thanks for the edits - they are all on the second patch. With this all tests pass in sage/matrix and sage/modules.
Still need some advice on the polyhedra failure.
Rob
comment:7 Changed 12 years ago by
Volker - any chance of looking at this numerical issue in the polyhedra code? #2512 just saw some work duplicating this.
Rob
comment:8 follow-up: 9 Changed 12 years ago by
We should just pick a point in the projection to doctest whose coordinates are not zero so that the floating point issues don't show up. E.g. change to
sage: ppoints[1] (-0.3182829598..., 1.18784817...)
comment:9 Changed 12 years ago by
Status: | needs_info → needs_work |
---|
Changed 12 years ago by
Attachment: | trac_10837-norms-condition-CDF-edits-v2.patch added |
---|
comment:10 Changed 12 years ago by
v2 of the edit patch adds some consistency checks for matrix norms and condition numbers and adjusts the polyhedra doctest.
Running full tests right now.
comment:11 Changed 12 years ago by
Description: | modified (diff) |
---|
comment:12 Changed 12 years ago by
Cc: | Harald Schilly Simon Spicer added |
---|---|
Status: | needs_work → needs_review |
Passes all long tests now, so ready for review.
comment:13 follow-up: 14 Changed 12 years ago by
Hi Rob
All the tests pass muster, and the code checks out. A couple of cosmetic issues:
1) Line 530 of sage/matrix/matrix_double_dense.pyx:
######################################################################## # LEVEL 3 functionality (Optional) # * cdef _sub_ # * __deepcopy__ # * __invert__ # * Matrix windows -- only if you need strassen for that base # * Other functions (list them here): # # compute_LU(self) # ########################################################################
Perhaps list the methods here for ease of maintainance later on.
2) In your documentation on condition() and norm() you're missing an 'n' in the word 'column' for the -Infinity norm case. Line 582 of sage/matrix/matrix_double_dense.pyx:
- ``p = Infinity`` or ``p = oo``: the maximum row sum. - ``p = -Infinity`` or ``p = -oo``: the minimum colum sum. - ``p = 1``: the maximum column sum.
3) Line 705 of sage/matrix/matrix_double_dense.pyx:
if numpy is None: import numpy import sage.rings.infinity import sage.rings.integer import sage.rings.real_double
By convention, shouldn't import commands be listed at the top of a file?
4) The same again as above for the norm() code for matrices and vectors you've added.
Simon
comment:14 Changed 12 years ago by
Replying to spice: Hi Simon,
Thanks for the review. Responses below:
1) Line 530 of sage/matrix/matrix_double_dense.pyx:
<snip>
Perhaps list the methods here for ease of maintainance later on.
Take a look at sage/matrix/docs.py. This stuff comes from there and is a list of things you have to do in order for matrices to "work". So it seems to be used as a check-list more than a list of what is available.
2) In your documentation on condition() and norm() you're missing an 'n' in the word 'column' for the -Infinity norm case.
Good catch - I rolled this into a version 3 of the "edits" patch.
3) Line 705 of sage/matrix/matrix_double_dense.pyx: By convention, shouldn't import commands be listed at the top of a file? 4) The same again as above for the norm() code for matrices and vectors you've added.
At the top of the file, then the import happens at start-up, which adds to the (noticeable) delay. You can import anywhere, this is an attempt to delay it until it is needed. numpy
should be a variable, with module scope, so the conditional will mean the import only happens once (but I suspect it is not strictly necessary), which you will see throughout this file in other methods.
Rob
Changed 12 years ago by
Attachment: | trac_10837-norms-condition-CDF-edits-v3.patch added |
---|
comment:15 follow-up: 16 Changed 12 years ago by
Keywords: | matrix condition norm added |
---|---|
Reviewers: | → Simon Spicer |
Status: | needs_review → positive_review |
Hi Rob
Thanks, good to know for future. Everything checks out, so I believe this is good to go.
Simon
comment:16 Changed 12 years ago by
Replying to spice:
Thanks, Simon. Appreciate the help. I'll add you to the master list of linear algebra patches on the next post.
comment:17 Changed 12 years ago by
Description: | modified (diff) |
---|
comment:18 Changed 12 years ago by
Description: | modified (diff) |
---|
I assume the v3 version of the patch is the one which should be applied?
comment:19 Changed 12 years ago by
Status: | positive_review → needs_work |
---|
This patch conflicts with #10802.
comment:20 Changed 12 years ago by
Description: | modified (diff) |
---|---|
Status: | needs_work → positive_review |
This conflicts with #10802, but is just fine all by itself - applies, builds, passes long tests on 4.7.alpha3.
There is an original patch and three iterations of a follow-on "edit" patch, so there are two patches to apply. Description is updated.
I am going to whip #10802 into shape, since it has other "issues." Thus, I'm going to flip this back to "positive review."
comment:21 Changed 12 years ago by
Merged in: | → sage-4.7.alpha4 |
---|---|
Resolution: | → fixed |
Status: | positive_review → closed |
comment:22 Changed 12 years ago by
Merged in: | sage-4.7.alpha4 |
---|---|
Resolution: | fixed |
Status: | closed → new |
On cicero (Fedora 14-32):
sage -t -long -force_lib devel/sage/sage/modules/vector_double_dense.pyx Warning: divide by zero encountered in power ********************************************************************** File "/home/buildbot/build/sage/cicero-1/cicero_full/build/sage-4.7.alpha4/devel/sage-main/sage/modules/vector_double_dense.pyx", line 628: sage: v.norm(p=0) Expected: 8 Got: 8.0 ********************************************************************** File "/home/buildbot/build/sage/cicero-1/cicero_full/build/sage-4.7.alpha4/devel/sage-main/sage/modules/vector_double_dense.pyx", line 640: sage: w.norm(p=0) Expected: 2 Got: 2.0 **********************************************************************
sage -t -long -force_lib devel/sage/sage/matrix/matrix_double_dense.pyx ********************************************************************** File "/home/buildbot/build/sage/cicero-1/cicero_full/build/sage-4.7.alpha4/devel/sage-main/sage/matrix/matrix_double_dense.pyx", line 646: sage: A.condition() Expected: 1.63346888329e+13 Got: 1.63347342847e+13 ********************************************************************** File "/home/buildbot/build/sage/cicero-1/cicero_full/build/sage-4.7.alpha4/devel/sage-main/sage/matrix/matrix_double_dense.pyx", line 791: sage: A.norm(p=-2) Expected: 3.84592537...e-16 Got: 2.86378720384e-16 ********************************************************************** File "/home/buildbot/build/sage/cicero-1/cicero_full/build/sage-4.7.alpha4/devel/sage-main/sage/matrix/matrix_double_dense.pyx", line 1862: sage: T.round(4) Expected: [-13.5698 0.0 0.0 0.0] [ 0.0 -0.8508 -0.0 -0.0] [ 0.0 0.0 7.7664 0.0] [ 0.0 0.0 0.0 11.6542] Got: [-13.5698 -0.0 -0.0 -0.0] [ 0.0 -0.8508 0.0 -0.0] [ 0.0 0.0 7.7664 0.0] [ 0.0 0.0 0.0 11.6542] **********************************************************************
comment:23 Changed 12 years ago by
On cleo (RHEL 5.3-64):
sage -t -long -force_lib devel/sage/sage/modules/vector_double_dense.pyx Warning: divide by zero encountered in power ********************************************************************** File "/home/buildbot/build/sage/cleo-1/cleo_full/build/sage-4.7.alpha4/devel/sage-main/sage/modules/vector_double_dense.pyx", line 626: sage: v.norm(p=-oo) Expected: 0.0 Got: -0.0 **********************************************************************
sage -t -long -force_lib devel/sage/sage/matrix/matrix_double_dense.pyx ********************************************************************** File "/home/buildbot/build/sage/cleo-1/cleo_full/build/sage-4.7.alpha4/devel/sage-main/sage/matrix/matrix_double_dense.pyx", line 646: sage: A.condition() Expected: 1.63346888329e+13 Got: 1.63344849368e+13 ********************************************************************** File "/home/buildbot/build/sage/cleo-1/cleo_full/build/sage-4.7.alpha4/devel/sage-main/sage/matrix/matrix_double_dense.pyx", line 791: sage: A.norm(p=-2) Expected: 3.84592537...e-16 Got: 1.64639435859e-16 ********************************************************************** File "/home/buildbot/build/sage/cleo-1/cleo_full/build/sage-4.7.alpha4/devel/sage-main/sage/matrix/matrix_double_dense.pyx", line 1862: sage: T.round(4) Expected: [-13.5698 0.0 0.0 0.0] [ 0.0 -0.8508 -0.0 -0.0] [ 0.0 0.0 7.7664 0.0] [ 0.0 0.0 0.0 11.6542] Got: [-13.5698 -0.0 0.0 0.0] [ 0.0 -0.8508 0.0 -0.0] [ 0.0 0.0 7.7664 -0.0] [ 0.0 0.0 0.0 11.6542] **********************************************************************
comment:24 Changed 12 years ago by
Status: | new → needs_work |
---|
There are several doctest failures on other buildbot machines with the same tests are the above.
comment:25 Changed 11 years ago by
trying to help the build bot :
Apply trac_10837-norms-condition-CDF.patch trac_10837-norms-condition-CDF-edits-v3.patch
comment:26 Changed 11 years ago by
Description: | modified (diff) |
---|
comment:27 Changed 11 years ago by
Description: | modified (diff) |
---|
trying again
Apply trac_10837-norms-condition-CDF.patch, trac_10837-norms-condition-CDF-edits-v3.patch
comment:28 Changed 11 years ago by
This is supposed to wake up the bot:
Apply trac_10837-norms-condition-CDF.patch, trac_10837-norms-condition-CDF-edits- v3.patch
but it did not work (already tried twice, let us try again..)
comment:29 Changed 11 years ago by
Cc: | Martin Raum added |
---|---|
Status: | needs_work → needs_info |
I was going to fix the doctests and the 0-norm for the vectors. But have a look at the condition of A in your doctests! The -oo condition is 17.5, but clearly the minimal sum over rows is 9! This is not an issue of the wrapper, but numpy gives the same result. Do you have any explanation at hand?
One thing: Is there any particular reason why you didn't include the usual condition, given as the quotient of the minimal and the maximal sv? This works for nonsquare matrices as well and is thus very important to have.
Changed 11 years ago by
Attachment: | trac-10837-norms-condition-CDF-review.patch added |
---|
Changed 11 years ago by
Attachment: | trac-10837-norms-condition-CDF-review2.patch added |
---|
comment:30 Changed 11 years ago by
Description: | modified (diff) |
---|---|
Reviewers: | Simon Spicer → Simon Spicer, Martin Raum |
Status: | needs_info → needs_review |
Sorry, I confused the norm and the condition method. Everthing is OK now.
I fixed the doctests and so that they will work on cleo, too. I also added the possibility to ask for the usual condition by passing p = 'sv' for singular values. All your changes are OK, so if you approve the new changes, you can give this a positive review.
Apply:
comment:31 Changed 11 years ago by
Hi Martin,
Somehow missed the singular value option in the NumPy docs. Thanks for catching that and enabling it!
All the changes and additions look good to me. The one test in the "review2" patch has a comment symbol in front of the all()
. If that is removed, the test passes (with result True
). Did you intend to remove the comment symbol?
If so, just let me know and I can fix it and get this ticket marked positive review and all ready to go.
Thanks, Rob
comment:32 Changed 11 years ago by
Description: | modified (diff) |
---|
You're absolutely right, please make the comment a test.
Changed 11 years ago by
Attachment: | trac-10837-norms-condition-CDF-review-v2.patch added |
---|
Combined reviewer patch
comment:33 Changed 11 years ago by
Authors: | Rob Beezer → Rob Beezer, Martin Raum |
---|---|
Description: | modified (diff) |
Reviewers: | Simon Spicer, Martin Raum → Simon Spicer, Martin Raum, Rob Beezer |
Status: | needs_review → positive_review |
I took out the comment symbol to restore the test, and have combined the two reviewer tickets, since they need a user string (added Martin in on that). Enabling the 'sv' option is a significant addition, so I have added Martin as an author (and myself as the reviewer of that).
Passes all long tests, so as proposed, I have switched this to 'positive' review. Thanks for the help on this on, Martin and Simon.
Rob
comment:34 Changed 11 years ago by
Milestone: | sage-4.7.1 → sage-4.7.2 |
---|
comment:35 Changed 11 years ago by
Status: | positive_review → needs_work |
---|---|
Work issues: | → rebase to #10839 |
This patch seems to conflict with #10839.
comment:36 Changed 11 years ago by
Description: | modified (diff) |
---|---|
Status: | needs_work → positive_review |
Work issues: | rebase to #10839 |
"v2" version of main patch is a rebase against a stock 4.7.1 with #10839 applied. Tested on sage/matrix/matrix_double_dense.pyx. Thanks.
comment:37 Changed 11 years ago by
Dependencies: | → #10839 |
---|
comment:38 Changed 11 years ago by
Merged in: | → sage-4.7.2.alpha2 |
---|---|
Resolution: | → fixed |
Status: | positive_review → closed |
comment:39 Changed 11 years ago by
Merged in: | sage-4.7.2.alpha2 |
---|---|
Resolution: | fixed |
Status: | closed → new |
On hawk (OpenSolaris? 06/2009 i86pc Xeon W3580):
sage -t -long -force_lib devel/sage/sage/matrix/matrix_double_dense.pyx ********************************************************************** 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 713: sage: abs(c-d) < 1.0e-14 Expected: True Got: False **********************************************************************
comment:40 Changed 11 years ago by
Status: | new → needs_review |
---|
comment:41 Changed 11 years ago by
Status: | needs_review → needs_work |
---|
Changed 11 years ago by
Attachment: | trac_10837-numerical-noise-solaris.patch added |
---|
comment:43 Changed 11 years ago by
Description: | modified (diff) |
---|---|
Status: | needs_work → needs_review |
"noise-solaris" patch fixes the failing doctest by relaxing the tolerance, and makes a similar change to a similar doctest in the same block.
comment:44 Changed 11 years ago by
Reviewers: | Simon Spicer, Martin Raum, Rob Beezer → Simon Spicer, Martin Raum, Rob Beezer, Jeroen Demeyer |
---|---|
Status: | needs_review → positive_review |
Positive review for trac_10837-numerical-noise-solaris.patch. I haven't tested it on Solaris, but that will happen later.
comment:45 Changed 11 years ago by
Merged in: | → sage-4.7.2.alpha4 |
---|---|
Resolution: | → fixed |
Status: | positive_review → closed |
With a more specific norm now defined for vectors and matrices over CDF/RDF, the computation might conceivably differ from the more generic implementation provided in
matrix2.pyx
. Just one test failure though, and I'm not sure how to fix it up.Volker, Marshall? Any ideas?