इस अनुभाग में हम देखेंगे कि विरल मैट्रिक्स (Sparse Matrix) क्या होता है और इसे मेमोरी में कैसे प्रस्तुत किया जा सकता है। एक मैट्रिक्स विरल मैट्रिक्स होता है यदि इसके अधिकांश तत्व 0 हों। एक अन्य परिभाषा के अनुसार, अधिकतम 1/3 गैर-शून्य तत्वों (लगभग 30% m x n) वाला मैट्रिक्स विरल मैट्रिक्स कहलाता है।
हम कंप्यूटर मेमोरी में मैट्रिक्स का उपयोग कुशलतापूर्वक संक्रियाएँ करने के लिए करते हैं। लेकिन यदि मैट्रिक्स प्रकृति में विरल हैं, तो यह संक्रियाओं को कुशलतापूर्वक करने में मदद कर सकता है, लेकिन यह मेमोरी में बड़ा स्थान घेरता है। उन स्थानों का कोई उद्देश्य नहीं होता। इसलिए हम विरल मैट्रिक्स को संग्रहीत करने के लिए अन्य प्रकार की संरचनाओं का पालन करेंगे।
मान लीजिए हमारे पास नीचे जैसा एक विरल मैट्रिक्स है:
हम देख सकते हैं कि 8 गैर-शून्य तत्व हैं और 28 शून्य-मान हैं। यह मैट्रिक्स 6*6 = 36 मेमोरी स्थान ले रहा है। यदि मैट्रिक्स का आकार बड़ा है, तो स्थान की बर्बादी बढ़ जाएगी।
टेबल संरचना का उपयोग करके विरल मैट्रिक्स संग्रहीत करना
हम टेबल संरचना का उपयोग करके विरल मैट्रिक्स के बारे में जानकारी संग्रहीत कर सकते हैं। मान लीजिए हम नीचे जैसी X नामक एक टेबल बनाते हैं:
यहाँ पहला कॉलम पंक्ति संख्या (Row number) रखता है, दूसरा कॉलम स्तंभ संख्या (Column number) रखता है। तीसरा कॉलम M[row, col] पर मौजूद डेटा रखता है। इस टेबल की प्रत्येक पंक्ति को ट्रिपलेट्स (triplets) कहा जाता है, क्योंकि इसमें तीन पैरामीटर होते हैं। पहला ट्रिपलेट मैट्रिक्स की आकार जानकारी रखता है। पंक्ति = 6 और स्तंभ = 6 दर्शाता है कि मैट्रिक्स M 6 x 6 मैट्रिक्स है। मान फ़ील्ड सरणी में मौजूद गैर-शून्य तत्वों की संख्या को दर्शाता है।
यह टेबल भी 9 * 3 = 36 स्थान ले रहा है, तो लाभ कहाँ है? यदि मैट्रिक्स का आकार 8*8 = 64 है, लेकिन केवल 8 तत्व मौजूद हैं, तब भी टेबल X 36 इकाई स्थान लेगा। हम देख सकते हैं कि 3 निश्चित कॉलम हैं, पंक्तियों की संख्या गैर-शून्य तत्वों की संख्या के साथ बदलती है। इसलिए यदि T गैर-शून्य तत्व हैं, तो स्थान जटिलता O(3*T) = O(T) होगी। मैट्रिक्स के लिए यह O(m x n) होगी।
