Closed 1d7ec08f-60ae-4512-91a6-8324c06eab9f closed 13 years ago
Author: Rob Beezer
Attachment: trac_10837-norms-condition-CDF.patch.gz
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?
**********************************************************************
File "/sage/dev/devel/sage-main/sage/geometry/polyhedra.py", line 4948:
sage: ppoints[0]
Expected:
(0.0, 0.0)
Got:
(1.28197512426e-15, 1.28197512426e-15)
**********************************************************************
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.
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"
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
Great. I'm downloading 4.6.2.rc0 now and will compile it overnight.
Attachment: trac_10837-norms-condition-CDF-edits.patch.gz
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
Volker - any chance of looking at this numerical issue in the polyhedra code? #2512 just saw some work duplicating this.
Rob
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...)
Replying to @vbraun:
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
Thanks, Volker. I'll switch to that and I have another test to add from #2512. Tomorrow.
Attachment: trac_10837-norms-condition-CDF-edits-v2.patch.gz
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.
Description changed:
---
+++
@@ -1 +1,3 @@
Three new methods for matrices and vectors over RDF/CDF, directly wrapping functions from `NumPy/SciPy`.
+
+Apply trac_10837-norms-condition-CDF.patch, trac_10837-norms-condition-CDF-edits-v2.patch
Passes all long tests now, so ready for review.
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
Replying to @haikona: Hi Simon,
Thanks for the review. Responses below:
1) Line 530 of sage/matrix/matrix_double_dense.pyx:
Attachment: trac_10837-norms-condition-CDF-edits-v3.patch.gz
Reviewer: Simon Spicer
Changed keywords from none to matrix, condition, norm
Hi Rob
Thanks, good to know for future. Everything checks out, so I believe this is good to go.
Simon
Replying to @haikona:
Thanks, Simon. Appreciate the help. I'll add you to the master list of linear algebra patches on the next post.
Description changed:
---
+++
@@ -1,3 +1,3 @@
Three new methods for matrices and vectors over RDF/CDF, directly wrapping functions from `NumPy/SciPy`.
-Apply trac_10837-norms-condition-CDF.patch, trac_10837-norms-condition-CDF-edits-v2.patch
+Apply [attachment: trac_10837-norms-condition-CDF.patch](https://github.com/sagemath/sage-prod/files/10652183/trac_10837-norms-condition-CDF.patch.gz) and [attachment: trac_10837-norms-condition-CDF-edits-v2.patch](https://github.com/sagemath/sage-prod/files/10652185/trac_10837-norms-condition-CDF-edits-v2.patch.gz)
Description changed:
---
+++
@@ -1,3 +1,3 @@
Three new methods for matrices and vectors over RDF/CDF, directly wrapping functions from `NumPy/SciPy`.
-Apply [attachment: trac_10837-norms-condition-CDF.patch](https://github.com/sagemath/sage-prod/files/10652183/trac_10837-norms-condition-CDF.patch.gz) and [attachment: trac_10837-norms-condition-CDF-edits-v2.patch](https://github.com/sagemath/sage-prod/files/10652185/trac_10837-norms-condition-CDF-edits-v2.patch.gz)
+Apply [attachment: trac_10837-norms-condition-CDF.patch](https://github.com/sagemath/sage-prod/files/10652183/trac_10837-norms-condition-CDF.patch.gz) and [attachment: trac_10837-norms-condition-CDF-edits-v3.patch](https://github.com/sagemath/sage-prod/files/10652186/trac_10837-norms-condition-CDF-edits-v3.patch.gz)
I assume the v3 version of the patch is the one which should be applied?
This patch conflicts with #10802.
Description changed:
---
+++
@@ -1,3 +1,11 @@
Three new methods for matrices and vectors over RDF/CDF, directly wrapping functions from `NumPy/SciPy`.
-Apply [attachment: trac_10837-norms-condition-CDF.patch](https://github.com/sagemath/sage-prod/files/10652183/trac_10837-norms-condition-CDF.patch.gz) and [attachment: trac_10837-norms-condition-CDF-edits-v3.patch](https://github.com/sagemath/sage-prod/files/10652186/trac_10837-norms-condition-CDF-edits-v3.patch.gz)
+---
+
+**Depends on:**
+
+**Apply:**
+1. [attachment: trac_10837-norms-condition-CDF.patch](https://github.com/sagemath/sage-prod/files/10652183/trac_10837-norms-condition-CDF.patch.gz)
+2. [attachment: trac_10837-norms-condition-CDF-edits-v3.patch](https://github.com/sagemath/sage-prod/files/10652186/trac_10837-norms-condition-CDF-edits-v3.patch.gz)
+
+
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."
Merged: sage-4.7.alpha4
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]
**********************************************************************
Changed merged from sage-4.7.alpha4 to none
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]
**********************************************************************
There are several doctest failures on other buildbot machines with the same tests are the above.
trying to help the build bot :
Apply trac_10837-norms-condition-CDF.patch trac_10837-norms-condition-CDF-edits-v3.patch
Description changed:
---
+++
@@ -4,8 +4,8 @@
**Depends on:**
-**Apply:**
-1. [attachment: trac_10837-norms-condition-CDF.patch](https://github.com/sagemath/sage-prod/files/10652183/trac_10837-norms-condition-CDF.patch.gz)
-2. [attachment: trac_10837-norms-condition-CDF-edits-v3.patch](https://github.com/sagemath/sage-prod/files/10652186/trac_10837-norms-condition-CDF-edits-v3.patch.gz)
+Apply
+trac_10837-norms-condition-CDF.patch
+trac_10837-norms-condition-CDF-edits-v3.patch
trying again
Apply trac_10837-norms-condition-CDF.patch, trac_10837-norms-condition-CDF-edits-v3.patch
Description changed:
---
+++
@@ -4,8 +4,6 @@
**Depends on:**
-Apply
-trac_10837-norms-condition-CDF.patch
-trac_10837-norms-condition-CDF-edits-v3.patch
+Apply trac_10837-norms-condition-CDF.patch, trac_10837-norms-condition-CDF-edits-v3.patch
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..)
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.
Attachment: trac-10837-norms-condition-CDF-review.patch.gz
Attachment: trac-10837-norms-condition-CDF-review2.patch.gz
Changed reviewer from Simon Spicer to Simon Spicer, Martin Raum
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:
Description changed:
---
+++
@@ -2,8 +2,10 @@
---
-**Depends on:**
+**Apply:**
-Apply trac_10837-norms-condition-CDF.patch, trac_10837-norms-condition-CDF-edits-v3.patch
+1. [attachment: trac_10837-norms-condition-CDF.patch](https://github.com/sagemath/sage-prod/files/10652183/trac_10837-norms-condition-CDF.patch.gz)
+2. [attachment: trac_10837-norms-condition-CDF-edits-v3.patch](https://github.com/sagemath/sage-prod/files/10652186/trac_10837-norms-condition-CDF-edits-v3.patch.gz)
+3. [attachment: trac_10837-norms-condition-CDF-review.patch](https://github.com/sagemath/sage/files/ticket10837/trac_10837-norms-condition-CDF-review.patch.gz)
+4. [attachment: trac_10837-norms-condition-CDF-review2.patch](https://github.com/sagemath/sage/files/ticket10837/trac_10837-norms-condition-CDF-review2.patch.gz)
-
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
You're absolutely right, please make the comment a test.
Description changed:
---
+++
@@ -6,6 +6,6 @@
1. [attachment: trac_10837-norms-condition-CDF.patch](https://github.com/sagemath/sage-prod/files/10652183/trac_10837-norms-condition-CDF.patch.gz)
2. [attachment: trac_10837-norms-condition-CDF-edits-v3.patch](https://github.com/sagemath/sage-prod/files/10652186/trac_10837-norms-condition-CDF-edits-v3.patch.gz)
-3. [attachment: trac_10837-norms-condition-CDF-review.patch](https://github.com/sagemath/sage/files/ticket10837/trac_10837-norms-condition-CDF-review.patch.gz)
-4. [attachment: trac_10837-norms-condition-CDF-review2.patch](https://github.com/sagemath/sage/files/ticket10837/trac_10837-norms-condition-CDF-review2.patch.gz)
+3. [attachment: trac-10837-norms-condition-CDF-review.patch](https://github.com/sagemath/sage-prod/files/10652187/trac-10837-norms-condition-CDF-review.patch.gz)
+4. [attachment: trac-10837-norms-condition-CDF-review2.patch](https://github.com/sagemath/sage-prod/files/10652188/trac-10837-norms-condition-CDF-review2.patch.gz)
Attachment: trac-10837-norms-condition-CDF-review-v2.patch.gz
Combined reviewer patch
Changed reviewer from Simon Spicer, Martin Raum to Simon Spicer, Martin Raum, Rob Beezer
Changed author from Rob Beezer to Rob Beezer, Martin Raum
Three new methods for matrices and vectors over RDF/CDF, directly wrapping functions from
NumPy/SciPy
.Apply:
Depends on #10839
CC: @sagetrac-mhampton @vbraun @haraldschilly @haikona @sagetrac-mraum
Component: linear algebra
Keywords: matrix, condition, norm
Author: Rob Beezer, Martin Raum
Reviewer: Simon Spicer, Martin Raum, Rob Beezer, Jeroen Demeyer
Merged: sage-4.7.2.alpha4
Issue created by migration from https://trac.sagemath.org/ticket/10837