计算矩阵行列式的最快算法

Question

对于一篇研究论文，我被指派研究计算矩阵行列式的最快算法。

我已经知道LU分解和Bareiss算法，它们都在O（n^3）中运行，但是经过一些挖掘，似乎有一些算法运行在n^2和n^3之间。

这个来源（

见第113-114页）和这个来源（见第198页）说存在一种在O（n^2.376）中运行的算法，因为它是基于Coppersmith-Winograd的矩阵相乘算法。但是，我无法找到有关此类算法的任何详细信息。

我的问题是：

1. 用于计算矩阵行列式的最快创建（非理论）算法是什么？
2. 在哪里可以找到有关此最快算法的信息？

非常感谢。

Answer 1

我相信

实践中最快的（也是常用的）算法是斯特拉森算法。您可以在维基百科上找到解释以及示例 C 代码。

基于Coppersmith-Winograd乘法算法的算法过于复杂而不实用，尽管到目前为止它们具有最好的渐近复杂性。

Answer 2

我知道

这不是我问题的直接答案，但为了完成我的研究论文，这就足够了。我最后问了我的教授，我将总结一下他说的话：

总结：

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

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

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

Answer 3

请参阅以下 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(' ');