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?
$\begingroup$
$\endgroup$
asked Dec 20, 2013 at 6:17
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
5
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}$.
answered Dec 20, 2013 at 6:34
-
$\begingroup$ thank you very much! Is there other formula for
LUdecomposition andHouseholdermethods in solving linear systems? $\endgroup$ Commented Dec 20, 2013 at 6:50 -
$\begingroup$ Additionally, in
Choleskydecomposition, there are at leastntimessquare rootused; how to count such operations? $\endgroup$ Commented 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$ Commented Dec 20, 2013 at 7:24
-
$\begingroup$ thank you very much! Does the conclusion hold even for multiple precision computation via
GMPmultiple precision library? $\endgroup$ Commented 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$ Commented Dec 20, 2013 at 8:21