math - LDL 形式的 Cholesky 分解的时间复杂度

Question

Cholesky Decomposition 有两种不同的形式:

A = M * ctranspose (M)

和 LDL 形式

A = L * D * ctranspose (L)

其中 ctranspose 是复数转置。

我想知道每种形式的浮点运算次数。维基百科引用了一篇论文 Matrix Inversion Using Cholesky Decomposition上面写着

When efficiently implemented, the complexity of the LDL decomposition is same (sic) as Cholesky decomposition.

论文说 Cholesky 分解需要 n^3/6 + O(n^2) 操作。然而，维基百科说浮点运算的数量是 n^3/3 并且我自己的计算得到了第一种形式。它基本上归结为三角形数字的总和:

n*(n+1)*(n+2)/6.  

这就是我认为论文得到 n^3/6 的地方。但是对于第一种形式，最里面的三重和中的项是 a[i][k]*a[j][k]，它基本上是一个点积。那是总和中的 2*n 个浮点运算。所以浮点指针操作应该是n^3/3 + O(n^2)。如果您查看 LDL 形式，最内层总和中的项是 a[i][k]*a[j][k]*d[k]。那是 3*n 浮点指针操作(2 次乘法和 1 次加法)。所以浮点运算应该是n^3/2 + O(n^2)。

换句话说，LDL 形式需要多 50% 的浮点运算。 我说得对吗？我认为这篇论文是错误的(尽管他们没有定义他们的内容指的是一个操作)。这很重要，因为我正在实现一种基于 LDL 形式的 Choleksy 分解的修改形式，并且我想估计我的算法的效率。

也许这个问题更适合https://math.stackexchange.com/

Answer 1

该陈述考虑了 Cholesky 分解的整体复杂性，包括平方根反比(的实现)，并且是在 DSP 上详细介绍整个算法的部分的剩余内容。

我现在确实看到断章取意的说法是误导性的。因此，要计算括号内的项(在论文中)，LDL 需要比 Cholesky 分解更多的操作(操作是复杂的 MAC)。