Temporary complexity of Cholesky decomposition for LDL form

Question

There are two different forms for Cholesky Decomposition :

A = M * ctranspose (M) 

and LDL form

 A = L * D * ctranspose (L) 

where ctranspose is a complex transposition.

I want to know the number of floating point operations for each form . Wikipedia cited a Matrix Inversion article using Cholesky Decomposition , which states

With effective implementation, the complexity of LDL decomposition is the same (sic) as Cholesky decomposition.

The document says that Cholesky decomposition requires operations n^3/6 + O(n^2) 3/6 n^3/6 + O(n^2) . However, Wikipedia states that the number of floating point operations is n^3/3 , and my own calculation also gets this for the first form. This basically comes down to the sum of the numbers of triangles, which:

 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 point product. These are 2 * n floating point operations in total. Therefore, floating-point operations must 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] . These are 3 * n floating-point operations (2 multiplications and 1 addition). Thus, floating point operations must be n^3/2 + O(n^2) .

In other words, an LDL form requires more than 50% floating point operations. Am I right? I think the article is incorrect (although they do not determine what they mean operation). This is important because I am implementing a modified Choleksy Decomposition form based on the LDL form, and I want to evaluate the effectiveness of my algorithm.

Perhaps this question is more suitable for https://math.stackexchange.com/

Answer 1

This statement addresses the overall complexity of Cholesky’s decomposition, including (implementing) the inverse square root, and this is what remains of the section that details the entire algorithm on the DSP. Now I see that from the context the statement is misleading. Thus, to calculate the term in brackets (in the document), LDL requires more operations than Cholesky decomposition (the operation is a complex MAC).