加速计算矩阵辅因子的 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 矩阵约为 1000 倍）。主要原因是根本性的：这是一个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 因此其他部分的进一步优化没有多大意义。

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]])

Answer 4

我建议使用 SVD，而不是使用逆矩阵和行列式

def cofactors(A):
    U,sigma,Vt = np.linalg.svd(A)
    N = len(sigma)
    g = np.tile(sigma,N)
    g[::(N+1)] = 1
    G = np.diag(-(-1)**N*np.product(np.reshape(g,(N,N)),1)) 
    return U @ G @ Vt