8
$\begingroup$

I found these information about computation-time of following decompositions:

  1. Cholesky: (1/3)*n^3 + O(n^2) --> So computation-time is O(n^3)
  2. LU: 2*(n^3/3) --> So computation-time is O(n^3) also (not sure)
  3. QR: (2/3)*n^3 + n^2 + (1/3)*n- 2 --> So computation-time is O(n^3) as well

But what I found in other documents says that Cholesky is the fastest among these three algorithms, then comes LU, and last (slowest) is QR.

How we see here, in the formulas above? (or are my formulas wrong?)

$\endgroup$
5
  • $\begingroup$ They are all cubic in asymptotic complexity, but Cholesky has the smallest coefficient, so in what sense is the statement about Cholesky being fastest in any sense problematic in this context? $\endgroup$
    – Johan Löfberg
    Commented Jul 4, 2018 at 14:55
  • $\begingroup$ Oh okay I see. So the coefficient is relevant too. And in the case LU vs QR? They both have the same coefficient as well.. How is LU faster than QR? $\endgroup$
    – ZelelB
    Commented Jul 4, 2018 at 15:18
  • $\begingroup$ If you count all operations (namely $+,-,*,/$), then all algorithms are $\alpha n^3+O(n^2)$, where $\alpha=1/3$ for Cholesky, $\alpha=2/3$ for LU, and $\alpha=4/3$ for Householder. If you count only multiplication and division (which is usually much more expensive than addition or subtraction), the coefficients get halved. $\endgroup$
    – Algebraic Pavel
    Commented Jul 4, 2018 at 17:18
  • $\begingroup$ The coefficient is absolutely important in practice. Cubic means effort is 8 times larger when you double $n$, but whether is goes from 1 second to 8 seconds or from 1 hour to 8 hours is of course crucially important. $\endgroup$
    – Johan Löfberg
    Commented Jul 4, 2018 at 18:26
  • $\begingroup$ Thank you for the explanation, both of Johan and Pavel! $\endgroup$
    – ZelelB
    Commented Jul 4, 2018 at 18:41

1 Answer 1

Reset to default
10
$\begingroup$

Nick Higham's book "Functions of Matrices Theory and Computation" has a nice summary of the computation costs that he scraped from Golub and van Loan's "Matrix Computations" book that summarizes the constant costs. Do note, this all makes assumptions on how we want to value different operations, which are not all the same:

Cost of Factorizations

Anyway, it's easier to see why certain factorizations are faster than others.

$\endgroup$
1
  • $\begingroup$ Sharing this table is excellent. Nice work! $\endgroup$
    – jvdillon
    Commented Apr 7, 2020 at 16:10

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .