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

Question

为了一篇研究论文，我被分配研究计算矩阵行列式的最快算法。

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

这source (参见第 113-114 页)和这个 source (请参阅第 198 页)说存在一种算法，其运行时间为 O(n^2.376)，因为它基于 Coppersmith-Winograd 的矩阵乘法算法。但是，我无法找到有关此类算法的任何详细信息。

我的问题是:

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

非常感谢。

Answer 1

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

算法基于Coppersmith-Winograd's multiplication algorithms太复杂而不实用，尽管它们具有迄今为止最好的渐近复杂性。