2
$\begingroup$

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.

$\endgroup$
  • 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$ – Wolfgang Bangerth 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$ – Justin Solomon 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$ – Justin Solomon Nov 17 '16 at 20:25

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.