Najszybszy algorytm obliczania wyznacznika macierzy?

Question

W celu napisania pracy badawczej zlecono mi badanie najszybszego algorytmu obliczania wyznacznika macierzy.

już wiem o LU dekompozycji i Bareiss algorytm który zarówno przebieg w czasie O (n^3), ale po jakiejś kopania, wydaje się, istnieją pewne algorytmy, które działają gdzieś pomiędzy n^2 i N^3.

to source (patrz strona 113-114) i ten source (strona 198), że istnieje algorytm, który działa w O (N^2,376), ponieważ opiera się na algorytmie kotlarz-Winograd za mnożenie macierzy. Jednak nie byłem w stanie znaleźć żadnych szczegółów na temat takiego algorytmu.

Moje pytania są następujące:

1. Jaki jest najszybszy stworzony (nie teoretyczne) algorytm do obliczania wyznacznika macierzy?
2. Gdzie mogę znaleźć informacje o tym najszybszym algorytmie?

Dziękuję bardzo.

Answer 1

Uważam, że najszybszym w praktyce (i najczęściej używanym) algorytmem jest algorytm Strassena. Możesz znaleźć wyjaśnienie na Wikipedia wraz z przykładowym kodem C.

Algorytmy oparte na Coppersmith-Winograd's multiplication algorithms są zbyt złożone, aby mogły być praktyczne, chociaż mają jak największą asymptotyczną złożoność.

Answer 2

Wiem, że to nie jest bezpośrednia odpowiedź na moje pytanie, ale do celów wypełnienia mojego artykułu badawczego wystarczy. Właśnie zakończył się pytaniem mojego profesora i będę podsumować to, co powiedział:

Podsumowanie:

• najszybszych algorytmów matrycę mnożenia (np Coppersmith-Winograd i nowsze ulepszenia) może być używany z O (n^~ 2,376) operacje arytmetyczne, ale używają ciężkich narzędzi matematycznych i często są niepraktyczne.
• LU rozkładu i Bareiss nie korzysta O (N^3) operacji, ale są bardziej praktyczne

Podsumowując, chociaż LU rozkładu i Bareiss nie tak szybko, jak najbardziej efektywne algorytmy są bardziej praktyczne i powinienem skoncentrować się na moich badaniach na tych dwóch sprawach.

Dziękuję wszystkim, którzy skomentowali i pomogli!

Answer 3

Zobacz poniższy skrypt testowy Matlab, który oblicza wyznaczniki dowolnych macierzy kwadratowych (porównań funkcją wbudowaną w MATLAB jest również w zestawie):

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