विरल मैट्रिक्स

विरल आव्यूह का उदाहरण $\left({\begin{smallmatrix}11&22&0&0&0&0&0\\0&33&44&0&0&0&0\\0&0&55&66&77&0&0\\0&0&0&0&0&88&0\\0&0&0&0&0&0&99\\\end{smallmatrix}}\right)$
उपरोक्त विरल आव्यूह में 26 शून्य अवयवों के साथ मात्र 9 गैर-शून्य अवयव होते हैं। इसकी दुर्लभता 74% है, और इसकी घनत्व 26% है।

दो आयामों में परिमित अवयव विधि को हल करते समय प्राप्त विरल आव्यूह। गैर-शून्य अवयवों को काले रंग में दिखाया गया है।

संख्यात्मक विश्लेषण और वैज्ञानिक कंप्यूटिंग में, एक विरल आव्यूह या एक विरल सरणी(गणित) है जिसमें अधिकांश अवयव शून्य होते हैं।^[1] आव्यूह के लिए विरल के रूप में योग्यता के लिए शून्य-मान अवयवों के अनुपात के संबंध में कोई विशुद्ध परिभाषा नहीं है, परन्तु एक सामान्य मापदण्ड यह है कि गैर-शून्य अवयवों की संख्या लगभग पंक्तियों या स्तंभों की संख्या के बराबर होती है। इसके विपरीत, यदि अधिकांश अवयव गैर-शून्य हैं, तो आव्यूह को सघन माना जाता है।^[1] अवयवों की कुल संख्या से विभाजित शून्य-मान वाले अवयवों की संख्या(उदाहरण के लिए, m × n आव्यूह के लिए m × n) को कभी-कभी आव्यूह की 'विरलता' कहा जाता है।

संकल्पनात्मक रूप से, विरलता कुछ युग्‍मानूसार अंतःक्रियाओं वाली पद्धति से मेल खाती है। उदाहरण के लिए, एक से दूसरे में स्प्रिंग द्वारा संयोजित गेंदों की पंक्ति पर विचार करें: यह एक विरल पद्धति है क्योंकि मात्र समीपवर्ती गेंदों को युग्मित किया जाता है। इसके विपरीत, यदि गेंदों की एक ही पंक्ति में प्रत्येक गेंद को अन्य सभी गेंदों से संयोजी स्प्रिंगें हों, तो पद्धति एक सघन आव्यूह के अनुरूप होगा। विरलता की अवधारणा साहचर्य और प्रयोग क्षेत्रों जैसे नेटवर्क सिद्धांत और संख्यात्मक विश्लेषण में उपयोगी है, जिसमें सामान्यतः महत्वपूर्ण डेटा या संपर्क का घनत्व कम होता है। आंशिक अंतर समीकरणों को हल करते समय बड़े विरल आव्यूह प्रायः वैज्ञानि की या अभियांत्रिकी अनुप्रयोगों में उपस्थित होते हैं।

कंप्यूटर पर विरल आव्यूह का संग्रहण और परिचालन के समय, विशेष एल्गोरिदम और डेटा संरचनाओं का उपयोग करना लाभप्रद और प्रायः आवश्यक होता है जो आव्यूह की विरल संरचना का लाभ उठाते हैं। विरल आव्यूह के लिए विशिष्ट कंप्यूटर बनाए गए हैं,^[2] क्योंकि वे मशीन अधिगम क्षेत्र में सामान्य हैं।^[3] प्रसंस्करण के रूप में बड़े विरल आव्यूह पर लागू होने पर मानक घने-आव्यूह संरचनाओं और एल्गोरिदम का उपयोग करने वाले संचालन धीमे और अक्षम होते हैं और मेमोरी शून्य पर क्षीण हो जाती है। विरल डेटा स्वभाव से अधिक आसानी से डेटा संपीड़न होता है और इस प्रकार कंप्यूटर डेटा संग्रहण में अत्यधिक कम की आवश्यकता होती है। मानक घने-आव्यूह एल्गोरिदम का उपयोग करके परिचालन के लिए कुछ बहुत बड़े विरल आव्यूह अक्षम हैं।

