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.
$\begingroup$
$\endgroup$
Add a comment
|
$\begingroup$
$\endgroup$
2
@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$.
answered Dec 15 '13 at 21:39
-
1$\begingroup$ I posted the long form of the comment as answer: By increasing the eigenvalues and thus reducing their relative distance, the proposed forward iteration may converge significantly slower than the inverse iteration. This may even out the initial cost of the inverse iteration, or most likely be in total somewhat faster. $\endgroup$ – Lutz Lehmann Dec 15 '13 at 22:45
-
$\begingroup$ Yes, that's a valid point. You may want to choose $\bar\lambda$ just large enough that the largest positive eigenvalue is significantly smaller by magnitude than $\lambda_\text{min}-\bar\lambda$. $\endgroup$ – Wolfgang Bangerth Dec 16 '13 at 6:38
$\begingroup$
$\endgroup$
2
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.
-
$\begingroup$ Instead of decomposing the matrix, we can do a least squares estimation of $A^{-1}x$ at every iteration by using some sort of a gradient descent method. $\endgroup$ – nojka_kruva Dec 16 '13 at 9:21
-
$\begingroup$ For efficient CG you need to apply a pre-conditioner first. This may not end up with a tridiagonal matrix, but depending on the matrix type, it can come close. $\endgroup$ – Lutz Lehmann Dec 16 '13 at 10:10
$\begingroup$
$\endgroup$
4
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$.
-
$\begingroup$ Alternatively, you can apply power iteration to find the maximum eigenvalue of $-A$, which is also the maximum negative eigenvalue of A. $\endgroup$ – Paul♦ Dec 15 '13 at 20:56
-
2$\begingroup$ @Paul's solution will only work if the most negative eigenvalue is also the one with the largest magnitude. $\endgroup$ – Wolfgang Bangerth Dec 15 '13 at 21:36
-
$\begingroup$ @WolfgangBangerth: you're right! For some reason, i thought it might work in the general case too. But power method does converge to the largest magnitude eigenvalue, regardless of sign. $\endgroup$ – Paul♦ Dec 19 '13 at 18:48
-
