मैट्रिक्स cofactors कंप्यूटिंग के लिए पायथन कोड गति

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 

ऐसा लगता है कि इस मैट्रिक्स cofactor कोड टोंटी है, और मैं इसके बाद के संस्करण कोड स्निपेट अनुकूलन करना चाहते हैं: यहाँ मेरी कोड है। ऐसा करने के लिए कोई विचार क्या है?

Answer 1

यदि आपका मैट्रिक्स उलटी है, सहायक कारक के प्रतिलोम से संबंधित है:

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

इस बड़े speedups (~ 1000x 50x50 के लिए मैट्रिक्स) देता है। मुख्य कारण मौलिक है: यह O(n^3) एल्गोरिदम है, जबकि मामूली-पृथक एक O(n^5) है।

इसका शायद यह अर्थ है कि गैर-परिवर्तनीय मैट्रिक्स के लिए भी, कोफैक्टर की गणना करने के लिए कुछ चालाक तरीका है (यानी, ऊपर वर्णित गणितीय सूत्र का उपयोग न करें, लेकिन कुछ अन्य समकक्ष परिभाषा)।

---

आप det आधारित दृष्टिकोण के साथ चिपके रहते हैं, तो आप क्या कर सकते है निम्नलिखित:

समय के बहुमत det अंदर खर्च किया जा रहा है। (इसे स्वयं ढूंढने के लिए line_profiler देखें।) आप इंटेल एमकेएल के साथ नम्पी को जोड़कर उस हिस्से को गति देने की कोशिश कर सकते हैं, लेकिन इसके अलावा, ऐसा नहीं किया जा सकता है।

आप इस तरह कोड के अन्य भाग में तेजी लाने के कर सकते हैं:

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% कुल रनटाइम अपने मैट्रिक्स के आकार के आधार। मूल कोड में पायथन range और सूची मैनिपुलेशन हैं, जो प्रत्यक्ष स्लाइस इंडेक्सिंग से धीमे होते हैं। आप अधिक चालाक होने की कोशिश कर सकते हैं और नाबालिग के केवल कुछ हिस्सों की प्रतिलिपि बना सकते हैं जो वास्तव में बदलते हैं --- हालांकि, उपर्युक्त परिवर्तन के बाद ही, numpy.linalg.det के अंदर 100% समय व्यतीत किया जाता है ताकि अन्य भागों का बेहतर अनुकूलन न हो बहुत समझदारी करो।

Answer 2

np.array(range(row)+range(row+1,nrows))[:,np.newaxis] की गणना col पर निर्भर नहीं है ताकि आप आंतरिक लूप के बाहर उसे स्थानांतरित कर सकें और मूल्य को कैश कर सकें। आपके पास कॉलम की संख्या के आधार पर यह एक छोटा अनुकूलन दे सकता है।