Is there an efficient way to find the largest negative eigenvalue of a matrix? The matrix in question is a Markov matrix.
Computing the full spectrum of the matrix by decomposing it is not an acceptable solution.
Computational Science Stack Exchange is a question and answer site for scientists using computers to solve scientific problems. It only takes a minute to sign up.
Sign up to join this communityIs there an efficient way to find the largest negative eigenvalue of a matrix? The matrix in question is a Markov matrix.
Computing the full spectrum of the matrix by decomposing it is not an acceptable solution.
@VictorMay has provided an answer using the inverse power iteration, but this is of course expensive. If you have an estimate that $\bar\lambda > \lambda_i$, i.e., it is an upper bound to all eigenvalues including the positive ones, then $A-\bar\lambda I$ is a negative definite matrix. You can then apply the power iteration (instead of the inverse power iteration) to finding the largest eigenvalue by magnitude. Call it $\mu$. Since the matrix is negative definite, you then know that the most negative eigenvalue of $A$ is $\lambda_\text{min}=-\mu+\bar\lambda$.
While the inverse power iteration requires an initial matrix decomposition of any sensible type, which requires $O(n^3)$ operations, the following vector iterations are $O(n^2)$ like the forward power iteration.
For example, to make this initial step overly complicated, one may start with a transformation to Hessenberg form, use Gerschgorin circles to locate the eigenvalues and then modify the diagonal, since $Q^TAQ+cI=Q^T(A+cI)Q$. Then factor the resulting tridiagonal matrix.
The expense in initial cost may be justified by faster convergence. The forward iterate converges linearly with factor
$$q_D=\frac{|\lambda_2|+\bar\lambda}{|\lambda_1|+\bar\lambda}=1-\frac{|\lambda_1|-|\lambda_2|}{|\lambda_1|+\bar\lambda}$$,
where $\lambda_1<\lambda_2<\lambda_k$ are the smallest and second smallest eigenvalues.
The inverse power iteration with only the initial shift converges with factor
$$q_I=\frac{\bar\lambda-|\lambda_1|}{\bar\lambda-|\lambda_2|}=1-\frac{|\lambda_1|-|\lambda_2|}{\bar\lambda-|\lambda_2|}$$,
which because of the structurally smaller denominator will be smaller than $q_D$. One only needs an advantage of $O(n)$ iteration that the inverse PIu uses less to justify the initial costs.
Here is one solution: Add $\|A\|_{inf}$ to the diagonal elements of $A$. Compute the smallest eigenvalue of the resulting matrix using inverse power iterations. Subtract $\|A\|_{inf}$ from the resulting eigenvalue to get the largest negative eigenvalue of $A$.