5
$\begingroup$

How to estimate $$\max_i |\mathrm{Arg}(-\lambda_i)|,$$ where $\{\lambda_i\}$ are eigenvalues of a large sparse matrix $A$ all lying in the left complex half-plane?

$\endgroup$
7
  • $\begingroup$ What exactly do you mean by the "argument" or eigenvalues? $\endgroup$
    – Paul
    Commented May 9, 2012 at 16:16
  • $\begingroup$ en.wikipedia.org/wiki/Arg_%28mathematics%29 $\endgroup$
    – Emre
    Commented May 9, 2012 at 16:55
  • $\begingroup$ Given $M=URU^\ast + \Im UIU^\ast=0.5(M+M^\ast)+0.5(M-M^\ast)=S+A$, where $U$ is a unitary matrix, $R$ and $I$ are real diagonal matrices, $A$ is the antisymmetric component and $S$ is the hermitian component, could you just use $Arg(\|S\|+\Im \|A\|)$? $\endgroup$ Commented May 10, 2012 at 13:35
  • $\begingroup$ @Deathbreath: I think that would only find the argument of the largest real and imaginary parts. I think that if an eigenvalue had a very small magnitude but a large argument that your method would not pick it up. I might be wrong about this, though. $\endgroup$
    – Dan
    Commented May 10, 2012 at 21:02
  • $\begingroup$ Have you tried to find the eigenvalue with the largest real part? $\endgroup$
    – dranxo
    Commented May 23, 2012 at 7:27

2 Answers 2

1
$\begingroup$

You could multiply a random vector by the matrix repeatedly. The magnitude of a given eigenvalue will tend to cause the vector's magnitude to grow, and the argument will tend to cause the vector to oscillate.

If you store the vector after each step, and then take the componentwise FFT, the highest frequency components should correspond to the largest arguments of eigenvalues of the matrix.

We can show this as follows:

Let each eigenvalue $\lambda_k=r_ke^{i\theta_k}$. Then, for a given eigenvector $x_k$, the effect of the matrix applied $n$ times would be $r_k^ne^{in\theta_k}x_k$, which clearly has a peak in the fourier transform with respect to $n$ around $\theta_k$. If one has a vector which is a linear combination of eigenvectors, there will be one peak per eigenvector.

This method has some problems:

  • If the magnitude of the eigenvector with the greatest argument is small, the oscillation may be so suppressed that you are unable to detect it.

  • It's not a standard method as far as I know (just something I came up with), so it probably has thorny bits I'm not aware of. Also, I haven't actually tried it.

  • The $r^n$ term will mix in some low frequency components, so if the largest argument is small enough it could be hidden by this term.

$\endgroup$
1
  • $\begingroup$ Thank you, Dan. I'm afraid I don't see how the analog of power method that you've proposed can work here... Is there any mathematical justification of your idea? $\endgroup$
    – faleichik
    Commented May 10, 2012 at 12:23
0
$\begingroup$

If you just want an upper bound, another way of estimating it is to use Gershgorin's circle theorem. You could simply determine the maximum argument of any point on the union of the Gershgorin disks, and this would be guaranteed to be larger than the argument of any of your eigenvalues.

This method has a serious problem, though: if the Gershgorin region contains some neighborhood of the origin, no restrictions on the largest argument of any of your eigenvalues can be derived.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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