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

ما هي المصفوفة المتفرقة؟

تُسمى المصفوفة متفرقة عندما تكون الغالبية العظمى من عناصرها أصفاراً. لا يوجد حد عالمي محدد، لكن في الممارسة العملية تكون المصفوفة متفرقة حين يؤدي استغلال بنية الأصفار فيها إلى وفورات حسابية ملموسة. الكثافة هي نسبة العناصر غير الصفرية: الكثافة = nnz / (m × n)، حيث nnz هو عدد العناصر غير الصفرية. تنشأ المصفوفات ذات الكثافة أقل من 1% — وغالباً أقل من ذلك بكثير — بشكل طبيعي في العلوم والهندسة.

تأمل شبكة اجتماعية بـ n = 10⁶ مستخدم. مصفوفة التجاور حجمها n × n = 10¹² عنصراً. تخزينها كثيفاً يتطلب 8 تيرابايت (بمعدل 8 بايت لكل عدد مزدوج الدقة). لكن متوسط المستخدم يتابع ~300 شخص، فـ nnz ≈ 3 × 10⁸ — أي 0.03% فقط من العناصر غير صفرية. التخزين المتفرق يقلل الذاكرة إلى ~2.4 غيغابايت: توفير بمقدار 3000 مرة. نجد بنية مماثلة في تقسيم العناصر المحدودة (كل عقدة تتصل فقط بجيرانها) وسلاسل ماركوف (الانتقالات فقط إلى الحالات القابلة للوصول)، والمؤثرات التفاضلية (كل معادلة تشمل نقاط الشبكة المجاورة فقط).

ثلاثة نماذج كلاسيكية تولّد مصفوفات متفرقة في الهندسة: (1) لابلاسيانات الرسوم البيانية — لرسم بياني بـ n عقدة وm حافة: L = D − A لها nnz = n + 2m، عادةً O(n) للرسوم البيانية المتفرقة؛ (2) مصفوفات الصلابة في العناصر المحدودة — تقسيم معادلة تفاضلية جزئية ثنائية الأبعاد على شبكة بـ n عقدة يعطي مصفوفة بـ nnz ≈ 5n إلى 7n حسب نوع العنصر؛ (3) مصفوفات انتقال ماركوف — كل عمود مجموعه 1 وعدد عناصره غير الصفرية يساوي درجة الخروج من الحالة المقابلة.

صيغ التخزين

أكثر ثلاث صيغ شيوعاً تقدم مقايضات مختلفة بين الذاكرة وسهولة البناء وكفاءة العمليات.

COO — صيغة الإحداثيات

أبسط صيغة متفرقة تخزن ثلاثة مصفوفات: row[k] وcol[k] وval[k]، كل منها بطول nnz. العنصر k يمثل العنصر غير الصفري A[row[k], col[k]] = val[k]. لا تفترض COO أي ترتيب — يمكن أن تظهر الإدخالات بأي تسلسل. هذا يجعل COO مثالية لبناء المصفوفة: تجميع مصفوفة صلابة العناصر المحدودة يولد ثلاثيات (صف، عمود، قيمة) بشكل طبيعي، تُكدَّس في COO ثم تُحوَّل لاحقاً إلى صيغة مضغوطة. تتطلب COO 3 × nnz من التخزين (بالإضافة إلى تكرارات محتملة أثناء التجميع). ضرب المصفوفة في متجه مباشر لكن ليس صديقاً للذاكرة المؤقتة، لأن الوصول إلى الصفوف عشوائي.

CSR — الصف المضغوط المتفرق

CSR (المعروف أيضاً بـ CRS) هو الصيغة القياسية للعمليات الحسابية على المصفوفات المتفرقة. يستخدم ثلاثة مصفوفات:

val[0..nnz−1] — القيم غير الصفرية، مخزنة صفاً بصف
col_ind[0..nnz−1] — فهرس العمود لكل عنصر غير صفري
row_ptr[0..m] — row_ptr[i] هو الفهرس في val/col_ind حيث يبدأ الصف i؛ row_ptr[m] = nnz

الصف i له عناصر غير صفرية في الأعمدة col_ind[row_ptr[i]], …, col_ind[row_ptr[i+1]−1] بقيم val[row_ptr[i]], …, val[row_ptr[i+1]−1]. الذاكرة: (m+1) عدداً صحيحاً لـ row_ptr بالإضافة إلى 2×nnz لـ val وcol_ind — أي نحو (2 nnz + m) كلمة في المجموع، مقابل m × n للتخزين الكثيف.

