# Number of FLOPS required to solve Sherman-Morrison formula for matrix inversion

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?

-
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. – Thomas Klimpel Sep 1 '11 at 18:36
@Thomas: more likely, Fredrik just wanted a flop, in the sense of Golub and Van Loan. – J. M. Sep 1 '11 at 23:47
@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. – Thomas Klimpel Sep 2 '11 at 13:50
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$? – J. M. Sep 2 '11 at 15:04

$$(\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. :)
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. – Fredrik Sep 7 '11 at 17:30