13

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.

Md. Abu Nafee Ibna Zahid
  • 455
  • 1
  • 6
  • 19
John-Luke Laue
  • 3,736
  • 3
  • 32
  • 60

3 Answers3

6

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.

Richard
  • 56,349
  • 34
  • 180
  • 251
Sopel
  • 1,179
  • 1
  • 10
  • 15
  • 3
    It's worth noting that the current bound is `O(n^{2.3728639})` but as Sopel says, it is unlikely that the smaller exponent is worth pursing on a practical computation since they have an _enormous_ constant factor in front. – Hooked Nov 18 '14 at 21:29
  • @Sopel I believe Strassen is used for matrix inversion. see http://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations And as for algorithms based on Coppersmith-Winograd, you are correct - I asked my professor and he said they are the fastest, but are too complex to be practical. Thank you! – John-Luke Laue Nov 19 '14 at 03:17
  • I believe they are very similar problems (I'm concluding it from that Coppersmith-Winograd's algorithm for matrix multiplication can be transformed to calculate determinants), but I don't have a big knowledge about this so I may be wrong. – Sopel Nov 19 '14 at 14:37
  • 4
    Could you explain how a matrix multiplication algorithm can be used to computer determinants? – HelloGoodbye Mar 09 '21 at 02:10
4

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!

John-Luke Laue
  • 3,736
  • 3
  • 32
  • 60
  • 4
    It's a nit, but "LU Decomposition and Bareiss are not as fast" isn't really correct. What you mean is "LU Decomposition and Bareiss are not as fast _asymptotically_". The asymptotically superior algorithms have such high constants in their actual execution time functions, that the "slower" algorithms are faster in practice. For example, 1e6*n is bigger than 0.0001*n^2 for all n < 1e5. – Gene Feb 19 '18 at 07:16
  • You can be more specific and say something like "LU Decomposition and Bareiss are faster than Coppersmith-Winograd to find the determinant of an nxn matrix, when n < some_big_constant". Of course that requires some work to find out the big constant. – Stef Mar 23 '22 at 10:48
0

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(' ');
vnormi75
  • 1
  • 1
    Just dumping code does not an answer make. (0) Did you write this, and what is its licence? If not, where did you get it? Now to actually answer the questions: (1) How is its performance versus others, concretely quantified? (2) What is the info on _how_ it performs so well? – underscore_d Jun 08 '20 at 10:05