Opened 10 years ago

Last modified 9 years ago

#11608 closed enhancement

RDF/CDF eigenvalues: symmetric matrices, multiplicities — at Version 10

Reported by: rbeezer Owned by: jason, was
Priority: minor Milestone: sage-5.1
Component: linear algebra Keywords: sd40.5
Cc: jason Merged in:
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.patch

Change History (11)

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 10 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

Note: See TracTickets for help on using tickets.