LDL形式的Cholesky分解的时间复杂度 [英] Time complexity of Cholesky Decomposition for the LDL form

问题描述

胆汁分解有两种不同形式:

A = M * ctranspose (M)

和LDL表格

A = L * D * ctranspose (L)

其中ctranspose是复杂的转置.

where ctranspose is the complex transpose.

我想知道每种表单的浮点运算次数. Wikipedia引用了使用Cholesky分解进行矩阵求逆

I want to know the number of floating point operations for each form. Wikipedia references a paper Matrix Inversion Using Cholesky Decomposition which says

有效实施后，LDL分解的复杂性与Cholesky分解相同.

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，而我自己的计算也可以用第一种形式得到.它基本上可以归结为三角形数之和:

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.  

那是我认为论文得到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).

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).

换句话说，LDL表单需要更多的浮点运算50％. 我正确吗?我认为本文是错误的(尽管它们没有定义它们的含义)指操作).这很重要，因为我正在基于LDL形式实现改进的Choleksy分解形式，并且我想估计算法的效率.

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.

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

推荐答案

该语句考虑了Cholesky分解的整体复杂性，包括反平方根(的实现)，这是详细说明DSP上整个算法的部分所剩下的内容.

That statement considers the overall complexity of Cholesky decomposition including (an implementation of) inverse square root, and is what is left of a section that detailed the whole algorithm on a DSP.

这篇关于LDL形式的Cholesky分解的时间复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！