12

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.

4

3 回答 3

5

我相信实践中最快的（也是常用的）算法是 Strassen 算法。您可以在Wikipedia上找到解释以及示例 C 代码。

基于Coppersmith-Winograd 乘法算法的算法过于复杂而无法实用，尽管它们具有迄今为止最好的渐近复杂度。

于 2014-11-18T20:43:57.003 回答
3

我知道这不是我问题的直接答案，但为了完成我的研究论文，这就足够了。我刚刚问了我的教授，我将总结他所说的：

概括：

  • 最快的矩阵乘法算法（例如，Coppersmith-Winograd 和最近的改进）可以与 O(n^~2.376) 算术运算一起使用，但使用繁重的数学工具并且通常不切实际。
  • LU Decomposition 和 Bareiss 确实使用 O(n^3) 运算，但更实用

简而言之，尽管 LU Decomposition 和 Bareiss 不如最有效的算法快，但它们更实用，我应该将我的研究论文集中在这两个上。

感谢所有评论和帮助的人！

于 2014-11-19T03:15:44.920 回答
0

请参阅以下 Matlab 测试脚本，该脚本计算任意方阵的行列式（还包括与 Matlab 内置函数的比较）：

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(' ');
于 2017-01-12T14:31:31.207 回答