加快用于计算矩阵辅因子的python代码 [英] Speed up python code for computing matrix cofactors

问题描述

作为一项复杂任务的一部分，我需要计算矩阵辅助因子 .我使用此用于计算矩阵未成年人的不错的代码以一种直接的方式完成了此任务.这是我的代码:

As part of a complex task, I need to compute matrix cofactors. I did this in a straightforward way using this nice code for computing matrix minors. Here is my code:

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

事实证明，此矩阵辅助因子代码是瓶颈，我想优化上面的代码片段.有关如何执行此操作的任何想法?

It turns out that this matrix cofactor code is the bottleneck, and I would like to optimize the code snippet above. Any ideas as to how to do this?

推荐答案

如果矩阵是可逆的，则辅因子与逆有关:

If your matrix is invertible, the cofactor is related to the inverse:

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

这可以大大提高速度(对于50x50矩阵，约为1000倍).主要原因是根本的:这是O(n^3)算法，而基于次要下位的算法是O(n^5).

This gives large speedups (~ 1000x for 50x50 matrices). The main reason is fundamental: this is an O(n^3) algorithm, whereas the minor-det-based one is O(n^5).

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

This probably means that also for non-invertible matrixes, there is some clever way to calculate the cofactor (i.e., not use the mathematical formula that you use above, but some other equivalent definition).

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

If you stick with the det-based approach, what you can do is the following:

大部分时间似乎都花在了det内部. (请查看 line_profiler 自己进行查找.)您可以尝试通过链接Numpy来加快这一部分的速度.使用英特尔MKL，但除此之外，没有什么可以做的.

The majority of the time seems to be spent inside det. (Check out line_profiler to find this out yourself.) You can try to speed that part up by linking Numpy with the Intel MKL, but other than that, there is not much that can be done.

您可以像这样加快代码的另一部分:

You can speed up the other part of the code like this:

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％至5​​0％的总运行时间，具体取决于矩阵的大小.原始代码具有Python range和列表操作，这比直接切片索引慢.您也可以尝试变得更聪明，只复制实际更改的次要部分---但是，在完成上述更改后，numpy.linalg.det内部已经花费了将近100％的时间，以便进一步优化其他部分没什么意义.

This gains some 10-50% total runtime depending on the size of your matrices. The original code has Python range and list manipulations, which are slower than direct slice indexing. You could try also to be more clever and copy only parts of the minor that actually change --- however, already after the above change, close to 100% of the time is spent inside numpy.linalg.det so that furher optimization of the othe parts does not make so much sense.

这篇关于加快用于计算矩阵辅因子的python代码的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！