Fastest algorithm for computing the determinant of a matrix?

Question

For a research paper, I have been assigned to research the fastest algorithm for computing the determinant of a matrix.

I already know about LU decomposition and Bareiss algorithm which both run in O(n^3), but after doing some digging, it seems there are some algorithms that run somewhere between n^2 and n^3.

This source (see page 113-114) and this source (see page 198) say that an algorithm exists that runs in O(n^2.376) because it is based on the Coppersmith-Winograd's algorithm for multiplying matrices. However, I have not been able to find any details on such an algorithm.

My questions are:

1. What is the fastest created (non-theoretical) algorithm for computing the determinant of a matrix?
2. Where can I find information about this fastest algorithm?

Thanks so much.

Answer 1

I know this is not a direct answer for my question, but for the purposes of completing my research paper, it is enough. I just ended up asking my professor and I will summarize what he said:

Summary:

• The fastest matrix-multiplication algorithms (e.g., Coppersmith-Winograd and more recent improvements) can be used with O(n^~2.376) arithmetic operations, but use heavy mathematical tools and are often impractical.
• LU Decomposition and Bareiss do use O(n^3) operations, but are more practical

In short, even though LU Decomposition and Bareiss are not as fast as the most efficient algorithms, they are more practical and I should focus my research paper on these two.

Thanks for all who commented and helped!

Answer 2

I believe the fastest in practice (and commonly used) algorithm is the Strassen Algorithm. You can find explanation on Wikipedia along with sample C code.

Algorithms based on Coppersmith-Winograd's multiplication algorithms are too complex to be practical, though they have best asymptotic complexity as far.

Answer 3

See the following Matlab test script, which computes determinants of arbitrary square matrices (comparisons to Matlab's built-in function is also included):

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