त्रिभुज/स्पैस भंडारण के लिए numpy मैट्रिक्स गुणा?

Question

मैं एक बहुत बड़े स्पैर मैट्रिक्स गुणा (matmul) समस्या के साथ काम कर रहा हूँ। उदाहरण के तौर पर मान लें:

• ए एक बाइनरी (75 x 200,000) मैट्रिक्स है। यह स्पैस है, इसलिए मैं स्टोरेज के लिए सीएससी का उपयोग कर रहा हूं।

• बी = A.transpose() * एक

• उत्पादन आकार 200Kx200K का एक विरल और सममित मैट्रिक्स होने जा रहा है: मैं निम्नलिखित matmul आपरेशन करने की जरूरत है।

दुर्भाग्य से, बी तरह से रैम में स्टोर करने के लिए बड़े (या "कोर में") अपने लैपटॉप पर करने के लिए होने जा रहा है। दूसरी ओर, मैं भाग्यशाली हूं क्योंकि बी के कुछ गुण हैं जो इस समस्या को हल करना चाहिए।

चूंकि बी विकर्ण और स्पैस के साथ सममित होने वाला है, इसलिए मैटुल ऑपरेशन के परिणामों को संग्रहीत करने के लिए मैं त्रिकोणीय मैट्रिक्स (ऊपरी/निचला) का उपयोग कर सकता हूं और एक स्पैर मैट्रिक्स स्टोरेज प्रारूप आकार को और कम कर सकता है।

मेरा प्रश्न है ... समय से पहले, क्या आउटपुट स्टोरेज आवश्यकताएं दिखने जा रही हैं, ताकि मैं numpy का उपयोग करके स्टोरेज समाधान का चयन कर सकूं और "मैट्रिक्स बहुत बड़ा" से बच सकूं। गणना के कई मिनट (घंटे) के बाद रनटाइम त्रुटि?

दूसरे शब्दों में, मैट्रिक्स के लिए भंडारण आवश्यकताओं को अनुमानित गिनती एल्गोरिदम का उपयोग करके दो इनपुट मैट्रिक्स की सामग्री का विश्लेषण करके गुणा किया जा सकता है?

• https://en.wikipedia.org/wiki/Approximate_counting_algorithm

यदि नहीं, तो मैं एक जानवर बल समाधान में देख रहा हूँ। नक्शा/कम करने, आउट-ऑफ-कोर भंडारण, या निम्न वेब लिंक से एक matmul उपखंड समाधान (strassens एल्गोरिथ्म) से जुड़ी कोई भी:

एक जोड़े मानचित्र/कम समस्या उपखंड समाधान

• http://www.norstad.org/matrix-multiply/index.html
• http://bpgergo.blogspot.com/2011/08/matrix-multiplication-in-python.html

एक आउट-ऑफ-कोर (PyTables) भंडारण समाधान

• Very large matrices using Python and NumPy

एक matmul उपखंड समाधान:

• https://en.wikipedia.org/wiki/Strassen_algorithm
• http://facultyfp.salisbury.edu/taanastasio/COSC490/Fall03/Lectures/FoxMM/example.pdf
• http://eli.thegreenplace.net/2012/01/16/python-parallelizing-cpu-bound-tasks-with-multiprocessing/

धन्यवाद अग्रिम में कोई सुझाव, टिप्पणियाँ, या मार्गदर्शन के लिए!

Answer 1

चूंकि आप अपने ट्रांसपोज़र के साथ मैट्रिक्स के उत्पाद के बाद हैं, तो [m, n] पर मूल्य मूल रूप से आपके मूल मैट्रिक्स में कॉलम m और n के डॉट उत्पाद होने जा रहा है।

मैं एक खिलौना उदाहरण

a = np.array([[0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1], 
       [0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0], 
       [0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1]]) 
