6
$\begingroup$

I have have multiple large matrices for which I need to find the largest absolute eigenvalue. I know that there is a large submatrix that does not vary. Is it possible to ignore/discard the submatrix?

My question is also related to this question: What is the fastest way to calculate the largest eigenvalue of a general matrix?

$\endgroup$
  • 1
    $\begingroup$ I've encountered at least one problem where discarding a submatrix did not affect the spectrum of the matrix (although, of course, it affects the eigenvectors). I am not sure if there are theorems that generalize this observation. $\endgroup$ – Geoff Oxberry Apr 3 '12 at 5:32
3
$\begingroup$

If the part that is unchanged does not cover most of the matrix there is little you can do to save work.

If the part that is unchanged can be permuted by a symmetric permutation to occupy the top left corner of yopur matrix, you can first similarity transform it to (tri)diagonal form. Extending the transform to the whole matrix leaves a matrix of the form $\pmatrix{ T & A\cr B & C}$ with (tri)diagonal $T$, whose eigenvalues are those of the original matrix. Its eigenvalues are relatively cheap to find by some subspace iteration steps followed by inverse iteration for extracting the absolutely largest eigenvalues once reasonable approximations are available.

$\endgroup$
5
$\begingroup$

If you know that the second matrix is only a perturbation of the first, then you can do a perturbation argument. For example, if $\tilde A=A+\delta A$ where $\delta A$ is the difference (and is zero in large parts), then assume that the eigenvectors and eigenvalues also have an expansion $\tilde u_k=u_k+\delta u_k$ and $\tilde \lambda_k = \lambda_k + \delta \lambda_k$.

Let the eigenvalues be order in ascending order, so that $\lambda_N$ is the largest. By definition of the Rayleight quotient, it holds: $$ \lambda_N = \frac{u_N^T A u_N}{u_N^T u_N} $$ and $$ \tilde \lambda_N = \frac{\tilde u_N^T \tilde A \tilde u_N}{\tilde u_N^T \tilde u_N}. $$

If you stick the expansion into this expression, you get $$ \tilde \lambda_N = \lambda_N + \frac{\delta u_N^T A u_N + u_N^T A \delta u_N + \delta u_N^T \delta A u_N}{\tilde u_N^T \tilde u_N} + O(\delta\lambda_N^2). $$

If you happen to know anything about how the eigenvectors may change, you may get something out of this expression about the biggest eigenvalue.

$\endgroup$
  • $\begingroup$ Thanks. However, I don't know how the eigenvectors may change. When you have delta multiplied by A, is it a scalar multiplied by the same matrix A? $\endgroup$ – power Apr 5 '12 at 3:01
  • $\begingroup$ No, $\delta A=\tilde A-A$ is the change in the matrix. From your description, $\delta A$ is going to be a very empty matrix. $\endgroup$ – Wolfgang Bangerth Apr 6 '12 at 4:11

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.