2
$\begingroup$

I heard that subspace iteration plus Ritz acceleration could improve the performance a lot for solving clustered eigenvalues, for the eigenvalues and eigenvectors could converge linearly with ratio $\lambda_{p+1}/\lambda_j$, $j=1,\ldots,p$. For Hermitian Matrix this is even faster.

This is really fantastic. Now for any $n\times n$ Complex Matrix $C$ with sufficient eigenvectors that is not deficit, we can construct an algorithm to make all the eigenvalues be solved in an extremely efficient way:

  1. Add a big number to the diagonal elements to make the eigenvalue large in magnitude.
  2. Add a zero column together with a zero row to make it an $n+1\times n+1$ matrix $C'$.
  3. Modify $C'_{n+1\times n+1}$ with a very small nonzero number.
  4. Use Subspace Iteration Algorithm with $n$ orthogonal $n+1$ dimensional vectors. According to the proof of the Algorithm it should converge very fast, for the first $n$ eigenvalues are respectively huge to the last one.
  5. Subtract the big number to the solved $n$ eigenvalues to get the original ones. Does anyone think it possible?
Improve this question
$\endgroup$
3
  • $\begingroup$ Are you asking for an opinion? $\endgroup$
    – belisarius
    Dec 6, 2013 at 16:00
  • $\begingroup$ Yes. I am thinking to solve the cluster eigenvalue problem. $\endgroup$
    – Zhong
    Dec 6, 2013 at 16:03
  • $\begingroup$ Do you have any reference for this? I am interested in this subject $\endgroup$
    – Sai Venkat
    Dec 13, 2013 at 11:52

2 Answers 2

Reset to default
2
$\begingroup$

My gut instinct says no. Suppose that hypothetically one of the eigenvalues of your original matrix $C$ is $\lambda_k = 1.0$, while with your method you add an artificial eigenvalue $\lambda_{n+1} = 10^{17}$. Using your method, you'll find an eigenvalue $10^{17}+1.0$ for the matrix $C'$ which, in floating point arithmetic, gets rounded to $10^{17}$. You'd then subtract off $10^{17}$ for all the eigenvalues you found for $C'$ and get that $\lambda_1 = 0$, which is pretty far off.

That's an extreme case, but even for the eigenvalues whose magnitudes are not so small compared to $\lambda_{p+1}$, you'll have poor numerical precision. In floating point arithmetic, computing $(a+b)-b$ when $b$ is much larger than $a$ will lose many digits of accuracy, giving you an unstable algorithm.

However, this is just my first guess and I don't have a formal proof for you. It's possible that there's a numerically stable variant of this algorithm (like Gram-Schmidt vs. Householder orthogonalization) or that I'm entirely wrong.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Well, with consideration of roundoff my method sounds unreasonable, yet there are now many softwares supporting multiple or even arbitrary precision such as Mathematica and MPack and GMP. mplapack.sourceforge.net $\endgroup$
    – Zhong
    Dec 8, 2013 at 7:35
  • $\begingroup$ And the transformation is orthogonal and we can also use Householder to tridiagonalize it first. $\endgroup$
    – Zhong
    Dec 8, 2013 at 7:47
1
$\begingroup$

Adding the (decoupled) extra dimension to the vector space cannot possibly help discriminate among the clustered eigenvalues in the original $n$ dimensions. Any subspace iterations you do will maintain the partitioning of the first $n$ dimensions and the last (extra) one dimensional subspace. While the theory tells you that "separation" can rapidly be obtained between a basis for the larger (original) subspace and the small one, you start out with perfect separation, so there's nothing to be gained.

Shifting the spectrum can (and often does) help in separating clustered eigenvalues, but it has to be done more skillfully than just adding an arbitrarily large real number to all eigenvalues. The effect here would be to cluster those eigenvalues together more tightly.

Improve this answer
$\endgroup$
7
  • $\begingroup$ Yet after Ritz acceleration the convergence rate of jth eigenvalue should be $\lambda_{p+1}/\lambda_j$ rather than $\lambda_{j+1}/\lambda_j$, so this is only relevant to the separation between my added eigenvalue and the original clustered ones. The separation of the clustered ones does not matter according to the proof, though it is more tightly. $\endgroup$
    – Zhong
    Dec 9, 2013 at 5:00
  • $\begingroup$ And after I add one eigenvalues I do subspace iteration in n+1 dimension. $\endgroup$
    – Zhong
    Dec 9, 2013 at 5:07
  • $\begingroup$ By $\lambda_j$ you mean the tiny eigenvalue that you artificially added, enlarging $C$ by an extra dimension and introducing a "very small" diagonal entry (Step 3), right? My point is simply that you already know this eigenvalue/eigenvector pair perfectly. Being able to separate it from the clustered ones by subspace iteration does not contribute to separating the clustered ones from each other. $\endgroup$
    – hardmath ♦
    Dec 9, 2013 at 11:05
  • $\begingroup$ Thank you, yet I think I would like to reiterate something to make it more clear. There does exist theorem on estimnating the upper and lower bound of the eigenvalue magnitude/modulus. So for Matrix $C$ we use the bound theroem to estimate the lower bound for its n eigenvalues, and then we extend it into $C$ by adding the (n+1) th small eigenvalue whose modulus is much smaller than that lower bound. Now since for matrix $C'$, we have |$\lambda_1$|>|$\lambda_2$|>...>|$\lambda_n$|>>|$\lambda_{n+1}$|, according to Ritz acceleration theorem, we have $O$(|$\lambda_{n+1}$|/|$\lambda_n$|). $\endgroup$
    – Zhong
    Dec 10, 2013 at 6:24
  • $\begingroup$ and then we extend it to $C’$, by adding n+1 th eigenvalue, not $C$. Sorry there is a wrong sign in the comment above and I can’t change it with my terminal now. $\endgroup$
    – Zhong
    Dec 10, 2013 at 15:43

Your Answer

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

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