Define $S\in\mathbb{R}^{n\times n}$ as $$S:=H+Q^\top V^{-1} Q.$$ $H,V$ are positive semidefinite. Here, $H$, $Q$, and $V$ are large, dense matrices but they are structured: I can write code for matrix-vector products (e.g. $x\mapsto Hx$) but computing $V^{-1}$ or the map $x\mapsto V^{-1}x$ would require iteration.

Given a sparse, symmetric, positive definite matrix $M$, what is the best way to find the $k$ smallest eigenvalues of $S$ satisfying $Sx=\lambda Mx$?

Note that this problem is equivalent to the expanded generalized eigenvalue problem $$ \begin{pmatrix} H &Q^\top\\Q & -V \end{pmatrix} \begin{pmatrix} x \\ z \end{pmatrix} = \lambda \begin{pmatrix} M & 0 \\ 0 & 0 \end{pmatrix} \begin{pmatrix} x \\ z \end{pmatrix}, $$ where $z$ is an auxiliary variable. This is nice because it's symmetric and does not contain $V^{-1}$, so I was hoping to use machinery for generalized eigenvalues. But the right-hand side of this generalized problem is not invertible, which seems to prevent the use of usual eigenvalue iteration.

  • 2
    $\begingroup$ What about solving the for the inverse eigenvalues $Mx = (1/\lambda) Sx$? $\endgroup$
    – nicoguaro
    Nov 16 '16 at 22:11
  • $\begingroup$ Indeed. You already know that zero is not an eigenvalue of $S$, so there is no downside to turning the problem around. $\endgroup$ Nov 17 '16 at 3:26
  • $\begingroup$ There are two reasons. One is that I don't know that zero isn't an eigenvalue of $S$ (in fact in my application I know that it is, but probably not with much multiplicity). Here, $H$ and $V$ are only semidefinite. But the more pertinent reason is that solving the problem you suggest requires inverse iteration, so, I'd have to invert $S$ in every step. This is itself an expensive iterative process. It seems we should be able to do this with only one "for loop." $\endgroup$ Nov 17 '16 at 13:26
  • $\begingroup$ Hi Justin. If V is not too huge, you may try to pre-factorize it, and you may be able to exploit its structure to pre-factorize it. How is it structured ? Another possibility is factorizing the right-hand side matrix in your expanded generalized eigenvalue problem (using LDLt factorization). $\endgroup$
    – BrunoLevy
    Nov 17 '16 at 18:08
  • $\begingroup$ Hi Bruno! Thanks for the idea :-) . Sadly, we're constructing $V$ using boundary PDE methods where we never actually write down its elements (e.g. fast multipole). All we can do is matrix-vector products, which are usually enough for eigenvalue problems, but not here it appears. We can invert $M$, for what it's worth -- can even think of $M$ as diagonal. $\endgroup$ Nov 17 '16 at 20:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.