स्पैर मैट्रिक्स

Question

के साथ वर्गबद्ध रूप मैट्रिक्स गुणा के लिए एल्गोरिदम मैं कोड को अनुकूलित कर रहा हूं जो कस्टम कस्टम मैट्रिक्स लाइब्रेरी पर निर्भर करता है (जिसे परियोजना से बाहर नहीं रखा जाएगा क्योंकि यह हर जगह है। यह अच्छा नहीं है, लेकिन यह एक तथ्य है। ..) कई गणना 10-20 पंक्तियों और स्तंभों की मैट्रिक्स के साथ किया जाता है, कई संगणना की तरह

C = A*B*A' 

एक द्विघात रूप में शामिल हैं मैंने महसूस किया कि अक्सर एक विरल है और मैं इस तथ्य का उपयोग करना चाहते हैं। तो मैं एक एल्गोरिदम की तलाश में हूं जो इस मामले को संभालेगा। संख्यात्मक स्थिरता महत्वपूर्ण है। क्या मैं कुछ भी उपयोग कर सकता हूं? (मैंने अपनी लाइब्रेरी नहीं लिखी है, इसलिए मुझे नहीं पता कि मुझे कोई नुकसान है या नहीं?)

"हमारी" सरल ओ (एन^3) गुणा विधि के रूप में Eigen 3 पर तेजी से निष्पादित करता है लक्ष्य मंच, क्योंकि मुझे संख्यात्मक स्थिरता की आवश्यकता है और मैट्रिस बहुत बड़े नहीं हैं, मुझे लगता है कि स्ट्रैसेन के एल्गोरिदम के साथ-साथ कॉपरस्मिथ-विनोग्राड एल्गोरिदम मैं जो भी ढूंढ रहा हूं वह नहीं है। इसके बजाए यह केवल एक वर्गबद्ध रूप गुणा है जिस तरह से मुझे ए

किसी भी सुझाव के लिए धन्यवाद में आसानी से शून्य की जांच करने देता है!

Answer 1

तेजी से स्पैर मैट्रिक्स गुणा से निपटने, this पेपर मौजूद है। विकसित एल्गोरिदम स्पैस मैट्रिक्स को दो भागों में विभाजित करता है: एक घना और एक स्पैस और उस पर एक तेज गुणा एल्गोरिदम लागू होता है। तो मेरे लिए ऐसा लगता है कि यह मैट्रिक्स के आकार पर निर्भर नहीं है, जैसा कि आपने स्ट्रैसेन के संबंध में उल्लेख किया है, लेकिन तथ्य यह है कि यह स्पैस है।

Answer 2

एक स्पैस मैट्रिक्स को लागू करने के तरीके हैं जो घने मैट्रिक्स से अधिक संघनित होते हैं। एक तरीका यह है कि मैं इसे इस प्रकार है कार्य करें:

[0 0 0 0 0] 
[0 1 2 0 9] 
[0 0 0 2 0] 
[0 1 0 0 0] 

हे के बजाय गैर शून्य तत्व

typedef struct { 
    int row; 
    int col; 
    double entry; 
} Element; 

typedef SparseMatrix Element*; 

तो मैट्रिक्स अब हे (एन) के एक अंतरिक्ष जटिलता है की एक रेखीय सरणी (हो जाता है एन^2) ए * बी के लिए, जहां ए और बी matrices हैं, आपको केवल मिलान तत्वों के लिए प्रत्येक सरणी को पार करने की आवश्यकता है (यानी ए-> पंक्ति == बी-> कोल & & a-> col == b-> पंक्ति), और संभवतः कई एक साथ (आंतरिक उत्पाद) जोड़ें। यह एल्गोरिदम ओ (एन^3) की बजाय ओ (एन^2) जटिलता का होगा। ऐसा इसलिए है क्योंकि आप एक आंतरिक उत्पाद लेने के बेवकूफ ऑपरेशन को छोड़ सकते हैं जिसके परिणामस्वरूप शून्य हो जाएगा।

Answer 3

जांच Highly Parallel Sparse Matrix-Matrix Multiplication algorothm