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

numpy.linalg.det个州的文件显示

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

我运行了以下运行时测试，并拟合了2、3和4度多项式，因为这涵盖了this table个最差选项中最差的选项.该表还提到，LU分解方法需要花费$O(n^3)$时间，但给出here的LU分解的理论复杂性是$O(n^2.376)$.当然，算法的 Select 很重要，但我不确定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程序员都在使用这种实现，如果能够找到答案，可能会有助于许多人的理解.