>>> np.dot(a.T, a) 
array([[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 
     [0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0], 
     [0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1], 
     [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 
     [0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1], 
     [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 
     [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 
     [0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0], 
     [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 
     [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 
     [0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0], 
     [0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 2]]) 

यह आकार (3, 12) की है और 7 गैर शून्य प्रविष्टियों के रूप में निम्नलिखित मैट्रिक्स का उपयोग करने के लिए जा रहा हूँ। इसके साथ इसका स्थानांतरण करने का उत्पाद आकार (12, 12) के आकार का है और इसमें 16 गैर-शून्य प्रविष्टियां हैं, जिनमें से 6 विकर्ण में हैं, इसलिए इसे केवल 11 तत्वों के संग्रहण की आवश्यकता है।

आप कर सकते हैं कि आपके उत्पादन मैट्रिक्स का आकार दो तरीकों में से एक में होने जा रहा है की एक अच्छा विचार मिलता है:

सीएसआर प्रारूप

अपने मूल मैट्रिक्स C गैर शून्य कॉलम है , आपके नए मैट्रिक्स में C**2 गैर-शून्य प्रविष्टियां होंगी, जिनमें से C विकर्ण में हैं, और इन्हें शून्य नहीं होने का आश्वासन दिया जाता है, और शेष प्रविष्टियों में से केवल आपको आधा रखने की आवश्यकता होती है, इसलिए यह (C**2 + C)/2 गैर- शून्य तत्व बेशक, इनमें से कई शून्य भी होंगे, इसलिए यह शायद एक सकल अतिवृद्धि है।

यदि आपका मैट्रिक्स csr प्रारूप में संग्रहीत किया जाता है, तो इसी scipy वस्तु की indices विशेषता सभी गैर शून्य तत्वों के स्तंभ सूचकांक के साथ एक सरणी है, तो आप आसानी से के रूप में ऊपर अनुमान की गणना कर सकते हैं:

>>> a_csr = scipy.sparse.csr_matrix(a) 
>>> a_csr.indices 
array([ 2, 11, 1, 7, 10, 4, 11]) 
>>> np.unique(a_csr.indices).shape[0] 
6 

तो वहाँ गैर शून्य प्रविष्टियों के साथ 6 स्तंभ हैं, और इसलिए अनुमान पर सबसे 36 गैर शून्य प्रविष्टियों, जिस तरह से वास्तविक 16.

सीएससी प्रारूप से अधिक के लिए किया जाएगा

यदि गैर-शून्य तत्वों के कॉलम इंडेक्स के बजाय हमारे पास पंक्ति सूचकांक हैं, तो हम वास्तव में एक बेहतर अनुमान कर सकते हैं। दो कॉलम के डॉट उत्पाद के लिए गैर-शून्य होने के लिए, उनके पास एक ही पंक्ति में एक गैर-शून्य तत्व होना चाहिए। यदि किसी दिए गए पंक्ति में R गैर-शून्य तत्व हैं, तो वे R**2 उत्पाद में गैर-शून्य तत्वों का योगदान देंगे। जब आप सभी पंक्तियों के लिए यह योग करते हैं, तो आप कुछ तत्वों को एक से अधिक बार गिनने के लिए बाध्य होते हैं, इसलिए यह भी ऊपरी बाउंड है।

अपने मैट्रिक्स के गैर शून्य तत्वों की पंक्ति सूचकों एक विरल सीएससी मैट्रिक्स के indices विशेषता में हैं, इसलिए इस अनुमान की गणना इस प्रकार किया जा सकता है:

>>> a_csc = scipy.sparse.csc_matrix(a) 
>>> a_csc.indices 
array([1, 0, 2, 1, 1, 0, 2]) 
>>> rows, where = np.unique(a_csc.indices, return_inverse=True) 
>>> where = np.bincount(where) 
>>> rows 
array([0, 1, 2]) 
>>> where 
array([2, 3, 2]) 
>>> np.sum(where**2) 
17 

यह रफ़ू असली के करीब है 16! और यह वास्तव में एक संयोग नहीं है कि यह अनुमान वास्तव में रूप में ही है नहीं है:

def estimate(a) : 
    a_csc = scipy.sparse.csc_matrix(a) 
    _, where = np.unique(a_csc.indices, return_inverse=True) 
    where = np.bincount(where) 
    return np.sum(where**2) 

def test(shape=(10,1000), count=100) : 
    a = np.zeros(np.prod(shape), dtype=int) 
    a[np.random.randint(np.prod(shape), size=count)] = 1 
    print 'a non-zero = {0}'.format(np.sum(a)) 
    a = a.reshape(shape) 
    print 'a.T * a non-zero = {0}'.format(np.flatnonzero(np.dot(a.T, 
                   a)).shape[0]) 
    print 'csc estimate = {0}'.format(estimate(a)) 

>>> test(count=100) 
a non-zero = 100 
a.T * a non-zero = 1065 
csc estimate = 1072 
>>> test(count=200) 
a non-zero = 199 
a.T * a non-zero = 4056 
csc estimate = 4079 
>>> test(count=50) 
a non-zero = 50 
a.T * a non-zero = 293 
csc estimate = 294