Opened 10 years ago

Closed 9 years ago

#11608 closed enhancement (fixed)

RDF/CDF eigenvalues: symmetric matrices, multiplicities

Reported by: rbeezer Owned by: jason, was
Priority: minor Milestone: sage-5.1
Component: linear algebra Keywords: sd40.5
Cc: jason Merged in: sage-5.1.beta4
Authors: Rob Beezer Reviewers: Volker Braun
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Status badges

Description (last modified by rbeezer)

As the summary says, this patch improves eigenvalues of matrices with double-precision floating-point entries.

  1. Uses SciPy's eigh routine for symmetric and Hermitian matrices.
  2. Allows grouping of "equal" eigenvalues, based on a tolerance parameter.

Apply:

  1. trac_11608-eigenvalues-symmetric-multiplicity-rebase.patch
  2. trac_11608-eigenvalues-symmetric-multiplicity-update-v2.patch

Attachments (2)

trac_11608-eigenvalues-symmetric-multiplicity-rebase.patch (11.4 KB) - added by rbeezer 9 years ago.
Rebased on 5.0-beta10
trac_11608-eigenvalues-symmetric-multiplicity-update-v2.patch (3.9 KB) - added by rbeezer 9 years ago.

Download all attachments as: .zip

Change History (19)

comment:1 Changed 10 years ago by rbeezer

  • Authors set to Rob Beezer
  • Description modified (diff)
  • Status changed from new to needs_review

comment:2 Changed 9 years ago by jason

  • Cc jason added

comment:3 Changed 9 years ago by davidloeffler

  • Status changed from needs_review to needs_work
  • Work issues set to rebase

Patch does not apply to 5.0.beta7 (see patchbot logs)

Changed 9 years ago by rbeezer

Rebased on 5.0-beta10

comment:4 Changed 9 years ago by rbeezer

  • Description modified (diff)
  • Status changed from needs_work to needs_review
  • Work issues rebase deleted

comment:5 Changed 9 years ago by dimpase

it's kind of weird that one coerces a complex matrix into real symmetric, but then treats it as a Hermitian one... Surely with real symmetric matrices there might be better options, no?

comment:6 Changed 9 years ago by vbraun

Despite the name, scipy.linalg.eigh will call lapack syevr / heevr depending on whether the field is real / complex.

comment:7 Changed 9 years ago by rbeezer

The algorithm='symmetric' keyword is meant to allow the routine accomodate both base rings (RDF/CDF) while also allowing a user to specify that a matrix is known to be symmetric. In this case, the conversion from CDF to RDF is made by the routine and then the SciPy behavior that Volker notes will take place.

Any suggestions on making the docstring clearer? Maybe saying "then applies the algorithm for Hermitian matrices" should be stated differently?

comment:8 follow-up: Changed 9 years ago by vbraun

  • Reviewers set to Volker Braun
  • Status changed from needs_review to needs_work

On Fedora 16 x86_64, I get

sage -t  devel/sage-main/sage/matrix/matrix_double_dense.pyx
**********************************************************************
File "/home/vbraun/opt/sage-5.0.rc0/devel/sage-main/sage/matrix/matrix_double_dense.pyx", line 1570:
    sage: A.eigenvalues(algorithm='symmetric', tol=1.0e-20)
Expected:
    [(-2.0, 1), (-2.0, 2), (-2.0, 1), (1.0, 1), (1.0, 1), (1.0, 1), (1.0, 1), (1.0, 1), (3.0, 1)]
Got:
    [(-2.0, 1), (-2.0, 2), (-2.0, 1), (1.0, 1), (1.0, 1), (1.0, 2), (1.0, 1), (3.0, 1)]

ATLAS is from Fedora, CPU is a Sandy-Bridge i7 quad-core.

Minor nitpicks while we are at it:

  • Can you return a tuple (=immutable) instead of a list?
  • the symmetric docstring, how about: "converts self to a real matrix and applies the algorithm for Hermitian matrices". Note: technically you convert (explicit), not coerce (implicit).
  • in the hermitian docstring, how about: "uses the :meth:~scipy.linalg.eigh method from SciPy, which applies only to real symmetric or complex Hermitian matrices. Since...". This would make it clear that the syevr implementation is used if possible.
  • the ".. warning::" block is not indented, so it is not typeset correctly.

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

Replying to vbraun:

On Fedora 16 x86_64, I get...

Thanks, I'll increase the tolerance and that should work better across platforms. You'd think I'd get the hang of this numerical stuff...

Minor nitpicks while we are at it:

  • Can you return a tuple (=immutable) instead of a list?

I'm not opposed, but other eigenvalue routines return mutable objects. I'd prefer to do one grand change across all matrix types, on a single-purpose ticket of its own.

sage: A = matrix(QQ, [[1]])
sage: ev=A.eigenvalues()   
sage: type(ev)
<class 'sage.structure.sequence.Sequence_generic'>
sage: ev[0]=5
sage: ev
[5]
  • the symmetric docstring, how about: "converts self to a real matrix and applies the algorithm for Hermitian matrices". Note: technically you convert (explicit), not coerce (implicit).
  • in the hermitian docstring, how about: "uses the :meth:~scipy.linalg.eigh method from SciPy, which applies only to real symmetric or complex Hermitian matrices. Since...". This would make it clear that the syevr implementation is used if possible.
  • the ".. warning::" block is not indented, so it is not typeset correctly.

Thanks for the nits. I'll make some changes right now.

Rob

comment:10 Changed 9 years ago by rbeezer

  • Description modified (diff)
  • Status changed from needs_work to needs_review

"Update" patch:

  1. Removes the 10^-20 tolerance doctest. Not really needed and will only cause trouble. (It was suppose to illustrate how a very small tolerance would split up "equal" eigenvalues.)
  2. Adjusts documentation according to suggestions above.
  3. Includes new pointers to routines to check symmetric and Hermitian properties.
  4. No code changes.

Rob

comment:11 follow-up: Changed 9 years ago by vbraun

  • Status changed from needs_review to positive_review

Looks great!

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

Replying to vbraun:

Looks great!

Thanks, Volker!

This was built on various 5.0-beta's, so I just double-checked that it applies, tests and builds on 5.0-rc0.

Rob

comment:13 Changed 9 years ago by jdemeyer

  • Milestone changed from sage-5.0 to sage-5.1

comment:14 Changed 9 years ago by jdemeyer

  • Status changed from positive_review to needs_work

The warning in the docstring is misformatted, see http://sagemath.org/doc/developer/conventions.html#documentation-strings

comment:15 Changed 9 years ago by rbeezer

  • Description modified (diff)
  • Status changed from needs_work to positive_review

I thought this was OK and I just triple-checked, and I think it is OK. One change: made "warning" all capital letters, this is the only change to the v2 version of the update patch.

The HTML documentation renders the warning blocks as they should. I'm going to move this back to positive review.

Jeroen - please let me know if I am really missing something here. Thanks.

Rob

comment:16 Changed 9 years ago by jdemeyer

  • Keywords sd40.5 added

Yes, it looks okay now. I don't remember what precisely was wrong before.

comment:17 Changed 9 years ago by jdemeyer

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