2
$\begingroup$

I have a (complex) $n\times n$ positive semidefinite matrix $Q$, need to find its smallest eigenvalue, and want to know the most computationally efficient method of doing so. It would be nice if the method is also stable against round-off errors, but my main interest at the moment is in efficiency. There are methods that find all eigenvalues and eigenvectors, such as transforming to tridiagonal form and then using QR/QL decomposition, but all I need is this one eigenvalue so am hoping there is something more efficient.

In general terms, I want to know if the nullspace of $Q$ is empty, and if so, how 'close' it is to being non-empty, that distance being 'measured' by the size of that smallest eigenvalue. (We can assume that $Tr(Q)=1$.)

P.S. A reference would also be much appreciated, if available.

$\endgroup$
  • $\begingroup$ You don't need eigenvalues for that problem. Rank revealing decomposition may be what you need $\endgroup$ – uranix Nov 24 '16 at 20:56
2
$\begingroup$

Look up "inverse power iteration", it finds the eigenvalue with smallest absolute value.

The sequence $v,A^{-1}v,A^{-2}v,…$ converges linearly towards the eigenvector of the smallest eigenvalue with a speed that is the ration of the two smallest eigenvalues. $v$ should be random enough to not be orthogonal to the searched for eigenspace.

$\endgroup$
  • 2
    $\begingroup$ Rayleigh quotient iteration is probably a better choice since we know that the matrix is symmetric $\endgroup$ – Omnomnomnom Nov 23 '16 at 17:15
  • $\begingroup$ @Omnomnomnom RQI converges to some eigenvalue, not necessary the smallest one. In practice, you cannot tell whether the obtained eigenvalue is the smallest one. $\endgroup$ – uranix Nov 24 '16 at 20:55

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.