4
$\begingroup$

Problem

Let's say I can write a model as the Hermitian eigensystem: $$ A x = \lambda x $$ where $A \in \mathbb{C}^{n\times n}$ is Hermitian, or as the generalized Hermitian eigensystem: $$ \tilde A \tilde x = \lambda \tilde B \tilde x $$ where $\tilde A, \tilde B \in \mathbb{C}^{\tilde n \times \tilde n}$ are Hermitian and $\tilde B$ is positive definite. How much smaller must $\tilde n$ be than $n$ for the generalized model to be more efficient?

Qualifications

I understand that there are many other factors that influence the answer. A general intuition would be best, but, if added complexity is unavoidable, assume:

  • Serial solver
  • Direct solver
  • $A,\tilde A, \tilde B$ are dense
  • The $m$ eigen-pairs with lowest eigenvalues are desired, where $n / m \approx 10$
  • $A$ and $\tilde A, \tilde B$ model the same system, so the relative differences in the $m$ eigen-pairs are small
  • $\tilde B = I + \hat{B}$ where $\text{rank}(\hat{B}) = p$, and $p \approx 2 m = n/5$

Answers for a different set of qualifications might be useful to other readers as well.

Improve this question
$\endgroup$
5
  • $\begingroup$ Which eigenpairs do you want? Does $\tilde B$ have structure (sparsity, a kernel, etc)? How does the spectrum of the two formulations compare? (This affects which algorithm will be used.) $\endgroup$
    – Jed Brown
    Nov 6, 2013 at 14:01
  • $\begingroup$ @JedBrown low-eigenvalue eigen-pairs. $\tilde B - I$ is not full rank, but it is not quite low rank and is dense. The spectrum's should be almost the same. Edited qualifications accordingly. $\endgroup$
    – Max Hutchinson
    Nov 6, 2013 at 16:50
  • $\begingroup$ How concentrated is the spectrum of $A$ (or $\tilde B^{-1/2} \tilde A \tilde B^{-1/2}) near the origin? Have you compared the cost of solving using a shift-and-invert spectral transform? (Internal eigenvalues are hard, but extreme eigenvalues, even near zero, can often be found quickly without needing to invert.) $\endgroup$
    – Jed Brown
    Nov 6, 2013 at 20:28
  • $\begingroup$ In my particular case, the spectrum is approximately linear, $\lambda_n \in [(n-1) \omega,(n+1)\omega] + E_o$, but allowing for some degeneracy and with somewhat arbitrary shift $E_o$ (positive or negative). I will look into shift-and-invert. $\endgroup$
    – Max Hutchinson
    Nov 7, 2013 at 15:24
  • $\begingroup$ This is the pretty nicely-separated scenario where a standard diagonal shift is likely sufficient. You probably don't need shift-and-invert. $\endgroup$
    – Jed Brown
    Nov 7, 2013 at 23:16

1 Answer 1

Reset to default
3
$\begingroup$

For a dense, direct solver, Golub and Van Loan (Matrix Computations, 3rd ed) report the following cost estimates for eigenvalues only:

  • standard eigenproblem: $10n^3$ (p. 359).

  • generalized eigenproblem: $30n^3$ (p. 385).

Costs are in flops (additions and multiplications cost $1$ each).

If you want eigenvectors as well, you have to compute the orthogonal matrix in the Schur decomposition (or either $Q$ or $Z$ in QZ, respectively) as well and then you can obtain them using inverse iteration. Costs are not explicitly reported in GVL, but my guess is the following (for $m$ eigenvectors out of $n$, I am assuming one step of inverse iteration ($n^2$) on the triangular matrix is enough, and then multiplication by the orthogonal matrix ($2n^2$)):

  • standard eigenproblem: $25n^3 + 3n^2m$

  • generalized eigenproblem: $46n^3+3n^2m$.

All these figures are approximate because they assume a "typical average" number of shifted QR/QZ steps.

If it's a sparse eigenproblem or it's larger than it fits in RAM, I doubt you can get realistical a priori estimates (but I am a dense guy, so I might be wrong).

Improve this answer
$\endgroup$
1
  • $\begingroup$ Let me add that in practice, unless you write your own code for eigenvector extraction, standard methods will only compute either all ($m=n$) or no eigenvectors. $\endgroup$
    – Federico Poloni
    Nov 7, 2013 at 9:11

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.