المصفوفة المتفرقة

تُشكّل مصفوفات النطاق فئةً خاصةً من المصفوفات المتفرقة، حيث تتركز العناصر غير الصفرية بالقرب من القطر الرئيسي. وتتميز مصفوفة النطاق بعرض نطاقها الأدنى والأعلى، واللذان يشيران إلى عدد الأقطار أسفل وأعلى (على التوالي) القطر الرئيسي الذي تقع بينه جميع العناصر غير الصفرية.

بصورة رسمية، _{يُعرَّف} عرض النطاق الأدنى للمصفوفة A بأنه أصغر عدد p بحيث يكون العنصر aᵢ _{, ⱼ} يساوي صفرًا عندما يكون i > j + p . وبالمثل، يُعرَّف عرض النطاق الأعلى بأنه أصغر عدد p بحيث يكون _aᵢ , _{ⱼ =} 0 عندما يكون i < j − p ( جولوب وفان لون، 1996 ، §1.2.1) . على سبيل المثال، المصفوفة ثلاثية الأقطار لها عرض نطاق أدنى يساوي 1 وعرض نطاق أعلى يساوي 1. كمثال آخر، المصفوفة المتفرقة التالية لها عرض نطاق أدنى وعرض نطاق أعلى يساويان 3. لاحظ أن الأصفار ممثلة بنقاط للتوضيح. $${\displaystyle {\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 ′ ذات نطاق ترددي أقل. وقد صُممت العديد من الخوارزميات لتقليل النطاق الترددي .

تنشأ المصفوفة المتناظرة المتفرقة كمصفوفة تجاور لرسم بياني غير موجه ؛ ويمكن تخزينها بكفاءة كقائمة تجاور .

تتكون المصفوفة القطرية الكتلية من مصفوفات فرعية على طول كتلها القطرية. تأخذ المصفوفة القطرية الكتلية A الشكل التالي: $${\displaystyle \mathbf {A} ={\begin{bmatrix}\mathbf {A} _{1}&0&\cdots &0\\0&\mathbf {A} _{2}&\cdots &0\\\vdots &\vdots &\ddots &\vdots \\0&0&\cdots &\mathbf {A} _{n}\end{bmatrix}},}$$

حيث A _k هي مصفوفة مربعة لجميع قيم k = 1، ...، n .

تُعرف عناصر المصفوفة التي تتغير قيمتها من الصفر إلى قيمة غير صفرية أثناء تنفيذ الخوارزمية باسم "عناصر التعبئة". ولتقليل متطلبات الذاكرة وعدد العمليات الحسابية المستخدمة في الخوارزمية، يُنصح بتقليل عناصر التعبئة عن طريق تبديل الصفوف والأعمدة في المصفوفة. ويمكن استخدام تحليل تشوليسكي الرمزي لحساب أسوأ قيمة تعبئة ممكنة قبل إجراء تحليل تشوليسكي الفعلي .

توجد طرق أخرى غير تحليل تشوليسكي قيد الاستخدام. تُعدّ طرق التعامد (مثل تحليل QR) شائعة، على سبيل المثال، عند حلّ المسائل باستخدام طرق المربعات الصغرى. مع أن التعبئة النظرية تبقى نفسها، إلا أن "القيم غير الصفرية الزائفة" عمليًا قد تختلف باختلاف الطرق. ويمكن استخدام النسخ الرمزية لهذه الخوارزميات بنفس طريقة تشوليسكي الرمزية لحساب أسوأ حالة تعبئة.

توجد طرق تكرارية ومباشرة لحل المصفوفات المتفرقة.

تستخدم الطرق التكرارية، مثل طريقة التدرج المترافق و GMRES، حسابات سريعة لضرب المصفوفة في المتجه.${\displaystyle Ax_{i}}$، حيث المصفوفة${\displaystyle A}$تكون البيانات متفرقة. يمكن أن يؤدي استخدام المعالجات المسبقة إلى تسريع تقارب هذه الطرق التكرارية بشكل كبير.

تتكون DOK من قاموس يربط أزواج ( صف، عمود) بقيم العناصر. تُعتبر العناصر المفقودة من القاموس أصفارًا . يُعد هذا التنسيق مناسبًا لإنشاء مصفوفة متفرقة تدريجيًا بترتيب عشوائي، ولكنه غير مناسب للتكرار على القيم غير الصفرية بترتيب معجمي. عادةً ما يتم إنشاء مصفوفة بهذا التنسيق ثم تحويلها إلى تنسيق آخر أكثر كفاءة للمعالجة. ^{[ 4 ]}

يخزن LIL قائمة واحدة لكل صف، ويحتوي كل عنصر على فهرس العمود والقيمة. عادةً ما تُرتّب هذه العناصر حسب فهرس العمود لتسريع عملية البحث. هذا تنسيق آخر مناسب لإنشاء المصفوفات التزايدية. ^{[ 5 ]}

يخزن تنسيق COO قائمة من أزواج (الصف، العمود، القيمة) . من الناحية المثالية، يتم فرز الإدخالات أولاً حسب فهرس الصف ثم حسب فهرس العمود، لتحسين أوقات الوصول العشوائي. هذا تنسيق آخر مناسب لإنشاء المصفوفات التزايدية. ^{[ 6 ]}

يُمثل تنسيق الصفوف المتفرقة المضغوط (CSR) أو تخزين الصفوف المضغوط (CRS) أو تنسيق ييل، المصفوفة M بثلاثة مصفوفات (أحادية البعد)، تحتوي على التوالي على القيم غير الصفرية، وامتدادات الصفوف، ومؤشرات الأعمدة. وهو مشابه لتنسيق COO، ولكنه يضغط مؤشرات الصفوف، ومن هنا جاءت التسمية. يتيح هذا التنسيق الوصول السريع إلى الصفوف وعمليات ضرب المصفوفة في المتجه ( M × ). يُستخدم تنسيق CSR منذ منتصف الستينيات على الأقل، مع ظهور أول وصف كامل له في عام 1967. ^{[ 7 ]}

يخزن تنسيق CSR مصفوفة M متفرقة من الرتبة m × n في شكل صفوف باستخدام ثلاث مصفوفات (أحادية البعد) (V، COL_INDEX، ROW_INDEX) . لنفترض أن NNZ يمثل عدد العناصر غير الصفرية في M. (لاحظ أنه سيتم استخدام الفهارس التي تبدأ من الصفر هنا).

• يبلغ طول المصفوفتين V و COL_INDEX NNZ ، وتحتويان على القيم غير الصفرية ومؤشرات الأعمدة لتلك القيم على التوالي.
• يحتوي COL_INDEX على العمود الذي يوجد فيه الإدخال V المقابل.
• المصفوفة ROW_INDEX طولها m + 1 ، وتُشفّر فهرس بداية الصف المُعطى في V و COL_INDEX . وهذا يُكافئ ROW_INDEX[j] الذي يُشفّر العدد الإجمالي للقيم غير الصفرية فوق الصف j . العنصر الأخير هو NNZ ، أي الفهرس الوهمي في V الذي يلي مباشرةً آخر فهرس صالح NNZ − 1. ^{[ 8 ]}

على سبيل المثال، المصفوفة $${\displaystyle {\begin{pmatrix}5&0&0&0\\0&8&0&0\\0&0&3&0\\0&6&0&0\\\end{pmatrix}}}$$ هي مصفوفة 4 × 4 تحتوي على 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.

لاستخراج الصف الأول (الصف الثاني) من هذه المصفوفة، نُحدد قيمتي row_start=1و row_end=2. ثم نُنشئ الشرائح V[1:2] = [8]و COL_INDEX[1:2] = [1]. نعلم الآن أن لدينا في الصف الأول عنصرًا واحدًا في العمود الأول بقيمة 8.

في هذه الحالة، يحتوي تمثيل CSR على 13 مدخلاً، مقارنةً بـ 16 مدخلاً في المصفوفة الأصلية. يوفر تنسيق CSR مساحة في الذاكرة فقط عندما يكون NNZ < ( m ( n -1)-1) / 2 .

مثال آخر، المصفوفة $${\displaystyle {\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 × 6 (24 عنصرًا) تحتوي على 8 عناصر غير صفرية، لذا

الخامس = [ 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 مدخلاً: 8 في V ، و8 في COL_INDEX ، و5 في ROW_INDEX .

• يقوم 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 . علاوة على ذلك، من المرجح أن تكون تكلفة الذاكرة لهذا التخزين الزائد ضئيلة بالنسبة لمصفوفة كبيرة بما فيه الكفاية.

تُعدّ صيغ المصفوفات المتفرقة (القديمة والجديدة) في جامعة ييل مثالين على مخطط CSR. تعمل صيغة ييل القديمة تمامًا كما هو موضح أعلاه، بثلاث مصفوفات؛ أما الصيغة الجديدة فتجمع بين ROW_INDEX و COL_INDEX في مصفوفة واحدة وتتعامل مع قطر المصفوفة بشكل منفصل. ^{[ 9 ]}

بالنسبة لمصفوفات التجاور المنطقي ، يمكن حذف مصفوفة البيانات، حيث أن وجود عنصر في مصفوفة الصف يكفي لنمذجة علاقة تجاور ثنائية.

من المرجح أن يُعرف باسم تنسيق ييل لأنه تم اقتراحه في تقرير حزمة المصفوفات المتفرقة لعام 1977 الصادر عن قسم علوم الحاسوب في جامعة ييل. ^{[ 10 ]}

يُشبه تنسيق CSC تنسيق CSR باستثناء أنه يقرأ القيم أولاً حسب العمود، ويُخزَّن فهرس صف لكل قيمة، بالإضافة إلى مؤشرات الأعمدة. على سبيل المثال، يُكتب CSC على النحو التالي: (val, row_ind, col_ptr) ، حيث val عبارة عن مصفوفة من القيم غير الصفرية للمصفوفة (من الأعلى إلى الأسفل، ثم من اليسار إلى اليمين)؛ و row_ind هي فهارس الصفوف المقابلة للقيم؛ و col_ptr هي قائمة فهارس val التي يبدأ منها كل عمود. يستند الاسم إلى حقيقة أن معلومات فهرس العمود مضغوطة مقارنةً بتنسيق COO. عادةً ما يُستخدم تنسيق آخر (LIL، DOK، COO) للإنشاء. يُعد هذا التنسيق فعالاً للعمليات الحسابية، وتقطيع الأعمدة، وضرب المصفوفات في المتجهات. وهو التنسيق التقليدي لتحديد مصفوفة متفرقة في MATLAB (عبر الدالة sparse).