कक्षा के लिए फास्ट स्पैर मैट्रिक्स गुणा

Question

मुझे स्पैर मैट्रिस के लिए अपना खुद का रैखिक समीकरण सॉल्वर लिखना है। मैं स्पैर मैट्रिस के लिए किसी भी प्रकार की डेटा संरचना का उपयोग करने के लिए स्वतंत्र हूं और मुझे कंजुगेट ग्रेडिएंट सहित कई हलकों को लागू करना है।

मैं सोच रहा था कि स्पैर मैट्रिक्स को स्टोर करने का एक प्रसिद्ध तरीका है, जैसे वेक्टर के साथ गुणा अपेक्षाकृत तेज़ है।

अभी मेरे स्पैर मैट्रिस मूल रूप से एक लपेटा std::map< std::pair<int, int>, double> लागू किया गया है जो डेटा को स्टोर करता है, यदि कोई हो। यह वेक्टर से ओ (एन²) जटिलता के साथ एक ओ (n²log (n)) के साथ एक मैट्रिक्स के गुणा को बदलता है क्योंकि मुझे प्रत्येक मैट्रिक्स तत्वों के लिए लुक-अप करना होता है। मैंने येल स्पैर्स मैट्रिक्स प्रारूप में देखा है और ऐसा लगता है कि किसी तत्व का पुनर्प्राप्ति ओ (लॉग (एन)) में भी है, इसलिए मुझे यकीन नहीं है कि यह बहुत तेज़ होगा।

संदर्भ के लिए मेरे पास 800x800 मैट्रिक्स है जो 5000 प्रविष्टियों के साथ पॉप्युलेट किया गया है। Conjugate ढाल विधि के साथ इस तरह के एक प्रणाली को हल करने में लगभग 450 सेकंड लगते हैं।

क्या आपको लगता है कि यह किसी अन्य डेटा संरचना के साथ बहुत तेज़ करना संभव है?

धन्यवाद!

Answer 1

सबसे आम विकल्प CSC or CSR storage हैं। ये मैट्रिक्स-वेक्टर गुणा के लिए दोनों कुशल हैं। यदि आपको इसे स्वयं करना है तो उन गुणात्मक दिनचर्या को कोड करना भी बहुत आसान है।

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

यहां तक ​​कि आपके वर्तमान भंडारण के साथ आप ओ (एन) जटिलता में मैट्रिक्स गुणा प्रदर्शन कर सकते हैं। सभी स्पैर मैट्रिक्स-वेक्टर गुणा एल्गोरिदम जिन्हें मैंने कभी भी एक ही चरण में उबाल दिया है। उदाहरण के लिए वाई = एक्स पर विचार करें।

1. परिणाम वेक्टर शून्य, शून्य।
2. मैट्रिक्स के गैर शून्य तत्वों के लिए एक इटरेटर Initialise, ए
3. मैट्रिक्स की अगली गैर शून्य तत्व जाओ, एक [i, j] का कहना है। ध्यान दें कि i, j का पैटर्न नियमित पैटर्न का पालन नहीं करता है। यह बस उस क्रम को प्रतिबिंबित करता है जिसमें ए के गैर-शून्य तत्व संग्रहीत किए जाते हैं।
4. y [i] + = एक [i, j] * एक्स [जे]
5. अगर वहाँ एक के और अधिक तत्व हैं, गोटो 3.

मुझे लगता है कि आप पाश के लिए क्लासिक डबल लिख रहे हैं घने गुणा कोड:

for (i=0; i<N; i++) 
    for (j=0; j<N; j++) 
     y[i] += A[i,j]*x[j] 

और वह है क्या अग्रणी है आप लुकअप प्रदर्शन करने के लिए है।

लेकिन मैं यह सुझाव नहीं दे रहा हूं कि आप अपने std::map संग्रहण के साथ चिपके रहें। यह सुपर कुशल नहीं होने वाला है। मैं मुख्य रूप से सीएससी की सिफारिश करता हूं क्योंकि यह सबसे व्यापक रूप से उपयोग किया जाता है।