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

Question

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

我已经知道了在O( n^3 )中运行的LU分解和Bareiss算法，但是经过一些挖掘之后，似乎有一些算法运行在n^2和n^3之间。

这个来源 (见第113-114页)和这个来源 (参见第198页)表示，存在一个在O(n^2.376)中运行的算法，因为它是基于Coppersmith Winograd的矩阵乘法算法。不过，我一直未能找到有关这类算法的任何细节。

我的问题是：

1. 计算矩阵行列式的最快(非理论)算法是什么？
2. 在哪里可以找到有关这种最快算法的信息？

非常感谢。

Answer 1

我认为在实践中最快的(也是常用的)算法是Strassen算法。您可以在维基百科和样例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(' ');