Opened 11 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:

Status badges

Attachments (9)

Change History (54)

Changed 11 years ago by rbeezer

comment:1 Changed 11 years ago by rbeezer

  • Authors set to Rob Beezer
  • Cc mhampton vbraun added
  • Status changed from new to 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 11 years ago by jason

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 11 years ago by jason

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 11 years ago by rbeezer

  • 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 11 years ago by jason

Great. I'm downloading 4.6.2.rc0 now and will compile it overnight.

Changed 11 years ago by rbeezer

comment:6 Changed 11 years ago by rbeezer

  • 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 11 years ago by rbeezer

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: Changed 11 years ago by 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

sage: ppoints[1]
(-0.3182829598..., 1.18784817...)

comment:9 in reply to: ↑ 8 Changed 11 years ago by rbeezer

  • Status changed from needs_info to needs_work

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.

comment:10 Changed 11 years ago by rbeezer

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 11 years ago by rbeezer

  • Description modified (diff)

comment:12 Changed 11 years ago by rbeezer

  • 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: Changed 11 years ago by spice

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 11 years ago by rbeezer

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

comment:15 follow-up: Changed 11 years ago by spice

  • 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 11 years ago by rbeezer

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 11 years ago by jdemeyer

  • Description modified (diff)

comment:18 Changed 11 years ago by jdemeyer

  • Description modified (diff)

I assume the v3 version of the patch is the one which should be applied?

comment:19 Changed 11 years ago by jdemeyer

  • Status changed from positive_review to needs_work

This patch conflicts with #10802.

comment:20 Changed 11 years ago by rbeezer

  • 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 11 years ago by jdemeyer

  • Merged in set to sage-4.7.alpha4
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:22 Changed 11 years ago by jdemeyer

  • 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 11 years ago by jdemeyer

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 11 years ago by jdemeyer

  • 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 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 10 years ago by chapoton

  • Description modified (diff)

comment:27 Changed 10 years ago by chapoton

  • 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 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 10 years ago by mraum

  • 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.

comment:30 Changed 10 years ago by mraum

  • 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:

  1. trac_10837-norms-condition-CDF.patch
  2. trac_10837-norms-condition-CDF-edits-v3.patch
  3. trac_10837-norms-condition-CDF-review.patch
  4. trac_10837-norms-condition-CDF-review2.patch

comment:31 Changed 10 years ago by rbeezer

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 mraum

  • Description modified (diff)

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

Changed 10 years ago by rbeezer

Combined reviewer patch

comment:33 Changed 10 years ago by rbeezer

  • Authors changed from Rob Beezer to Rob Beezer, Martin Raum
  • 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 jdemeyer

  • Milestone changed from sage-4.7.1 to sage-4.7.2

comment:35 Changed 10 years ago by jdemeyer

  • Status changed from positive_review to needs_work
  • Work issues set to rebase to #10839

This patch seems to conflict with #10839.

Changed 10 years ago by rbeezer

Rebase

comment:36 Changed 10 years ago by rbeezer

  • 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 jdemeyer

  • Dependencies set to #10839

comment:38 Changed 10 years ago by jdemeyer

  • 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 jdemeyer

  • 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 jdemeyer

  • Status changed from new to needs_review

comment:41 Changed 10 years ago by jdemeyer

  • Status changed from needs_review to needs_work

comment:42 Changed 10 years ago by leif

Ping. (#10802 depends on this.)

Changed 10 years ago by rbeezer

comment:43 Changed 10 years ago by rbeezer

  • 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 jdemeyer

  • 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 jdemeyer

  • Merged in set to sage-4.7.2.alpha4
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.