विरल आव्यूह का संग्रहण

आव्यूह को सामान्यतः द्वि-आयामी सरणी के रूप में संग्रहीत किया जाता है। सरणी में प्रत्येक प्रविष्टि एक अवयव $a i, j$ का प्रतिनिधित्व करती है आव्यूह का और दो सूचकांकों द्वारा अभिगम किया जाता है परंपरागत रूप से, $i$ पंक्ति सूचकांक है जिसे ऊपर से नीचे तक क्रमांकित किया गया है, और $j$ स्तंभ सूचकांक है, जिसे बाएँ से दाएँ क्रमांकित किया गया है। $m \times n$ आव्यूह के लिए, इस प्रारूप में आव्यूह को संग्रहीत करने के लिए आवश्यक मेमोरी की मात्रा $m \times n$ आनुपातिक है(इस तथ्य की उपेक्षा करते हुए कि आव्यूह के आयामों को भी संग्रहीत करने की आवश्यकता है)।

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

स्वरूपों को दो समूहों में विभाजित किया जा सकता है:

वे जो दक्ष संशोधन का समर्थन करते हैं, जैसे डीओके(कुंजियों का शब्दकोश), एलआईएल(सूचियों की सूची), या सीओओ(समन्वय सूची)। ये सामान्यतः आव्यूह के निर्माण के लिए उपयोग किए जाते हैं।
वे जो सीएसआर(संपीड़ित विरल पंक्ति) या सीएससी(संपीड़ित विरल स्तंभ) जैसे दक्ष अभिगम और आव्यूह संचालन का समर्थन करते हैं।

कुंजियों का शब्दकोश(डीओके)

डीओके में एक शब्दकोश होता है जो मानचित्र साहचर्य आव्यूह $(row, column)$ अवयवों के मान के लिए युग्मित करता है। शब्दकोश से अनुपस्थित होने वाले अवयवों को शून्य मान लिया जाता है। प्रारूप यादृच्छिक क्रम में विरल आव्यूह के निर्माण के लिए अच्छा है, परन्तु कोशक्रमानुसार क्रम में गैर-शून्य मानों पर पुनरावृति के लिए अल्प है। एक सामान्यतः इस प्रारूप में आव्यूह बनाता है और फिर प्रसंस्करण के लिए एक और अधिक दक्ष प्रारूप में परिवर्तित हो जाता है।^[4]

सूचियों की सूची(एलआईएल)

एलआईएल प्रति पंक्ति एक सूची संग्रहीत करता है, जिसमें प्रत्येक प्रविष्टि में स्तंभ सूचकांक और मान होता है। सामान्यतः, इन प्रविष्टियों को तीव्रता से देखने के लिए स्तंभ सूचकांक द्वारा क्रमबद्ध रखा जाता है। वार्धिक आव्यूह निर्माण के लिए यह एक और प्रारूप अच्छा है।^[5]

समन्वय सूची(सीओओ)

सीओओ $(row, column, value)$ टपल की एक सूची संग्रहीत करता है। आदर्श रूप से, यादृच्छिक अभिगम समय में सुधार के लिए प्रविष्टियों को पूर्व पंक्ति सूचकांक और फिर स्तंभ सूचकांक द्वारा क्रमबद्ध किया जाता है। यह एक और प्रारूप है जो वार्धिक आव्यूह निर्माण के लिए अच्छा है।^[6]

संपीड़ित विरल पंक्ति(सीएसआर, सीआरएस या येल प्रारूप)

