What is the added cost of generalizing an eigensystem?

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.

• 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.) – Jed Brown Nov 6 '13 at 14:01
• @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. – Max Hutchinson Nov 6 '13 at 16:50