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?)

  • $\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 Jul 4 '18 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 Jul 4 '18 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 Jul 4 '18 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 Jul 4 '18 at 18:26
  • $\begingroup$ Thank you for the explanation, both of Johan and Pavel! $\endgroup$ – ZelelB Jul 4 '18 at 18:41

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.