加快计算矩阵辅助因子的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

原来这个矩阵辅因子代码是瓶颈，我想优化上面的代码片段。有什么办法吗？

Answer 1

如果矩阵是可逆的，则辅因子与逆矩阵相关：

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

这会产生较大的加速（50x50矩阵约为1000x）。主要原因是基本的：这是一个O(n^3)算法，而次要的基于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%的总运行时间。原始代码有Pythonrange和列表操作，这比直接切片索引慢。你也可以试着更聪明一些，只复制那些实际改变的小部分——然而，在上述改变之后，几乎100%的时间都花在了numpy.linalg.det里面，所以对其他部分的进一步优化就没有那么多意义了。

Answer 2

np.array(range(row)+range(row+1,nrows))[:,np.newaxis]的计算不依赖于col，因此可以将其移到内部循环之外并缓存该值。根据您拥有的列数，这可能会提供一个小的优化。

Answer 3

from sympy import *
A = Matrix([[1,2,0],[0,3,0],[0,7,1]])
A.adjugate().T

输出（即辅助因子矩阵）为：

Matrix([
[ 3, 0,  0],
[-2, 1, -7],
[ 0, 0,  3]])