Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have a sparse unitary matrix with complex entries and want to compute all its eigenvalues. Unfortunately, matlab doesn't like this. If I try do enter eigs(A, N) (A the matrix, N its size), it tells me that I should use eig(full(A)) instead. This is awfully slow ... comparred to the computation for self-adjoint sparse matrices.

Is there any way to do this quicker?

share|improve this question
    
You said "sparse", but is there any particular pattern in the sparsity? –  J. M. Sep 10 '11 at 23:41
    
It's a CMV matrix. See Section 4.2. of Barry's OPUC book available at math.caltech.edu/opuc/sampleopuc.html ... (set |alpha_N| = 1 to get an N times N matrix). –  Helge Sep 11 '11 at 10:48

1 Answer 1

An unitary matrix $A$ is normal, i.e. $A^HA=AA^H$. Let's define $\operatorname{Re}(A):=(A+A^H)/2$ and $\operatorname{Im}(A):=(A-A^H)/(2i)$. Note that $\operatorname{Re}(A)$ and $\operatorname{Im}(A)$ are self adjoint (sparse) matrices, and satisfy $\operatorname{Re}(A)\operatorname{Im}(A)=\operatorname{Im}(A)\operatorname{Re}(A)$, i.e. they commute.

So you can compute the real and imaginary parts of the eigenvalues separately. To match corresponding real and imaginary parts together, you have to look at the mutual eigenspaces.

share|improve this answer
    
'you have to look at the mutual eigenspaces' Perhaps it's more simple (and efficient) to compute just the real part and, knowing that $|\lambda|=1$, try out the two possible imaginary parts. –  leonbloy Sep 11 '11 at 0:09
    
@leonbloy Maybe it can be done simpler for unitary matrices, like you describe. I'm not really how to "try out" the imaginary parts, especially when $\operatorname{Re}(A)$ has duplicate eigenvalues. I also tried to explain why matlab and most libraries for computing eigenvalues don't provide special routines for normal matrices. –  Thomas Klimpel Sep 11 '11 at 9:15
    
This is possible ... but: 1. If one would start from an upper Hessenberg matrix, one would get a full matrix, and whereas the computation is fast for upper Hessenberg matrices, it's awfully slow for full ones. 2. This seems somewhat complicated to write. My current code to computing with the full matrix is like 20 lines, this would be somewhat longer ... –  Helge Sep 11 '11 at 10:50
    
If $A$ has $m$-nonzero entries, $A+A^H$ will have at most $2m$-nonzero entries. So if the computation is fast for upper Hessenberg matrices, I guess it's because these matrices are quite sparse Hessenberg matrices, and this sparsity will be preserved as far as possible. I don't fully understand your comment with the 20 lines. Just write a subroutine to compute the eigendecomposition of normal/unitary $A$. Writing eigs((A+A')/2,N) is probably not the difficult part, so I guess your complaint is about the matching part, which I haven't described in detail. Is this missing detail the real issue? –  Thomas Klimpel Sep 11 '11 at 16:13

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.