# What is the fomula of polynomial time of solving positive definite symmetric linear system

For a positive definite symmetric linear system, Cholesky decomposition based method should be the best solver which has a rough n^3/3 flops requirement.

What is the fomula of flops including n^2, n items? Is there any such reference?

Eyeballing it, it seems to agree with the formula given by Boyd in his convex optimization notes: $(1/3)n^{3} + 2n^{2}$.
• thank you very much! Is there other formula for LU decomposition and Householder methods in solving linear systems? – LCFactorization Dec 20 '13 at 6:50
• Additionally, in Cholesky decomposition, there are at least n times square root used; how to count such operations? – LCFactorization Dec 20 '13 at 6:55
• A square root will cost as much as a fixed multiple of floating point additions or multiplications, so it's still $O(n)$ of course. For even moderately large matrices, the $O(n^2)$ and $O(n^3)$ terms dominate, so whatever is linear in $n$ is not important and the exact factor in front of the linear term doesn't matter. – Wolfgang Bangerth Dec 20 '13 at 7:24
• thank you very much! Does the conclusion hold even for multiple precision computation via GMP multiple precision library? – LCFactorization Dec 20 '13 at 7:33