2

Suppose $A$ is a matrix and that we want to apply inverse iteration with a shift of $\mu$.

The inverse iteration method usually involves solving a linear system $(A-\mu I)w=v_{k-1}$ to obtain the $k$-th iterate, $v_k=w/\Vert w \Vert$.

Now, I understand there can be reasons why we can't compute the inverse $B:=(A-\mu I)^{-1}$ directly, but wouldn't we want to precompute $B$ and simply apply the power method on $B$ if possible? (Every source I've come across seems to only mention linear solve, never precomputing the inverse.)

Thanks!

user2978125
  • 349
  • 1
    Note that rather than solving $(A-\mu I) w =v_{k-1}$ from scratch at each iteration, we would typically construct an LU factorization of $(A-\mu I)$ and use it to solve the equations in each iteration. The factorization is more likely to be sparse than the inverse. – Brian Borchers Jan 11 '23 at 15:42
  • As per my reply below, I had somehow missed that w gets updated each iteration. But thank you for your comment, this is a good point! – user2978125 Jan 13 '23 at 17:55

1 Answers1

2

Briefly, it is not economical to precompute $B$.

Suppose that $A$ is an $n$-by-$n$ matrix. Precomputing $B$ is identical to solving $n$ linear systems. If the shift $\mu$ is sufficiently close to an eigenvalue of $A$, then we expect the power method to converge using far less than $n$ iterations. Since every iteration of the power method consists of a single linear solve and a normalization, we cannot improve the time-to-solution by precomputing $B$.

The power method and it generalization, the subspace iteration, are often applied when $A$ is large and sparse with $O(n)$ nonzero entries. Frequently $n$ is so large, that we do not have $n^2$ words of memory and storing $B$ is out of the question.

Carl Christian
  • 12,583
  • 1
  • 14
  • 37