File Exchange

image thumbnail

Symmetric eigenvalue decomposition and the SVD

version 1.0.0.0 (5.68 KB) by Yuji Nakatsukasa

Yuji Nakatsukasa (view profile)
Eigendecomposition of a symmetric matrix or the singular value decomposition of an arbitrary matrix
5.0
2 Ratings

8 Downloads

Updated 23 May 2012

View License

This submission contains functions for computing the eigenvalue decomposition of a symmetric matrix (QDWHEIG.M) and the singular value decomposition (QDWHSVD.M) by efficient and stable algorithms based on spectral divide-and-conquer. The computed results tend to be more accurate than those given by MATLAB's built-in functions EIG.M and SVD.M.

Function TEST.M runs a simple test of the codes.

Details on the underlying algorithms can be found in

Y. Nakatsukasa and N. J. Higham. Stable and Efficient Spectral Divide and Conquer Algorithms for the Symmetric Eigenvalue Decomposition and the SVD. MIMS EPrint 2012.52, The University of Manchester, May 2012.
http://eprints.ma.man.ac.uk/1824

Comments and Ratings (10)

Farooq Aamir

Farooq Aamir (view profile)

@tanglaoya for the complex symmetric matrix I think Takagi decomposition will work but I don't implant the above codes.

tanglaoya

tanglaoya (view profile)

Dear Yuji,
Thank you very much for your great work. Is it possible to generalize your algorithm and code to complex symmetric matrix and generalized eigenvalue problem?

Thanks,
Tang Laoya

Yuji Nakatsukasa

Yuji Nakatsukasa (view profile)

Dear Uri,
While I am happy to see your comment, that sounds surprising (my code often gives better accuracy, but the MATLAB built-in svd, eig, schur are also all backward stable and robust). Could you say more about how the built-in functions failed?

Uri Cohen

Uri Cohen (view profile)

Worked brilliently for me, where the built-in svd, eig and schur have failed completely!

Il

Il (view profile)

Yuji Nakatsukasa

Yuji Nakatsukasa (view profile)

Dear saitarun,
The code qdwheig.m is designed to work only for real symmetric or complex Hermitian matrices. For eigenvalue problems with nonsymmetric matrices I suggest simply using MATLAB's built-in command eig.

saitarun reddy

saitarun reddy (view profile)

I am trying to code the eigen value decomposition for a non-symmetric matrix and i end up getting complex eigen values. Can anyone help me on this?

Thanks.

Yuji Nakatsukasa

Yuji Nakatsukasa (view profile)

Dear Henc,
Many apologies for the delay, I did not notice your comment until now. Regarding row sorting, yes it is a valid option and you can use it when the rows of the matrix have widely varying norms. However there is no theory to support its use (if both column pivoting and row sorting is used the QDWH algorithm can be shown to give backward stable results; however in practice pivoting/sorting is not necessary, and not recommended for speed).

Henc

Henc (view profile)

Yuji,

Sorry, please ignore (2) in my previous comment.

Henc

Henc

Henc (view profile)

Hello Yuji,

I have a few questions/comments.

(1) Your code for qdwh.m provides options for column pivoting and row sorting and your usage comments indicate that you can have either one of: 'rc', 'c', or '' such that you have both row sorting and column pivoting, only column pivoting, or none, respectively. However, within the code your use strfind and it seems that you could also have simply 'r' for row sorting only. Is this a valid option as well?

(2) Within qdwh.m, if row sorting is enabled, I believe that the if statement which performs the row sorting should also contain the following: Uprev = U; since you have changed U and then when you jump into the while loop, your check of norm(U-Uprev, 'fro') would most often be greater than tol3.

Thank you for your submission,
Henc

MATLAB Release Compatibility
Created with R2012a
Compatible with any release
Platform Compatibility
Windows macOS Linux