Exact Computational Costs/Flop count for algorithms 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:


*

*SVD

*QR

*LU

*Cholesky


Any help would be greatly appreciated
 A: 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.


*

*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.

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

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

*Cholesky: half the work of LU: $\frac{1}{3}n^3$ (page 82)
A: 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?
