加速用于计算矩阵辅助因子的python代码

Question

作为复杂任务的一部分,我需要计算矩阵辅助因子.我使用这个漂亮的代码计算矩阵未成年人,以一种简单的方式做到了这一点.这是我的代码:

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

事实证明,这个矩阵辅助因子代码是瓶颈,我想优化上面的代码片段.关于如何做到这一点的任何想法？

Answer 1

如果你的矩阵是可逆的,那么辅助因子与逆矩阵有关:

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

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

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

如果您坚持使用基于det的方法,您可以做的是以下内容:

大部分时间似乎都花在了里面det.(查看line_profiler自己找出这个.)你可以尝试通过将Numpy与英特尔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,以便优化其他部分的优化不会使太有道理了.