ضرب المصفوفة المتفرقة في متجه (SpMV) بصيغة CSR

y_i = \sum_{j=\text{row\_ptr}[i]}^{\text{row\_ptr}[i+1]-1} \text{val}[j] \cdot x[\text{col\_ind}[j]], \quad i = 0, \ldots, m-1

لكل صف i، تجري الحلقة الداخلية على nnz_i عنصر غير صفري فقط في ذلك الصف. التكلفة الإجمالية: O(nnz) عملية ضرب وجمع. الوصول إلى val وcol_ind تسلسلي (ودّي للذاكرة المؤقتة)، لكن الوصول العشوائي إلى x قد يسبب إخفاقات في الذاكرة المؤقتة للمصفوفات الكبيرة.

CSR هي صيغة العمل لمحلات التكرار لأن SpMV يهيمن على تكلفة طرق مثل التدرج المترافق وGMRES. لكن الوصول إلى الأعمدة مكلف — إيجاد جميع العناصر غير الصفرية في عمود معين يستلزم مسح المصفوفة بأكملها. هذا يدفع نحو صيغة CSC المرافقة.

CSC — العمود المضغوط المتفرق

CSC نظير CSR باتجاه الأعمدة: ثلاثة مصفوفات val وrow_ind وcol_ptr، حيث col_ptr[j] يشير إلى بداية العمود j في val وrow_ind. CSC هي الصيغة الأصلية في MATLAB (الذي يخزن جميع المصفوفات بترتيب الأعمدة) وفي كثير من المحلات المباشرة، لأن تحليل Cholesky وLU يعالج الأعمدة بشكل طبيعي. لحساب A^T v بكفاءة، تُختزل صيغة CSC إلى SpMV في CSR. وتستخدم امتدادات LAPACK المتفرقة وSuiteSparse صيغة CSC داخلياً.

BSR والصيغ الكتلية الأخرى

عندما يكون نمط التفرق ذا بنية كتلية — مثل مصفوفات العناصر المحدودة ذات الكتل الكثيفة 3×3 أو 6×6 عند كل موضع غير صفري — تخزن BSR (الصفوف المتفرقة الكتلية) الكتل بشكل متجاور. يحسّن هذا استخدام تعليمات SIMD لأن كل كتلة تدخل في سجلات المتجهات مباشرة. حجم الكتل 4×4 أو 8×8 يمكن أن يحقق تسريعاً بمقدار 4–8 أضعاف عن CSR العددي على المعالجات الحديثة. وصيغة ELLPACK، الشائعة على معالجات الرسوميات، تخزن عدداً ثابتاً من العناصر غير الصفرية لكل صف في مصفوفة منتظمة، فيصبح الوصول إلى الذاكرة متلاحماً.

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

SpMV: الأساس الحاسم

ضرب المصفوفة المتفرقة في متجه (y ← Ax) هو أهم عملية متفرقة على الإطلاق. يقود محلات التكرار وخوارزميات الرسوم البيانية (PageRank، انتشار التسميات) واستدلال الشبكات العصبية للمصفوفات الوزنية المتفرقة. كثافة العمليات الحسابية في SpMV منخفضة جداً — حوالي 2 nnz عملية على 3 nnz + n كلمة بيانات — مما يجعلها محدودة بعرض نطاق الذاكرة. لمصفوفة متفرقة بـ nnz = 10⁷ وn = 10⁶ على معالج حديث بعرض نطاق ذاكرة 50 غيغابايت/ثانية، يستغرق SpMV نحو 1.6 ميلي ثانية؛ وعلى معالج رسوميات بـ 900 غيغابايت/ثانية، نحو 0.09 ميلي ثانية. كفاءة SpMV موضوع بحث منذ عقود: إعادة ترتيب الصفوف والأعمدة (مثل Reverse Cuthill-McKee) تحسن المحلية للذاكرة المؤقتة؛ وتجميع السجلات وتعليمات SIMD تحسن استخدام الحساب.

ضرب المصفوفات المتفرقة (SpGEMM)

