Opened 12 years ago

Closed 11 years ago

# Matrix and vector norms, condition number, over RDF/CDF

Reported by: Owned by: Rob Beezer jason, was minor sage-4.7.2 linear algebra matrix, condition, norm mhampton, Volker Braun, Harald Schilly, Simon Spicer, Martin Raum sage-4.7.2.alpha4 Rob Beezer, Martin Raum Simon Spicer, Martin Raum, Rob Beezer, Jeroen Demeyer N/A #10839

Three new methods for matrices and vectors over RDF/CDF, directly wrapping functions from `NumPy/SciPy`.

Apply:

### comment:1 Changed 12 years ago by Rob Beezer

Authors: → Rob Beezer mhampton Volker Braun added new → needs_info

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)
**********************************************************************
```

### comment:2 Changed 12 years ago by Jason Grout

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 Jason Grout

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
**********************************************************************
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 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 Rob Beezer

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:6 Changed 12 years ago by Rob Beezer

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 Rob Beezer

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 Volker Braun

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 12 years ago by Rob Beezer

Status: needs_info → needs_work

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.

### comment:10 Changed 12 years ago by Rob Beezer

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 Rob Beezer

Description: modified (diff)

### comment:12 Changed 12 years ago by Rob Beezer

Cc: Harald Schilly Simon Spicer added needs_work → needs_review

Passes all long tests now, so ready for review.

### comment:13 follow-up:  14 Changed 12 years ago by Simon Spicer

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 12 years ago by Rob Beezer

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

### comment:15 follow-up:  16 Changed 12 years ago by Simon Spicer

Keywords: matrix condition norm added → Simon Spicer 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 in reply to:  15 Changed 12 years ago by Rob Beezer

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 Jeroen Demeyer

Description: modified (diff)

### comment:18 Changed 12 years ago by Jeroen Demeyer

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 Jeroen Demeyer

Status: positive_review → needs_work

This patch conflicts with #10802.

### comment:20 Changed 12 years ago by Rob Beezer

Description: modified (diff) 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 Jeroen Demeyer

Merged in: → sage-4.7.alpha4 → fixed positive_review → closed

### comment:22 Changed 12 years ago by Jeroen Demeyer

Merged in: sage-4.7.alpha4 fixed 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 Jeroen Demeyer

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 Jeroen Demeyer

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 Frédéric Chapoton

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 Frédéric Chapoton

Description: modified (diff)

### comment:27 Changed 11 years ago by Frédéric Chapoton

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 Frédéric Chapoton

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 Martin Raum

Cc: Martin Raum added 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.

### comment:30 Changed 11 years ago by Martin Raum

Description: modified (diff) Simon Spicer → Simon Spicer, Martin Raum 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 Rob Beezer

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 Martin Raum

Description: modified (diff)

You're absolutely right, please make the comment a test.

### Changed 11 years ago by Rob Beezer

Combined reviewer patch

### comment:33 Changed 11 years ago by Rob Beezer

Authors: Rob Beezer → Rob Beezer, Martin Raum modified (diff) Simon Spicer, Martin Raum → Simon Spicer, Martin Raum, Rob Beezer 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 Jeroen Demeyer

Milestone: sage-4.7.1 → sage-4.7.2

### comment:35 Changed 11 years ago by Jeroen Demeyer

Status: positive_review → needs_work → rebase to #10839

This patch seems to conflict with #10839.

Rebase

### comment:36 Changed 11 years ago by Rob Beezer

Description: modified (diff) needs_work → positive_review 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 Jeroen Demeyer

Dependencies: → #10839

### comment:38 Changed 11 years ago by Jeroen Demeyer

Merged in: → sage-4.7.2.alpha2 → fixed positive_review → closed

### comment:39 Changed 11 years ago by Jeroen Demeyer

Merged in: sage-4.7.2.alpha2 fixed 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 Jeroen Demeyer

Status: new → needs_review

### comment:41 Changed 11 years ago by Jeroen Demeyer

Status: needs_review → needs_work

### comment:42 Changed 11 years ago by Leif Leonhardy

Ping. (#10802 depends on this.)

### comment:43 Changed 11 years ago by Rob Beezer

Description: modified (diff) 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 Jeroen Demeyer

Reviewers: Simon Spicer, Martin Raum, Rob Beezer → Simon Spicer, Martin Raum, Rob Beezer, Jeroen Demeyer 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 Jeroen Demeyer

Merged in: → sage-4.7.2.alpha4 → fixed positive_review → closed
Note: See TracTickets for help on using tickets.