संपीड़ित विरल पंक्ति(सीएसआर) या संपीड़ित पंक्ति संग्रहण(सीआरएस) या येल प्रारूप तीन(एक-आयामी) सरणियों द्वारा $M$ आव्यूह का प्रतिनिधित्व करता है, जिसमें क्रमशः शून्येतर मान, पंक्तियों का विस्तार, और स्तंभ सूचकांक होते हैं। यह सीओओ के समान है, परन्तु पंक्ति सूचकांकों को संकुचित करता है, इसलिए यह नाम है। यह प्रारूप तीव्र पंक्ति अभिगम और आव्यूह-सदिश गुणन( $M x$ ) की अनुमति देता है। सीएसआर प्रारूप कम से कम 1960 के दशक के मध्य से उपयोग में रहा है, जिसका प्रथम पूर्ण विवरण 1967 में प्रदर्शित हुआ था।^[7]

सीएसआर प्रारूप तीन(एक-आयामी) सरणियों $(V, COL_INDEX, ROW_INDEX)$ का उपयोग करके एक विरल $m \times n$ आव्यूह $M$ को पंक्ति रूप में संग्रहीत करता है। बता दें कि $NNZ$ $M$ में गैर-शून्य प्रविष्टियों की संख्या को निरूपित करता है।(ध्यान दें कि यहां शून्य-आधारित सूचकांकों का उपयोग किया जाएगा।)

सरणियाँ $V$ और $COL_INDEX$ लम्बाई $NNZ$ की हैं, और गैर-शून्य मान और क्रमशः उन मानों के स्तंभ सूचकांक सम्मिलित करें।
सरणी $ROW_INDEX$ की लम्बाई $m + 1$ है और सूचकांक को $V$ और $COL_INDEX$ कोडित करता है जहां दी गई पंक्ति प्रारम्भ होती है। यह $ROW_INDEX[j]$ के बराबर है जो पंक्ति $j$ के ऊपर गैर शून्य की कुल संख्या को कोडित करता है। अंतिम अवयव $NNZ$ है, अर्थात, अंतिम वैध सूचकांक $NNZ - 1$ के तुरंत बाद $V$ काल्पनिक सूचकांक है। ^[8]

उदाहरण के लिए, आव्यूह

{\begin{pmatrix}5&0&0&0\\0&8&0&0\\0&0&3&0\\0&6&0&0\\\end{pmatrix}}

4 गैर-शून्य अवयवों वाला

4 \times 4

आव्यूह है, इसलिए

V = [5 8 3 6]
COL_INDEX = [ 0 1 2 1 ]
ROW_INDEX = [ 0 1 2 3 4 ]

शून्य-अनुक्रमित भाषा मानता है।

एक पंक्ति निकालने के लिए, हम पूर्व परिभाषित करते हैं:

row_start = ROW_INDEX [row]
row_end = ROW_INDEX [row + 1]

फिर हम V और COL_INDEX से भाग लेते हैं जो row_start से प्रारम्भ होती है और row_end पर समाप्त होती है।

इस आव्यूह की पंक्ति 1(दूसरी पंक्ति) निकालने के लिए हम row_start=1 और row_end=2संग्रह करते हैं। फिर हम भाग V[1:2] = [8] और COL_INDEX[1:2] = [1]. बनाते हैं। अब हम जानते हैं कि पंक्ति 1 में हमारे समीप स्तंभ 1 में मान 8 के साथ एक अवयव है।

इस विषय में मूल आव्यूह में 16 की तुलना में सीएसआर प्रतिनिधित्व में 13 प्रविष्टियां हैं। सीएसआर प्रारूप मात्र $NNZ < (m (n - 1) - 1) / 2$ पर मेमोरी पर सहेजता है।

एक अन्य उदाहरण, आव्यूह

{\begin{pmatrix}10&20&0&0&0&0\\0&30&0&40&0&0\\0&0&50&60&70&0\\0&0&0&0&0&80\\\end{pmatrix}}

एक

4 \times 6

आव्यूह(24 प्रविष्टियाँ) जिसमें 8 अशून्य अवयव हैं, इसलिए

