Algoritmo più veloce per calcolare il determinante di una matrice?

Question

Per un documento di ricerca, sono stato assegnato alla ricerca l'algoritmo più veloce per calcolare il determinante di una matrice.

so già su decomposizione LU e algoritmo Bareiss che sia eseguito in O (n^3), ma dopo aver fatto qualche scavo, sembra che ci siano alcuni algoritmi che corrono da qualche parte tra n^2 e n^3.

Questo source (vedi pagina 113-114) e questo source (vedi pagina 198) dicono che esiste un algoritmo che viene eseguito in O (n^2.376) perché si basa su un algoritmo del Coppersmith-Winograd per moltiplicare le matrici. Tuttavia, non sono stato in grado di trovare dettagli su tale algoritmo.

Le mie domande sono:

1. Qual è il più veloce creata (non teorico) algoritmo per il calcolo del determinante di una matrice?
2. Dove posso trovare informazioni su questo algoritmo più veloce?

Grazie mille.

Answer 1

Credo che l'algoritmo di pratica più veloce (e comunemente usato) sia lo Strassen Algorithm. Puoi trovare spiegazioni su Wikipedia insieme al codice di esempio C.

Gli algoritmi basati su Coppersmith-Winograd's multiplication algorithms sono troppo complessi per essere pratici, sebbene abbiano la migliore complessità asintotica.

Answer 2

So che questa non è una risposta diretta per la mia domanda, ma ai fini del completamento del mio documento di ricerca, è sufficiente. Ho appena finito col chiedere il mio professore e io riassumere quello che ha detto:

Sommario:

• I più veloci algoritmi di matrice moltiplicazione (ad esempio, Coppersmith-Winograd ei miglioramenti più recenti) può essere utilizzato con O (n^~ 2.376) operazioni aritmetiche, ma usa pesanti strumenti matematici e spesso sono poco pratici.
• LU decomposizione e Bareiss si avvalgono O (n 3 ^) operazioni, ma sono più pratici

In breve, anche se LU decomposizione e Bareiss non sono veloci come gli algoritmi più efficienti, sono più pratici e dovrei concentrare la mia ricerca su questi due.

Grazie per tutti coloro che hanno commentato e aiutato!

Answer 3

vedere il seguente script di test Matlab, che calcola determinanti di matrici quadrate arbitrarie (paragoni per la funzione built-in di Matlab è anche incluso):

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