5
$\begingroup$

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?

  • 0
    It's a CMV matrix. See Section 4.2. of Barry's OPUC book available at http://www.math.caltech.edu/opuc/sampleopuc.html ... (set |alpha_N| = 1 to get an N times N matrix).2011-09-11

1 Answers 1

2

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.

  • 0
    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?2011-09-11