V = [10 20 30 40 50 60 70 80]
COL_INDEX = [ 0 1 1 3 2 3 4 5 ]
ROW_INDEX = [ 0 2 4 7 8 ]

संपूर्ण को 21 प्रविष्टियों के रूप में संग्रहीत किया जाता है: $V$ में 8, $COL_INDEX$ में 8, और $ROW_INDEX$ में 5।

$ROW_INDEX$ सरणी है $V$ को पंक्तियों में विभाजित करता है:(10, 20)(30, 40)(50, 60, 70)(80), $V$ (और $COL_INDEX$ ) के सूचकांक को दर्शाता है जहां प्रत्येक पंक्ति प्रारम्भ और समाप्त होती है;
$COL_INDEX$ स्तंभों में मानों को संरेखित करता है:(10, 20, ...)(0, 30, 0, 40, ...)(0, 0, 50, 60, 70, 0)(0, 0, 0, 0, 0, 80).

ध्यान दें कि इस प्रारूप में, $ROW_INDEX$ का प्रथम मान सदैव शून्य होता है और अंतिम सदैव $NNZ$ होता है, इसलिए वे कुछ अर्थ में अनावश्यक हैं(यद्यपि प्रोग्रामिंग भाषाओं में जहां सरणी लंबाई को स्पष्ट रूप से संग्रहीत करने की आवश्यकता होती है, $NNZ$ अनावश्यक नहीं होगा)। फिर भी, यह प्रत्येक पंक्ति की लंबाई की गणना करते समय एक असाधारण विषय को संभालने की आवश्यकता से बचता है, क्योंकि यह सूत्र की गारंटी देता है $ROW_INDEX[i + 1] - ROW_INDEX[i]$ किसी भी पंक्ति $i$ के लिए काम करता है। इसके अतिरिक्त, पर्याप्त रूप से बड़े आव्यूह के लिए इस अनावश्यक संग्रहण की मेमोरी लागत संभवतः नगण्य है।

(प्राचीन और नवीन) येल विरल आव्यूह प्रारूप सीएसआर पद्धति के उदाहरण हैं। प्राचीन येल प्रारूप ठीक ऊपर बताए अनुसार काम करता है, तीन सरणियों के साथ; नवीन स्वरूप $ROW_INDEX$ और $COL_INDEX$ को एकल सरणी में जोड़ता है और आव्यूह के विकर्ण को अलग से संभालता है।^[9]

तार्किक निकटता आव्यूह के लिए, डेटा सरणी को छोड़ा जा सकता है, क्योंकि पंक्ति सरणी में एक प्रविष्टि का अस्तित्व द्विआधारी आसन्न संबंध को मॉडल करने के लिए पर्याप्त है।

यह संभवतः येल प्रारूप के रूप में जाना जाता है क्योंकि यह येल विश्वविद्यालय में कंप्यूटर विज्ञान विभाग से 1977 येल विरल आव्यूह पैकेज विवरण में प्रस्तावित किया गया था।^[10]

संपीड़ित विरल स्तंभ(सीएससी या सीसीएस)

सीएससी सीएसआर के समान है अतिरिक्त इसके कि मान पूर्व स्तंभ द्वारा पढ़े जाते हैं, प्रत्येक मान के लिए एक पंक्ति सूचकांक संग्रहीत की जाती है, और स्तंभ सूचक संग्रहीत किए जाते हैं। उदाहरण के लिए, सीएससी $(val, row_ind, col_ptr)$ है, जहां $val$ सरणी के गैर-शून्य मानों(ऊपर से नीचे, फिर बाएं से दाएं) की एक आव्यूह है; $row_ind$ मानों के अनुरूप पंक्ति सूचकांक है; और, $col_ptr$ $val$ की सूची है जहां प्रत्येक स्तंभ प्रारम्भ होता है। नाम इस तथ्य पर आधारित है कि स्तंभ सूचकांक जानकारी सीओओ प्रारूप के सापेक्ष संकुचित होती है। एक सामान्यतः निर्माण के लिए दूसरे प्रारूप(एलआईएल, डीओके, सीओओ) का उपयोग करता है। यह प्रारूप अंकगणितीय संचालन, स्तंभ प्रखंड और आव्यूह-सदिश उत्पादों के लिए दक्ष है। स्कीपी.विरल.csc_matrix देखें। यह MATLAB(विरल चर के माध्यम से ) में विरल आव्यूह निर्दिष्ट करने के लिए यह पारंपरिक प्रारूप है।

