Schnellster Algorithmus zur Berechnung der Determinante einer Matrix?

Question

Für eine Forschungsarbeit wurde ich beauftragt, den schnellsten Algorithmus zur Berechnung der Determinante einer Matrix zu untersuchen.

Ich weiß schon über LU-Zerlegung und Bareiss Algorithmus, die beide laufen in O (n^3), aber nach einigen graben tun, es scheint, dass es einige Algorithmen sind, die irgendwo zwischen n^2 und n Run^3.

Dieses source (siehe Seite 113-114) und dieses source (siehe Seite 198) sagt, dass ein Algorithmus existiert, läuft in O (n^2,376), weil es zum Multiplizieren Matrix auf der Schmied-Winograd-Algorithmus basiert. Ich konnte jedoch keine Details zu einem solchen Algorithmus finden.

Meine Fragen sind:

1. Was der schnellsten erstellt (nicht-theoretische) Algorithmus zur Berechnung der Determinante einer Matrix ist?
2. Wo finde ich Informationen zu diesem schnellsten Algorithmus?

Vielen Dank.

Answer 1

Ich glaube, der schnellste in der Praxis (und häufig verwendete) Algorithmus ist der Strassen-Algorithmus. Sie können die Erklärung zu Wikipedia zusammen mit Beispiel-C-Code finden.

Algorithmen basierend auf Coppersmith-Winograd's multiplication algorithms sind zu komplex, um praktisch zu sein, obwohl sie die beste asymptotische Komplexität haben.

Answer 2

Ich weiß, dass dies keine direkte Antwort auf meine Frage ist, aber für die Zwecke meiner Abschlussarbeit reicht es. ich gerade zu Ende gegangen meinem Professor zu fragen, und ich werde zusammenfassen, was er sagte:

Zusammenfassung:

• Die schnellste Matrix-Multiplikation Algorithmen (zB Kupferschmiede-Winograd und neuere Verbesserungen) mit O verwendet werden (n^~ 2.376) arithmetische Operationen, verwenden aber schwere mathematische Werkzeuge und sind oft unpraktisch.
• LU Zerlegung und Bareiss do O verwenden (n^3) Operationen, sind aber praktisch

Kurz gesagt, obwohl LU Zerlegung und Bareiss sind nicht so schnell wie die effizientesten Algorithmen sind sie praktischer und ich sollte meine Forschungsarbeit auf diese beiden konzentrieren.

Danke für alle, die kommentiert und geholfen haben!

Answer 3

Siehe folgende Matlab Testskript, die Determinanten von beliebigen quadratische Matrizen berechnet (Vergleiche mit Matlab eingebauten Funktion ist ebenfalls enthalten):

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(' ');