Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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
add comment

1 Answer

up vote 2 down vote accepted

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. :)

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.