python - 加速用于计算矩阵余因子的 python 代码

Question

作为复杂任务的一部分，我需要计算 matrix cofactors .我使用这个 nice code for computing matrix minors 以一种直接的方式做到了这一点.这是我的代码:

def matrix_cofactor(matrix):
    C = np.zeros(matrix.shape)
    nrows, ncols = C.shape
    for row in xrange(nrows):
        for col in xrange(ncols):
            minor = matrix[np.array(range(row)+range(row+1,nrows))[:,np.newaxis],
                           np.array(range(col)+range(col+1,ncols))]
            C[row, col] = (-1)**(row+col) * np.linalg.det(minor)
    return C

原来这个matrix cofactor代码是瓶颈，我想优化一下上面的代码片段。关于如何执行此操作的任何想法？

Answer 1

如果您的矩阵是可逆的，则余因子与逆相关:

def matrix_cofactor(matrix):
    return np.linalg.inv(matrix).T * np.linalg.det(matrix)

这提供了很大的加速(对于 50x50 矩阵大约为 1000 倍)。主要原因是基本的:这是一个 O(n^3) 算法，而基于 minor-det 的算法是 O(n^5)。

这可能意味着对于不可逆矩阵，也有一些聪明的方法来计算余因子(即，不使用上面使用的数学公式，而是使用其他一些等效定义)。

---

如果您坚持使用基于 det 的方法，您可以执行以下操作:

大部分时间似乎都在 det 中度过。 (查看 line_profiler 自己找出答案。)您可以尝试通过将 Numpy 与 Intel MKL 链接来加快该部分的速度，但除此之外，没有什么可以做的了。

您可以像这样加速代码的其他部分:

minor = np.zeros([nrows-1, ncols-1])
for row in xrange(nrows):
    for col in xrange(ncols):
        minor[:row,:col] = matrix[:row,:col]
        minor[row:,:col] = matrix[row+1:,:col]
        minor[:row,col:] = matrix[:row,col+1:]
        minor[row:,col:] = matrix[row+1:,col+1:]
        ...

这会增加 10-50% 的总运行时间，具体取决于矩阵的大小。原始代码有 Python range 和列表操作，比直接切片索引慢。您也可以尝试变得更聪明，只复制实际更改的次要部分 --- 但是，在进行上述更改之后，接近 100% 的时间都花在了 numpy.linalg.det 因此进一步优化其他部分没有多大意义。