विशेष संरचना

पट्टित

विरल आव्यूह का एक महत्वपूर्ण विशेष प्रकार बैंड आव्यूह है, जिसे निम्नानुसार परिभाषित किया गया है। आव्यूह $A$ की निम्न बैंडविड्थ सबसे छोटी संख्या $p$ है जैसे कि प्रविष्टि $a i, j$ अनुपस्थित हो जाता है जब भी $i > j + p$ . इसी प्रकार, ऊपरी बैंडविड्थ सबसे छोटी संख्या $p$ है जैसे कि $a i, j = 0$ जब भी $i < j - p$ (गोलूब & वैन लोन 1996, §1.2.1)। उदाहरण के लिए, एक त्रिभुज आव्यूह में निम्न बैंडविड्थ $1$ और ऊपरी बैंडविड्थ $1$ है। एक अन्य उदाहरण के रूप में, निम्नलिखित विरल आव्यूह में निम्न और ऊपरी बैंडविड्थ दोनों 3 के बराबर हैं। ध्यान दें कि शून्य को स्पष्टता के लिए बिंदु के साथ दर्शाया गया है।

{\begin{bmatrix}X&X&X&\cdot &\cdot &\cdot &\cdot &\\X&X&\cdot &X&X&\cdot &\cdot &\\X&\cdot &X&\cdot &X&\cdot &\cdot &\\\cdot &X&\cdot &X&\cdot &X&\cdot &\\\cdot &X&X&\cdot &X&X&X&\\\cdot &\cdot &\cdot &X&X&X&\cdot &\\\cdot &\cdot &\cdot &\cdot &X&\cdot &X&\\\end{bmatrix}}

उचित रूप से छोटे ऊपरी और निचले बैंडविड्थ वाले आव्यूह को बैंड आव्यूह के रूप में जाना जाता है और प्रायः सामान्य विरल आव्यूह की तुलना में सरल एल्गोरिदम के लिए स्वयं को उधार देते हैं; या कोई कभी-कभी घने आव्यूह एल्गोरिदम लागू कर सकता है और कम संख्या में सूचकांकों पर लूप करके दक्षता प्राप्त कर सकता है।

आव्यूह $A$ की पंक्तियों और स्तंभों को पुनर्व्यवस्थित करके निम्न बैंडविड्थ के साथ $A'$ आव्यूह प्राप्त करना संभव हो सकता है। ग्राफ बैंडविड्थ के लिए कई एल्गोरिदम डिज़ाइन किए गए हैं।

विकर्ण

बैंड आव्यूह, विकर्ण आव्यूह के एक परम विषय के लिए बहुत ही दक्ष संरचना, मात्र मुख्य विकर्ण में प्रविष्टियों को एक आयामी सरणी के रूप में संग्रहीत करना है, इसलिए एक विकर्ण $n \times n$ आव्यूह को मात्र $n$ प्रविष्टियां की आवश्यकता होती है।

सममित

सममित विरल आव्यूह एक अप्रत्यक्ष ग्राफ के आसन्न आव्यूह के रूप में उत्पन्न होता है; इसे निकटता सूची के रूप में दक्षतापूर्वक संग्रहीत किया जा सकता है।

खंड विकर्ण

एक खंड-विकर्ण आव्यूह में इसके विकर्ण खंडों के साथ उप-आव्यूह होते हैं। एक खंड-विकर्ण आव्यूह $A$ का रूप है

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

Anonymous

Search