حساب C = A × B عندما تكون كلتا A وB متفرقتين أصعب جوهرياً من SpMV لأن نمط تفرق C غير معروف مسبقاً وقد يكون C أكثر كثافة بكثير من A أو B. SpGEMM هي العملية الأساسية في خوارزميات أقصر المسارات (Bellman-Ford كقوى للمصفوفة) وحساب المثلثات وتجميع شبكات الرسوم البيانية العصبية. التحدي الرئيسي هو ملء الفراغ: حتى لو كانت A وB تحتويان على O(n) عنصر غير صفري، يمكن أن يكون لـ C ما يصل إلى O(n²) عنصر غير صفري في أسوأ الحالات. خوارزميات SpGEMM العملية تستخدم خرائط تعمية (hash maps) أو دمجاً مرتباً لتكديس العناصر بكفاءة؛ ومكتبات مثل SuiteSparse:GraphBLAS تقدم تنفيذات عالية الأداء.

إعادة الترتيب لتقليل ملء الفراغ

عند تحليل مصفوفة متفرقة A = LU أو A = LL^T، تظهر عناصر جديدة غير صفرية — تسمى ملء الفراغ — في L وU في مواضع كانت صفراً في A. الترتيب السيئ يمكن أن يحول مصفوفة متفرقة بـ nnz = O(n) إلى معامل مثلثي كثيف بـ nnz = O(n²). خوارزمية الدرجة الدنيا تستبعد المتغير ذا أقل اتصالات في كل خطوة، فتقلل ملء الفراغ تقليلاً كبيراً. ترتيب التقسيم المتداخل، القائم على فواصل الرسوم البيانية، يحقق ملء أمثل مُثبَتاً للرسوم البيانية المستوية: O(n log n) في المسائل ثنائية الأبعاد وO(n^{4/3}) في ثلاثية الأبعاد، مقابل O(n^{3/2}) وO(n²) للترتيبات الساذجة. والمحلات المباشرة المتفرقة الحديثة (CHOLMOD، UMFPACK، PARDISO) تطبق التقسيم المتداخل تلقائياً قبل التحليل.

حدود ملء الفراغ حسب بُعد المسألة

\text{nnz}(L) = \begin{cases} O(n \log n) & \text{2D, تقسيم متداخل} \\ O(n^{4/3}) & \text{3D, تقسيم متداخل} \\ O(n^{3/2}) & \text{2D, ترتيب ساذج} \\ O(n^2) & \text{3D, ترتيب ساذج} \end{cases}

لمعادلة تفاضلية جزئية ثنائية الأبعاد على شبكة بـ n عقدة مع ترتيب التقسيم المتداخل الأمثل، عامل تشولسكي L له O(n log n) عنصراً غير صفرياً والتحليل يكلف O(n^{3/2}) عملية. في ثلاثة أبعاد، nnz(L) = O(n^{4/3}) والتحليل يكلف O(n²) عملية — لا يزال أقل بكثير من O(n³) للمصفوفات الكثيفة لكن كبير بما يكفي لتبرير الطرق التكرارية لـ n > 10⁵.

التطبيقات

الرسوم البيانية وتحليل الشبكات

كل رسم بياني غير موجه بـ n عقدة وm حافة له مصفوفة تجاور متماثلة A ∈ {0,1}^{n×n} بـ nnz = 2m. للرسوم البيانية المتفرقة (m = O(n))، A لها O(n) عنصر غير صفري. اللابلاسيان L = D − A متفرق بشكل مماثل. تدعم الجبر الخطي المتفرق خوارزميات الرسوم البيانية:

PageRank: حل (I − αA^T D^{-1})π = (1−α)e / n تكرارياً؛ A^T D^{-1} هي مصفوفة الانتقال المعيّرة بالأعمدة.
التجميع الطيفي: حساب أصغر k من المتجهات الذاتية لـ L باستخدام محلّات ذاتية متفرقة (LOBPCG، ARPACK).
أقصر المسارات: Bellman-Ford كـ SpMV متكرر في شبه الحلقة (min, +)؛ وخوارزمية Johnson لكل الأزواج باستخدام Dijkstra المتفرق.
شبكات الرسوم البيانية العصبية: كل طبقة تمرير رسائل تحسب Ã H W حيث Ã هي مصفوفة التجاور المتفرقة المعيّرة وH هي مصفوفة سمات العقد.

طريقة العناصر المحدودة (FEM)

