Time complexity of Cholesky Decomposition for the LDL form
-
04-07-2023 - |
Question
There are two different forms for Cholesky Decomposition:
A = M * ctranspose (M)
and the LDL form
A = L * D * ctranspose (L)
where ctranspose is the complex transpose.
I want to know the number of floating point operations for each form. Wikipedia references a paper Matrix Inversion Using Cholesky Decomposition which says
When efficiently implemented, the complexity of the LDL decomposition is same (sic) as Cholesky decomposition.
The paper says Cholesky decomposition requires n^3/6 + O(n^2)
operations. However, Wikipedia says the number of floating point operations is n^3/3
and my own calculation gets that as well for the first form. It basically comes down to the sum of triangle numbers which is:
n*(n+1)*(n+2)/6.
That's where I think the paper gets n^3/6
. But for the first form the term in the inner most triple sum is a[i][k]*a[j][k]
which is basically a dot product. That's 2*n floating point operations in the sum. So the floating pointer operations should be n^3/3 + O(n^2)
. And if you look at the LDL form the term in the innermost sum is a[i][k]*a[j][k]*d[k]
. That's 3*n floating pointer operations (2 multiplications and 1 addition). So the floating point operations should ben^3/2 + O(n^2)
.
In other words the LDL form needs 50% more floating point operations. Am I correct? I think the paper is wrong (though they don't define what they mean by an operation). This is important because I'm implementing a modified form of Choleksy Decomposition based on the LDL form and I want to estimate the efficiency of my algorithm.
Maybe this question is more suitable for https://math.stackexchange.com/
Solution