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

From Numerical Linear Algebra by Trefethen and Bau, page 175, it seems that the formula is

\begin{align} \sum_{k=1}^{n}\sum_{j = k + 1}^{n} (2(n - j + 1) + 1). \end{align}

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
• @LCFactorization: It is likely to hold; the conjecture could be tested to leading order by plotting the logarithm of execution time of a Cholesky factorization versus the logarithm of the size of the square, positive definite matrix. I suspect that precision effects also play a role, as the preferred multiplication algorithms used by GMP will likely change depending upon the number of digits used in your multiple precision computation. – Geoff Oxberry Dec 20 '13 at 8:21