تقسّم FEM المعادلات التفاضلية الجزئية على شبكات غير منتظمة. كل عنصر (مثلث، رباعي الأوجه، إلخ) يساهم بمصفوفة صلابة كثيفة صغيرة تُجمّع في مصفوفة الصلابة العالمية المتفرقة K. وتكون K الناتجة متماثلة ومعرّفة موجبة في كثير من المسائل الفيزيائية (انتشار الحرارة، ميكانيكا الإنشاءات، الكهرومغناطيسية). التفرق ينشأ لأن دوال الأساس ذات دعم محلي — دالة الأساس المرتبطة بعقدة i غير صفرية فقط داخل العناصر المشتركة مع i. لشبكة ثنائية الأبعاد بـ n عقدة وعناصر مثلثية O(n) (كل منها بثلاث عقد)، K لها nnz ≈ 7n في المتوسط. وعملية التجميع تولّد ثلاثيات COO بشكل طبيعي، تُجمَع ثم تُحوَّل إلى CSR للحل التكراري.

سلاسل ماركوف والمصفوفات العشوائية

سلسلة ماركوف بـ n حالة لها مصفوفة انتقال P حيث Pᵢⱼ هو احتمال الانتقال من الحالة j إلى الحالة i (اصطلاح ستوكاستي الأعمدة). لمعظم العمليات الحقيقية، كل حالة تنتقل إلى عدد قليل فقط من الحالات الأخرى، مما يجعل P متفرقة. إيجاد التوزيع الثابت π المحقق لـ Pπ = π (أي حل (P − I)π = 0 بشرط 1^T π = 1) هو مسألة قيم ذاتية متفرقة. PageRank هو تماماً هذه المسألة لرسم الويب البياني. والتكرار الأُسّي المتفرق (π ← Pπ، مُعاداً حتى التقارب) يكلف O(nnz) لكل خطوة ويتقارب عادةً في O(1/(1−|λ₂|)) خطوة، حيث λ₂ هي القيمة الذاتية الثانية لـ P.

المحلات المباشرة مقابل التكرارية للمصفوفات المتفرقة

الاختيار بين المحلّات المباشرة والتكرارية للمصفوفات المتفرقة مقايضة بين المتانة والذاكرة والزمن وعدد الأطراف اليمنى:

المحلات المباشرة المتفرقة

المحلات المباشرة المتفرقة (SuiteSparse/UMFPACK، PARDISO، SuperLU، MUMPS) تطبق تبديل ترتيب، ثم تحسب تحليلاً دقيقاً متفرقاً LU أو Cholesky. بعد التحليل، كل طرف أيمن جديد يكلف فقط O(nnz(L)) ≈ O(n log n) في المسائل ثنائية الأبعاد. المحلات المباشرة المتفرقة:

متينة: تعمل لأي مصفوفة غير شاذة دون ضبط معاملات التقارب.
مثالية لأطراف يمنى متعددة: حلل مرة واحدة بـ O(n^{3/2}) (ثنائي الأبعاد)، حل كل b جديد بـ O(n log n).
محدودة بالذاكرة في ثلاثة أبعاد: nnz(L) = O(n^{4/3}) للمسائل ثلاثية الأبعاد؛ عند n = 10⁶ هذا نحو 10⁸ عنصر — قابل للإدارة. عند n = 10⁷ يصبح 2 × 10⁹ — على الحد. وعند n = 10⁸ تصبح الطرق المباشرة غير عملية.
غير قابلة للتطبيق على المسائل الخالية من المصفوفة: إذا كانت A محددة ضمنياً (كدالة تحسب Av)، لا يمكن تطبيق المحلات المباشرة.

المحلات التكرارية المتفرقة

الطرق التكرارية (CG، GMRES، BiCGSTAB) تصل إلى A فقط عبر SpMV. تحافظ على التفرق طوال الوقت ويمكنها استغلال أي تمثيل ضمني للمصفوفة. لمسائل جيدة التكييف مع مسبّقات جيدة، تتفوق على الطرق المباشرة حتى في ثنائي الأبعاد. نقاط ضعفها: لا يُضمن التقارب لجميع المصفوفات؛ اختيار وضبط مسبّق يتطلب خبرة؛ وتعيد حلولاً تقريبية (وإن كان بدقة اختيارية)؛ وفي المسائل سيئة التكييف قد يكون التقارب بطيئاً إلى حد بعيد.

مقارنة تعقيد المحلات

