numpy.linalg.det 的时间复杂度是多少？

Question

的文档numpy.linalg.det指出

行列式是使用LAPACK例程 z/ dgetrf通过 LU 分解计算的。

我运行了以下运行时测试并拟合了 2、3 和 4 次多项式，因为这涵盖了该表中最不差的选项。该表还提到 LU 分解方法需要 $O(n^3)$ 时间，但此处给出的 LU 分解的理论复杂度为$O(n^{2.376})$。当然，算法的选择很重要，但我不确定我应该期望什么可用的时间复杂度numpy.linalg.det。

from timeit import timeit

import matplotlib.pyplot as plt
import numpy as np
from sklearn.linear_model import LinearRegression
from sklearn.preprocessing import PolynomialFeatures


sizes = np.arange(1,10001, 100)
times = []

for size in sizes:
    A = np.ones((size, size))
    time = timeit('np.linalg.det(A)', globals={'np':np, 'A':A}, number=1)
    times.append(time)
    print(size, time)

sizes = sizes.reshape(-1,1)
times = np.array(times).reshape(-1,1)

quad_sizes = PolynomialFeatures(degree=2).fit_transform(sizes)
quad_times = LinearRegression().fit(quad_sizes, times).predict(quad_sizes)
cubic_sizes = PolynomialFeatures(degree=3).fit_transform(sizes)
cubic_times = LinearRegression().fit(cubic_sizes, times).predict(cubic_sizes)
quartic_sizes = PolynomialFeatures(degree=4).fit_transform(sizes)
quartic_times = LinearRegression().fit(quartic_sizes, times).predict(quartic_sizes)

plt.scatter(sizes, times, label='Data', color='k', alpha=0.5)
plt.plot(sizes, quad_times, label='Quadratic', color='r')
plt.plot(sizes, cubic_times, label='Cubic', color='g')
plt.plot(sizes, quartic_times, label='Quartic', color='b')
plt.xlabel('Matrix Dimension n')
plt.ylabel('Time (seconds)')
plt.legend()
plt.show()

上述的输出如下图所示。

由于所有可用的复杂性都没有达到二次时间，因此我毫不奇怪，视觉上二次模型的拟合最差。三次模型和四次模型都具有出色的视觉拟合效果，并且毫不奇怪，它们的残差密切相关。

---

存在一些相关问题，但他们没有针对这个具体实现的答案。

• 矩阵求逆、行列式和伴随矩阵的空间复杂度
• 矩阵行列式的时间和空间复杂度
• 实验确定矩阵行列式的计算复杂度

由于这个实现被全世界很多Python程序员使用，如果找到答案可能会有助于很多人的理解。

Answer 1

TL;DR：它介于目标 BLAS 实现之间O(n^2.81)并且O(n^3)与目标 BLAS 实现有关。

\n

事实上，Numpy 使用 LU 分解（在对数空间中）。实际的实现可以在这里找到。它确实使用了LAPACK 的sgetrf/dgetrf原语。多个库提供了这样的库。最著名的是 NetLib，尽管它不是最快的。英特尔 MKL 是提供快速实施的库的一个示例。快速 LU 分解算法使用平铺方法，因此在内部使用矩阵乘法。他们这样做是因为矩阵乘法是最优化的方法之一线性代数库（例如 MKL、BLIS 和 OpenBLAS 通常成功地在现代处理器上达到近乎最佳的性能）。更一般地，LU 分解的复杂度是矩阵乘法的复杂度之一。

\n

朴素平方矩阵乘法的复杂度为O(n^3)。存在更快的算法，例如Strassen（及时运行~O(n^2.81)），通常用于大矩阵。Coppersmith \xe2\x80\x93Winograd算法实现了显着更好的复杂度 ( ~O(n^2.38))，但没有线性代数库实际使用它，因为它是一种银河算法。简而言之，这种算法在理论上渐近优于其他算法，但隐藏的常数使其对于任何现实世界的使用都不切实际。有关矩阵乘法的复杂性的更多信息，请阅读这篇文章。因此，在实践中，矩阵乘法的复杂性介于目标 BLAS 实现之间并且与目标 BLAS 实现有关（这取决于您的平台和 Numpy 的配置）。O(n^2.81)O(n^3)

\n