コレスキー分解には 2 つの異なる形式があります。
A = M * ctranspose (M)
および LDL フォーム
A = L * D * ctranspose (L)
ここで、ctranspose は複素転置です。
フォームごとの浮動小数点演算回数を知りたい。ウィキペディアは、コレスキー分解を使用した行列反転という論文を参照しています。
効率的に実装された場合、LDL 分解の複雑さはコレスキー分解と同じです (原文のまま)。
この論文によると、コレスキー分解には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 形式に基づいて修正された形式のコレクシー分解を実装しており、アルゴリズムの効率を推定したいので、これは重要です。