3
$\begingroup$

I want the eigenvalues of the following generalized eigenvalue problem: $$ Av = \lambda M v $$ where

  • $A\in\mathbb{R}^{n\times n}$ is sparse, symmetric, and positive semi-definite

  • $M\in\mathbb{R}^{n\times n}$ is sparse, symmetric, and indefinite (i.e. neither positive nor negative definite)

I want the eigenvalues $\lambda$ with the smallest absolute value, i.e. $|\lambda|$ closest to zero.

My problem is that I am using scipy and in particular scipy.sparse.linalg.eigsh. (Note that I have to use Python, but not necessarily scipy, if someone knows a better library.) In this case, eigsh forces me to use the buckling option, since $M$ is indefinite. However, the buckling mode sorts based on eigenvalues transformed via: $$ \widetilde{\lambda} = \frac{\lambda}{\lambda - \sigma} $$ where $\sigma$ is a user-defined constant. Unfortunately, I can't figure out how to get the eigenvalues with smallest magnitude from this. If I choose $\sigma$ to be large, then ask eigsh for the smallest magnitude (i.e. option SM), it is too slow. Slightly better is using the option BE, which returns values from both ends of the spectrum, with a small $\sigma$ close to zero. However, there's no reason to believe the smallest eigenvalues are equally distributed between positive and negative.

Does anyone have any advice for dealing with getting the smallest magnitude eigenvalues from a generalized symmetric eigenvalue problem where the mass matrix is indefinite?

(As a separate note, I have to add $\xi I$ to $A$, and then subtract $\xi$ from $\lambda$ at the end (for small $\xi$), so that it goes from positive semi-definite to positive definite, as required by buckling mode. I am aware that this is not an exact correction for the generalized eigenproblem as it is for the simpler case, but I could not find a better alternative so far, and it doesn't seem to be a big issue. I've asked a related question here, specific to this aspect.)

EDIT (091018): I needed some preliminary results and it seems like the following works, but certainly may not be optimal in terms of speed. Simply solve $M^{-1}Av=\lambda v$ instead using eigs. The trick to making it fast is using prefactorizations (i.e. sparse LUs) to make computing $M^{-1}A$ and $A^{-1}M$ fast. I'd love to know more about potentially better ways to do this!

|cite|improve this question
$\endgroup$
  • 2
    $\begingroup$ Do you know the nullspace of A? $\endgroup$ – user7440 Sep 9 '18 at 23:54
  • 1
    $\begingroup$ One could try to compute the largest eigenvalue in magnitude for the pencil (M, A). Matrix A now plays the role of the "mass" matrix and 'eigsh' accepts a positive semi-definite "mass" matrix, as long as a shift sigma is specified. (So the buckling mode is avoided). $\endgroup$ – user7440 Sep 10 '18 at 5:11
  • $\begingroup$ @user7440 Thanks for your interest! For the nullspace question, I am not sure how easy it is to get it, e.g. using sparse SVD? For your second comment, are you saying to solve $Mv=\lambda Av$ using the normal mode shift inversion to get the largest magnitude eigenvalues (e.g. LM mode with sigma=0)? Does this "inverse" system really have the reciprocal eigenvalues? $\endgroup$ – user3658307 Sep 10 '18 at 17:10
  • 1
    $\begingroup$ Sometimes, you might know the nullspace of A from purely physical considerations (eg the nullspace of the gradient operator is all-ones, or the nullspace of the curl operator is the span of all gradients). You could use such knowledge to suppress/regularize out the nullspace and obtain a positive operator for A. $\endgroup$ – rchilton1980 Sep 10 '18 at 17:30
  • 1
    $\begingroup$ As user7440 pointed out, pencils/eigenproblems can sometimes be driven in either direction, depending upon what part of the spectrum you're seeking and which 'side' is easier to eliminate. For example, if you just power iterate $M^{-1}A$ you'll obtain the large $\lambda$'s, while if you power iterate $A^{-1}M$ you'll obtain the small ones. In the latter case, you'd like to speed up the solution process $A^{-1}$, either by building (i) a good preconditioner or (ii) a direct solver. Knowing the nullspace of $A$ would probably be required for either (i) or (ii). $\endgroup$ – rchilton1980 Sep 10 '18 at 19:43

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.