2
$\begingroup$

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?

$\endgroup$

1 Answer 1

3
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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