3
$\begingroup$

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

2 Answers 2

4

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)

  • 0
    "figures quoted for the other decompositions should be exact" - They are. (Note that I didn't pick on those... ;) )2011-10-19
1

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?