12

ある研究論文で、行列式を計算するための最速のアルゴリズムを研究するように依頼されました。

O(n^3) で実行されるLU 分解とBareiss アルゴリズムについては既に知っていますが、掘り下げた後、n^2 と n^3 の間のどこかで実行されるアルゴリズムがいくつかあるようです。

この情報源(113 ～ 114 ページを参照) とこの情報源(198 ページを参照) は、O(n^2.376) で実行されるアルゴリズムが存在すると述べています。これは、行列を乗算するための Coppersmith-Winograd のアルゴリズムに基づいているためです。ただし、そのようなアルゴリズムの詳細を見つけることができませんでした。

私の質問は次のとおりです。

  1. 行列式を計算するための最も高速に作成された (非理論的な) アルゴリズムは何ですか?
  2. この最速のアルゴリズムに関する情報はどこにありますか?

本当にありがとう。

4

3 に答える 3

3

これが私の質問に対する直接的な回答ではないことは承知していますが、私の研究論文を完成させるためには、これで十分です。私は教授に尋ねたところ、彼が言ったことを要約します。

概要：

  • 最速の行列乗算アルゴリズム (たとえば、Coppersmith-Winograd や最近の改良) は O(n^~2.376) 算術演算で使用できますが、重い数学ツールを使用するため、多くの場合非現実的です。
  • LU 分解と Bareiss は O(n^3) 演算を使用しますが、より実用的です

要するに、LU 分解と Bareiss は最も効率的なアルゴリズムほど高速ではありませんが、より実用的であり、私の研究論文はこれら 2 つに集中する必要があります。

コメントして助けてくれたすべての人に感謝します！

于 2014-11-19T03:15:44.920 に答える
0

任意の正方行列の行列式を計算する次の Matlab テスト スクリプトを参照してください (Matlab の組み込み関数との比較も含まれています)。

nMin = 2;  % Start with 2-by-2 matrices
nMax = 50; % Quit with 50-by-50 matrices
nTests = 10000;
detsOfL = NaN*zeros(nTests, nMax - nMin + 1);
detsOfA = NaN*zeros(nTests, nMax - nMin + 1);
disp(' ');
for n = nMin:nMax
    tStart = tic;
    for j = 1:nTests
       A = randn(n, n);
       detA1 = det(A); % Matlab's built-in function
       if n == 1
           detsOfL(j, 1) = 1;
           detsOfA(j, 1) = A;
           continue; % Trivial case => Quick return
       end
       [L, U, P] = lu(A);
       PtL = P'*L;
       realEigenvaluesOfPtL = real(eig(PtL));
       if min(prod(realEigenvaluesOfPtL)) < 0 % det(L) is always +1 or -1
           detL = -1;
       else
           detL = 1;
       end
       detU = prod(diag(U));
       detA2 = detL * detU; % Determinant of A using LU decomposition
       if detA1 ~= detA2
           error(['Determinant computation failed at n = ' num2str(n) ', j = ' num2str(j)]);
       end
       detsOfL(j, n - nMin + 1) = detL;
       detsOfA(j, n - nMin + 1) = detA2;
    end
    tElapsed = toc(tStart);
    disp(sprintf('Determinant computation was successful for n = %d!! Elapsed time was %.3f seconds', n, tElapsed));
end
disp(' ');
于 2017-01-12T14:31:31.207 に答える