The fastest matrix determinant calculation algorithm?

Question

For research work, I have been instructed to investigate the fastest algorithm for calculating the determinant of a matrix.

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

This source (see p. 113-114) and this source (see p. 198) say that there is an algorithm that works in O (n ^ 2.376) because it is based on the Coppersmith-Winograd algorithm for matrix multiplication . However, I could not find any details about such an algorithm.

My questions:

• What is the fastest (not theoretical) algorithm for calculating the determinant of a matrix?
• Where can I find information about this fastest algorithm?

Thank you very much.

Answer 1

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

Algorithms based on Coppersmith-Winograd Multiplication Algorithms are too complex to be practical, although they have the best asymptotic complexity.

Answer 2

I know that this is not a direct answer to my question, but this is enough to complete my research work. 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 later improvements) can be used with O arithmetic operations (n ​​^ ~ 2.376), 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, although LU Decomposition and Bareiss are not as fast as the most efficient algorithms, they are more practical, and I have to focus my research on these two.

Thanks to everyone who commented and helped!

Answer 3

See the following Matlab test script, which computes the determinants of arbitrary square matrices (comparisons to the built-in Matlab function are 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 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(' ');