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 程序员使用,如果找到答案,它可能有助于很多人的理解。
最佳答案
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 配置)。
关于python - numpy.linalg.det 的时间复杂度是多少?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/72206172/