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 need exact computational costs for different algorithms to benchmark a code. For instance, the exact cost of Gauss Elimination is given here. I am not interested just in the leading order term.

The algorithms for which I need the exact cost are:

  1. SVD
  2. QR
  3. LU
  4. Cholesky

Any help would be greatly appreciated

share|improve this question
add comment

2 Answers

I'll address #1 only; given that the (modified) QR algorithm used in finding the singular values and singular vectors of a bidiagonal matrix is inherently iterative; it's hard to give an exact count of the effort needed to compute the decomposition. It depends a great deal on the singular value distribution, among other things.

For the others... why not do the arithmetic explicitly?

share|improve this answer
add comment

All computations expressed in terms of your $mxn$ matrix ($m$ rows, $n$ columns) and stolen from the book "Numerical Linear Algebra" by Trefethen and Bau.

  1. I'm not so sure about the SVD. The book gives numbers of $2mn^2 + 11n^3$ on page 84, but in lecture 31 it gives $4mn^2 - \frac{4}{3}n^3$ as the cost of phase 1 using "Golub-Kahn". (Phase 1 is supposed to dominate the total running time). From memory I thought $11n^3$ sounded familiar.

  2. QR decomposition using Householder transformations: $2mn^2-\frac{2}{3}n^3$ FLOPs, or $\frac{4}{3} n^3$ for square matrices. (Page 75).

  3. LU Decomposition: $\frac{2}{3}n^3$ (page 152).

  4. Cholesky: half the work of LU: $\frac{1}{3}n^3$ (page 82)

share|improve this answer
    
SVD is a two stage algorithm: the first part is finite (reduction to bidiagonal form), and you can certainly count flops for that (the actual count depending on the bidiagonalization method used). The second part, which is performing the decomposition via Golub-Kahan, is iterative (it is a repurposed QR algorithm after all), and the effort will be quite dependent on the distribution of singular values. The count also depends on whether you're computing all the (left and right) singular vectors in addition to the singular values, or only some of them... –  J. M. Oct 19 '11 at 0:13
    
Yeah, but according to the book, since phase 2 converges to machine epsilon in a finite number of iterations, "Phase 2 requires $O(n^2)$ flops all together. Thus, although Phase 1 is finite and Phase 2 is in principle infinite, in practice the latter is much less expensive." (page 236). The $O(n^3)$ from phase 1 should swamp out the $O(n^2)$ cost in phase 2, so while you can't get an exact figure for the FLOPs you should be able to get a very reasonable estimate, and at least be able to compare its expense vs. other decompositions, which seems to be the OP's purpose. –  Jay Lemmon Oct 19 '11 at 0:56
    
"while you can't get an exact figure for the FLOPs " - that was kind of my point, actually. –  J. M. Oct 19 '11 at 0:57
    
Then yeah, I agree that's true for SVD. The figures quoted for the other decompositions should be exact, though. –  Jay Lemmon Oct 19 '11 at 1:02
    
"figures quoted for the other decompositions should be exact" - They are. (Note that I didn't pick on those... ;) ) –  J. M. Oct 19 '11 at 1:03
add comment

Your Answer

 
discard

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