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?

  • 0
    FLOPS (floating point operations per second) is a measure of a computer's performance. You don't measure the performance of an algorithm in FLOPS. So I guess that the Sherman-Morrison formula is supposed to take $\approx 3m^2$ multiplications, not FLOPS.2011-09-01
  • 0
    @Thomas: more likely, Fredrik just wanted a *flop*, [in the sense of Golub and Van Loan](http://books.google.com/books?id=mlOa7wPX6OYC&pg=PA18).2011-09-01
  • 1
    @J.M. But with this definition, already $\mathbf{A^{-1}u}$ and $\mathbf{v^*A^{-1}}$ will take $\sim4m^2$ "flop"s. The number $\sim3m^2$ makes most sense when counting just the multiplications. And I also think that the number of multiplication is a good "abstract" effort measure. A "flop" is not necessarily a more accurate "practical" measure, since the number of "load"s and "store"s is often more important than the number of additions.2011-09-02
  • 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