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}$.

  • $\begingroup$ thank you very much! Is there other formula for LU decomposition and Householder methods in solving linear systems? $\endgroup$ – LCFactorization Dec 20 '13 at 6:50
  • $\begingroup$ Additionally, in Cholesky decomposition, there are at least n times square root used; how to count such operations? $\endgroup$ – LCFactorization Dec 20 '13 at 6:55
  • 1
    $\begingroup$ 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. $\endgroup$ – Wolfgang Bangerth Dec 20 '13 at 7:24
  • $\begingroup$ thank you very much! Does the conclusion hold even for multiple precision computation via GMP multiple precision library? $\endgroup$ – LCFactorization Dec 20 '13 at 7:33
  • 1
    $\begingroup$ @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. $\endgroup$ – Geoff Oxberry Dec 20 '13 at 8:21

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.