加速計算矩陣輔助因子的Python代碼

作爲複雜任務的一部分，我需要計算matrix cofactors。我使用這個nice code for computing matrix minors以直接的方式完成了這項工作。這裏是我的代碼：加速計算矩陣輔助因子的Python代碼

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

事實證明，這種基質輔助因子代碼是瓶頸，我想優化上面的代碼段。任何想法如何做到這一點？

來源

2011-06-29 Jeff O' Neill

一般的瓶頸殺手是用C寫瓶頸。這裏有一些技術人員嗎？ – Evpok

小心闡述爲什麼你需要計算'輔助因子'？是否有可能避免它，並試圖找到一個更直接的解決你的問題？即使有下面那些'糟糕的'建議，在靠近這樣的加速時你也不會得到什麼，當從'合適的角度'解釋問題時（如果可能的話）可能是可能的。謝謝 – eat

@eat，不可能避免它們。在這裏解釋太複雜了...... –

如果你的矩陣是可逆的，輔因子相關的逆：

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

這使得大的加速（〜1000倍的50×50矩陣）。主要原因是基本的：這是一個O(n^3)算法，而基於次要的算法是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之內，以便其他部分的更好優化不會非常有意義。

來源

2011-06-29 22:31:48

優秀的答案！我的矩陣是可逆的，所以一個班輪是一個巨大的節省時間。 –

這將計算伴隨矩陣，而不是輔助因子矩陣。 det（A）* inverse（A）= adjoint（A） – avmohan

@ v3ga：請實際閱讀答案。它計算'det（A）* inverse（A）^ T'。輔助因子是輔助者的轉置。 –

np.array(range(row)+range(row+1,nrows))[:,np.newaxis]的計算不取決於col，因此您可以將其移到內部循環外部並緩存該值。根據列的數量，可能會給出一個小的優化。

來源

2011-06-29 21:50:26 borrible

加速計算矩陣輔助因子的Python代碼

回答

相關問題