\text{بواسون ثنائي الأبعاد: }\begin{cases} \text{تحليل مباشر} & O(n^{3/2}) \\ \text{حل مباشر} & O(n \log n) \\ \text{PCG + متعدد الشبكات} & O(n) \end{cases}

لمسألة بواسون ثنائية الأبعاد بـ n مجهولاً. المباشر: تحليل O(n^{3/2})، كل حل O(n log n). PCG مع مسبّق متعدد الشبكات: O(n) لكل تكرار × O(1) تكرار = O(n) الإجمالي. لـ n = 10⁶ في ثنائي الأبعاد، المباشر يأخذ ~10⁹ عملية؛ متعدد الشبكات-PCG يأخذ ~10⁷ — أسرع بـ 100 مرة، مع أن المباشر يظل منافساً عند n أقل من 10⁵.

الأساليب الهجينة

أقوى الأدوات تجمع بين النهجين. ILU (تحليل LU غير مكتمل) يحسب تحليلاً تقريبياً متفرقاً — يُبقي فقط العناصر التي تتجاوز عتبة معينة أو التي تقع داخل نمط التفرق الأصلي — ويستخدمه كمسبّق لـ GMRES أو BiCGSTAB. طرق تقسيم النطاق تقسم النطاق إلى نطاقات فرعية، تحل كل منها بمحل مباشر، وتقرن النطاقات الفرعية تكرارياً. وطرق مكمّل شور تستبعد درجات الحرية الداخلية مباشرةً وتحل نظام الواجهة المتفرق تكرارياً. في الممارسة، معظم محلات الإنتاج المتفرقة (PETSc، Trilinos) تنفذ نهجاً طبقياً: حل مباشر للنطاقات الفرعية + اقتران تكراري.

تطبيق هندسي

في Python، توفر scipy.sparse صيغ COO وCSR وCSC مع تحويل تلقائي. scipy.sparse.linalg.spsolve يستخدم UMFPACK للحل المباشر المتفرق؛ scipy.sparse.linalg.cg / gmres للطرق التكرارية. في MATLAB، sparse() ينشئ مصفوفات CSC؛ عملية الشرطة المائلة تكشف التفرق تلقائياً وتختار محلاً مناسباً. للمسائل الكبيرة، يوفر PyAMG مسبّقات متعددة الشبكات الجبرية. وNetworkX وigraph تخزن الرسوم البيانية كقوائم تجاور؛ فإن أردت استخدام الجبر الخطي المتفرق (PageRank، المتجهات الذاتية للابلاسيان)، حوّل إلى scipy.sparse أولاً. وFAISS وannoy تستخدمان تمثيلات متفرقة للبحث التقريبي عن أقرب الجيران. وعند بناء محل عناصر محدودة، اجمع دائماً بصيغة COO وحوّل إلى CSR مرة واحدة قبل الحل التكراري — لا تحول أثناء التجميع.

النقاط الرئيسية

المصفوفات المتفرقة تحتوي على أصفار بشكل ساحق؛ استغلال ذلك يقلل الذاكرة من O(n²) إلى O(nnz) والحساب من O(n³) إلى O(nnz) لكل SpMV. COO (ثلاثيات صف وعمود وقيمة) الأسهل للتجميع؛ CSR (val وcol_ind وrow_ptr) الأكفأ لـ SpMV؛ CSC طبيعي لعمليات الأعمدة والتحليل المباشر. SpMV هو الأساس الحاسم للمحلات التكرارية وخوارزميات الرسوم البيانية. المصفوفات المتفرقة الواقعية تنشأ في الرسوم البيانية (التجاور واللابلاسيان) ومسائل FEM (دوال أساس ذات دعم محلي) وسلاسل ماركوف (انتقالات متفرقة). ملء الفراغ أثناء التحليل يدمر التفرق؛ خوارزميات إعادة الترتيب (التقسيم المتداخل، الدرجة الدنيا) تقلله من O(n²) إلى O(n log n) في ثنائي الأبعاد. المحلات المباشرة المتفرقة متينة وأمثل لأطراف يمنى متعددة؛ الطرق التكرارية ضرورية للمسائل ثلاثية الأبعاد والمسائل الضمنية وقيم n الكبيرة جداً. والطرق التكرارية الهجينة المسبّقة — ILU، ومتعدد الشبكات، وتقسيم النطاق — تجمع أفضل ما في العالمين.