Opened 10 years ago
Closed 10 years ago
#10837 closed enhancement (fixed)
Matrix and vector norms, condition number, over RDF/CDF
Reported by: | rbeezer | Owned by: | jason, was |
---|---|---|---|
Priority: | minor | Milestone: | sage-4.7.2 |
Component: | linear algebra | Keywords: | matrix, condition, norm |
Cc: | mhampton, vbraun, schilly, spice, mraum | 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 10 years ago by
comment:1 Changed 10 years ago by
- Cc mhampton vbraun added
- Status changed from new to needs_info
comment:2 Changed 10 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 10 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 10 years ago by
- Status changed from needs_info to 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 10 years ago by
Great. I'm downloading 4.6.2.rc0 now and will compile it overnight.
Changed 10 years ago by
comment:6 Changed 10 years ago by
- Status changed from needs_work to 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 10 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 10 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 in reply to: ↑ 8 Changed 10 years ago by
- Status changed from needs_info to needs_work
Changed 10 years ago by
comment:10 Changed 10 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 10 years ago by
- Description modified (diff)
comment:12 Changed 10 years ago by
- Cc schilly spice added
- Status changed from needs_work to needs_review
Passes all long tests now, so ready for review.
comment:13 follow-up: ↓ 14 Changed 10 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 in reply to: ↑ 13 Changed 10 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 10 years ago by
comment:15 follow-up: ↓ 16 Changed 10 years ago by
- Keywords matrix condition norm added
- Reviewers set to Simon Spicer
- Status changed from needs_review to positive_review
Hi Rob
Thanks, good to know for future. Everything checks out, so I believe this is good to go.
Simon
comment:16 in reply to: ↑ 15 Changed 10 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 10 years ago by
- Description modified (diff)
comment:18 Changed 10 years ago by
- Description modified (diff)
I assume the v3 version of the patch is the one which should be applied?
comment:19 Changed 10 years ago by
- Status changed from positive_review to needs_work
This patch conflicts with #10802.
comment:20 Changed 10 years ago by
- Description modified (diff)
- Status changed from needs_work to 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 10 years ago by
- Merged in set to sage-4.7.alpha4
- Resolution set to fixed
- Status changed from positive_review to closed
comment:22 Changed 10 years ago by
- Merged in sage-4.7.alpha4 deleted
- Resolution fixed deleted
- Status changed from closed to 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 10 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 10 years ago by
- Status changed from new to needs_work
There are several doctest failures on other buildbot machines with the same tests are the above.
comment:25 Changed 10 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 10 years ago by
- Description modified (diff)
comment:27 Changed 10 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 10 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 10 years ago by
- Cc mraum added
- Status changed from needs_work to 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 10 years ago by
Changed 10 years ago by
comment:30 Changed 10 years ago by
- Description modified (diff)
- Reviewers changed from Simon Spicer to Simon Spicer, Martin Raum
- Status changed from needs_info to 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 10 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 10 years ago by
- Description modified (diff)
You're absolutely right, please make the comment a test.
comment:33 Changed 10 years ago by
- Description modified (diff)
- Reviewers changed from Simon Spicer, Martin Raum to Simon Spicer, Martin Raum, Rob Beezer
- Status changed from needs_review to 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 10 years ago by
- Milestone changed from sage-4.7.1 to sage-4.7.2
comment:35 Changed 10 years ago by
- Status changed from positive_review to needs_work
- Work issues set to rebase to #10839
This patch seems to conflict with #10839.
comment:36 Changed 10 years ago by
- Description modified (diff)
- Status changed from needs_work to positive_review
- Work issues rebase to #10839 deleted
"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 10 years ago by
- Dependencies set to #10839
comment:38 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:39 Changed 10 years ago by
- Merged in sage-4.7.2.alpha2 deleted
- Resolution fixed deleted
- Status changed from closed to 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 10 years ago by
- Status changed from new to needs_review
comment:41 Changed 10 years ago by
- Status changed from needs_review to needs_work
comment:42 Changed 10 years ago by
Ping. (#10802 depends on this.)
Changed 10 years ago by
comment:43 Changed 10 years ago by
- Description modified (diff)
- Status changed from needs_work to 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 10 years ago by
- Reviewers changed from Simon Spicer, Martin Raum, Rob Beezer to Simon Spicer, Martin Raum, Rob Beezer, Jeroen Demeyer
- Status changed from needs_review to 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 10 years ago by
- Merged in set to sage-4.7.2.alpha4
- Resolution set to fixed
- Status changed from positive_review to 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?