3
$\begingroup$

I have the expression for the inversion of a matrix with the Sherman-Morrison formula as follows (given that $A^{-1}$ is known).

$B^{-1} = A^{-1} + \frac{A^{-1}\mathbf{uv^*}A^{-1}}{1-\mathbf{v^*}A^{-1}\mathbf{u}}$

Now I'm trying to figure out how many FLOPS this would require to calculate. This is what I get from looking at it:

  • one matrix-vector multiplication: $2m^2-m$
  • one vector-matrix multiplication: $2m^2-m$
  • one outer product: $m^2$
  • one Sesquilinear form multiplication ($\mathbf{v^*}A^{-1}u$): $2m^2 +m-1$
  • one subtraction: $1$ and
  • one matrix addition: $m^2$

Totaling $8m^2-m$

But everywhere I look it says that the Sherman-Morrison formula is supposed to be able to be calculated in $\sim3m^2$ FLOPS.

What am I missing here?

  • 1
    True, nobody really takes flops as the be-all and end-all in matters of measuring efficiency, @Thomas. (And data-shuttling can take more time than the arithmetic.) But how are you counting flops? Are you assuming that the explicit $\mathbf A^{-1}$ is being multiplied or (the one used in practice!) are you counting the flops for a backsubstitution from a decomposition of $\mathbf A$?2011-09-02

1 Answers 1

2

First off: you do not solve the Sherman-Morrison-Woodbury formula; the intention of this is to allow one to easily solve a set of linear equations when a rank-1 correction has been applied.

Secondly: it looks to me that you're not exploiting the occurrence of common subexpressions. It might aid you to see the computational savings you might accrue if you write SMW this way:

$(\mathbf A+\mathbf u\mathbf v^T)^{-1}=\mathbf A^{-1}-\frac{\mathbf w(\mathbf A^{-1}\mathbf v)^T}{1-\mathbf v\cdot\mathbf w},\qquad \mathbf w=\mathbf A^{-1}\mathbf u$

So let's see... assuming you have both the decomposed matrix and the inverse available (you do know that explicitly computing the inverse before multiplying to a vector can be unsound to do, yes?), you compute $\mathbf A^{-1}\mathbf u$ and $\mathbf A^{-1}\mathbf v$, take an outer and an inner product... well, you do the flop accounting. :)

  • 0
    Following this and doing the flop accounting I got to $\sim 6m^2$ FLOPS and I just asked my professor about it and he agreed it should be $\sim 6m^2$ FLOPS. The statement I found online that it should take $\sim 3m^2$ FLOPS is most likely related to them just counting the multiplications like stated in the comments on the question.2011-09-07