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

Question

numpy.linalg.det 的文档指出

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

我运行以下运行时间测试和拟合 2、3 和 4 次多项式，因为它涵盖了这个 table 中最差的选项。 table 还提到 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()

上面的输出如下图所示。

由于 none 可用的复杂性下降到二次时间，我并不奇怪视觉上二次模型的拟合最差。三次模型和四次模型都具有出色的视觉拟合度，毫不奇怪，它们的残差密切相关。

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

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

朴素平方矩阵乘法的复杂度为 O(n^3)。存在更快的算法，例如 Strassen (running in ~O(n^2.81) time) which is often used for big matrices. The Coppersmith–Winograd algorithm achieves a significantly better complexity (~O(n^2.38)), but no linear algebra libraries actually use it since it is a galactic algorithm. Put it shortly, such algorithm is theoretically asymptotically better than others but the hidden constant make it impractical for any real-world usage. For more information about the complexity of the matrix multiplication, please read this article。因此，在实践中，矩阵乘法的复杂性在 O(n^2.81) 和 O(n^3) 之间关于目标 BLAS 实现（这取决于您的平台和您的配置麻木）。

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

What is the time complexity of numpy.linalg.det?

python

numpy

linear-algebra

time-complexity

determinants