5
$\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

$\endgroup$

2 Answers 2

Reset to default
5
$\begingroup$

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)

$\endgroup$
5
  • 1
    $\begingroup$ 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... $\endgroup$
    – J. M. ain't a mathematician
    Oct 19, 2011 at 0:13
  • 1
    $\begingroup$ 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. $\endgroup$
    – Jay Lemmon
    Oct 19, 2011 at 0:56
  • $\begingroup$ "while you can't get an exact figure for the FLOPs " - that was kind of my point, actually. $\endgroup$
    – J. M. ain't a mathematician
    Oct 19, 2011 at 0:57
  • $\begingroup$ Then yeah, I agree that's true for SVD. The figures quoted for the other decompositions should be exact, though. $\endgroup$
    – Jay Lemmon
    Oct 19, 2011 at 1:02
  • $\begingroup$ "figures quoted for the other decompositions should be exact" - They are. (Note that I didn't pick on those... ;) ) $\endgroup$
    – J. M. ain't a mathematician
    Oct 19, 2011 at 1:03
1
$\begingroup$

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?

$\endgroup$

You must log in to answer this question.