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

Question

numpy.linalg.det 的文档指出

The determinant is computed via LU factorization using the LAPACK routine z/dgetrf.

我运行了以下运行时测试并拟合了 2、3 和 4 次多项式，因为它涵盖了 this table 中最差的选项。 .该表还提到 LU 分解方法需要 $O(n^3)$ 时间，但 LU 分解的理论复杂度给定 here是 $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()

上面的输出如下图所示。

由于所有可用的复杂性都不能归结为二次时间，因此从视觉上看，二次模型的拟合最差也就不足为奇了。三次模型和四次模型都具有出色的视觉拟合度，毫不奇怪，它们的残差密切相关。

---

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

• Space complexity of matrix inversion, determinant and adjoint
• Time and space complexity of determinant of a matrix
• Experimentally determining computing complexity of matrix determinant

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

Answer 1

TL;DR:关于目标 BLAS 实现，它介于 O(n^2.81) 和 O(n^3) 之间。

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

朴素 平方矩阵乘法的复杂度为 O(n^3)。存在更快的算法，例如 Strassen (在 ~O(n^2.81) 时间内运行)通常用于大矩阵。 Coppersmith–Winograd 算法实现了明显更好的复杂度 (~O(n^2.38))，但没有线性代数库实际使用它因为这是一个galactic algorithm .简而言之，这种算法在理论上比其他算法渐进地更好，但隐藏常数使其不切实际用于任何真实世界使用。有关矩阵乘法复杂性的更多信息，请阅读 this article .因此，在实践中，关于目标，矩阵乘法的复杂度介于 O(n^2.81) 和 O(n^3) 之间BLAS 实现(取决于您的平台和 Numpy 配置)。