# What is the computation time of LU-, Cholesky and QR-decomposition?

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

• 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? – Johan Löfberg Jul 4 '18 at 14:55
• 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? – ZelelB Jul 4 '18 at 15:18
• 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. – Algebraic Pavel Jul 4 '18 at 17:18
• 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. – Johan Löfberg Jul 4 '18 at 18:26
• Thank you for the explanation, both of Johan and Pavel! – ZelelB Jul 4 '18 at 18:41

## 1 Answer

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: Anyway, it's easier to see why certain factorizations are faster than others.