ملخص تقني: FINOM – خوارزمية Sinkhorn السريعة على الشبكات غير المنتظمة

بيان المشكلة

تتناول الورقة البحثية التحدي الحسابي المتمثل في حساب مسافة "واسرشتاين-1" (Wasserstein-1) بين مقاييس الاحتمال المنفصلة المعرفة على شبكات غير منتظمة (non-uniform meshes). وبينما تعد مشكلة النقل الأمثل (Optimal Transport - OT) أساسية في تطبيقات مثل ديناميكا السوائل، والتمويل، والتعلم الآلي، فإن حلها بكفاءة على الشبكات غير المنتظمة يظل أمراً صعباً.

تتطلب النهج العددية القياسية، مثل خوارزمية "سينكهورن" (Sinkhorn) (التي تستخدم تنظيم الإنتروبيا)، تعقيداً حسابياً قدره $O(N^2)$ لكل تكرار بسبب عمليات ضرب المصفوفات والمتجهات الكثيفة التي تتضمن مصفوفة النواة $K$. وقد نجحت أعمال سابقة للمؤلفين وآخرين في تسريع خوارزمية "سينكهورن" لتصل إلى تعقيد $O(N)$ للشبكات المنتظمة (uniform meshes) من خلال استغلال البنية "الخطية المتعامدة" (collinear) في مصفوفة النواة. ومع ذلك، فإن هذه الخاصية الخطية تنهار في الشبكات غير المنتظمة، مما يمنع التطبيق المباشر لهذه الطرق السريعة. وبناءً على ذلك، فإن التوفير الحسابي المكتسب من استخدام الشبكات غير المنتظمة (التي تستخدم نقاط شبكة أقل للتكثفات المركزة) غالباً ما يتم إبطاله بسبب التكلفة العالية لتكرارات "سينكهورن" البالغة $O(N^2)$.

المنهجية

يقترح المؤلفون خوارزمية FINOM (خوارزمية Sinkhorn السريعة على الشبكات غير المنتظمة)، وهي نهج برمجة ديناميكية يستعيد التعقيد الخطي $O(N)$ للمسائل أحادية البعد (1D) و$O(NM)$ للمسائل ثنائية الأبعاد (2D)، حتى على الشبكات غير المنتظمة.

1. مؤشر التقسيم وتقسيم الكتل (The Dividing Index and Block Partitioning)

الابتكار الجوهري هو تقديم "مؤشر تقسيم" $\zeta(i)$. بالنسبة لشبكة مصدر مرتبة $x$ وشبكة هدف $y$، يحدد $\zeta(i)$ فهرس الموقع في $y$ بحيث يكون $y_{\zeta(i)} \le x_i < y_{\zeta(i)+1}$. يسمح هذا المؤشر بتقسيم مصفوفة النواة $K$ (حيث $k_{ij} = e^{-|x_i - y_j|/\varepsilon}$) إلى كتلتين فرعيتين متكاملتين:

• الكتلة الدنيا ($K_L$): تحتوي على المدخلات حيث $j \le \zeta(i)$.
• الكتلة العليا ($K_U$): تحتوي على المدخلات حيث $j > \zeta(i)$.

2. البنية شبه الخطية (Quasi-Collinear Structure)

بينما تفتقر مصفوفة النواة الكاملة في الشبكة غير المنتظمة إلى الخطية الصارمة الموجودة في الشبكات المنتظمة، يوضح المؤلفون أن كتل التقسيم $K_L$ و $K_U$ تظهر خاصية "شبه خطية" (quasi-collinear). وتحديداً:

• ضمن المناطق غير الصفرية لهذه الكتل، تكون النسبة بين الصفوف المتتالية ثابتة (خاصية نسبة الصف الثابتة).
• تشكل المدخلات غير الصفرية نمط "درجي" (staircase pattern) تحدده عملية تقسيم المؤشر.

3. التمثيل المتجهي والبرمجة الديناميكية

من خلال الاستفضاء من الخاصية شبه الخطية، يثبت المؤلفون أنه يمكن تمثيل $K_L$ و $K_U$ بالكامل بواسطة:

• متجه نسبة ($r$ أو $r'$) يلتقط عوامل القياس الثابتة من صف إلى آخر.
• مجموعة من متجهات حواف الكتل ($\eta$ أو $\eta'$) التي تلتقط القيم الفريدة عند حدود النمط الدرجي.

يتيح هذا التمثيل حساباً تكرارياً لضرب المصفوفة في المتجه ($K\psi$ و $K^\top\phi$). فبدلاً من حساب الضرب النقطي الكامل لكل صف، تقوم الخوارزمية بتحديث النتيجة بشكل تكراري:
$$p_{i+1} = r_i p_i + \eta_{i+1} \cdot \psi_{i+1}$$
يقلل هذا من تكلفة عملية ضرب مصفوفة بمتجه واحدة من $O(N^2)$ إلى $O(N)$.

4. التوسع إلى أبعاد أعلى

بالنسبة للمسائل ثنائية الأبعاد وأعلى، تتحلل مصفوفة النواة إلى حاصل ضرب كرونيكر (Kronecker product) لمصفوفات نواة أحادية البعد ($K = K_y \otimes K_x$). يوسع المؤلفون FINOM عبر تطبيق خوارزمية الضرب السريع أحادية البعد بالتتابع عبر كل اتجاه إحداثي. وهذا يحافظ على التعقيد الخطي بالنسبة لإجمالي نقاط الشبكة ($O(NM)$ في حالة 2D).

المساهمات الرئيسية

1. تعميم "سينكهورن السريع": توسع الورقة البحثية خوارزميات "سينكهورن السريعة" التي كانت مقتصرة سابقاً على الشبكات المنتظمة لتشمل الحالة العامة للشبكات غير المنتظمة.
2. مفهوم مؤشر التقسيم: تقديم مؤشر التقسيم لتقسيم مصفوفة النواة إلى كتل ذات بنى شبه خطية.
3. خوارزمية ذات تعقيد خطي: تطوير FINOM، التي تحقق تعقيد $O(N)$ لكل تكرار في 1D و$O(NM)$ في 2D، مع الحفاظ على دقة عمليات ضرب المصفوفة الأصلية (على عكس طرق التقريب).
4. التحقق العددي: تجارب مكثفة تؤكد أن FINOM تحقق تسريعاً بعدة مراتب عشرية مقارنة بخوارزمية "سينكهورن" القياسية، مع إنتاج خطط نقل لا يمكن تمييزها عن الطريقة القياسية (الفروقات عند دقة الآلة).

النتائج

أجرى المؤلفون تجارب عددية على مسائل أحادية وثنائية الأبعاد بتوزيعات عشوائية على عقد "تشيبيشيف" (Chebyshev) وعقد عشوائية غير منتظمة.

• أداء 1D: أظهرت FINOM نسب تسريع تتراوح بين $\approx 10^2$ إلى $\approx 10^3$ مع زيادة $N$ من 500 إلى 8,000. كان التوسع الملحوظ تقريباً $O(N^{1.13})$ لـ FINOM مقابل $O(N^{2.58})$ لـ "سينكهورن" القياسية.
• أداء 2D: بالنسبة لشبكات 2D ($N \times N$)، نما معدل التسريع بسرعة، متجاوزاً $10^4$ لشبكة $160 \times 160$. كان التوسع الملحوظ تقريباً $O(N^{1.74})$ لـ FINOM مقابل $O(N^{4.62})$ لـ "سينكهورن" القياسية.
• الدقة: في جميع الاختبارات، كانت معيار فوروبينيوس (Frobenius norm) للفرق بين خطط النقل ($\Delta \Gamma$) المحسوبة بواسطة FINOM وخوارزمية "سينكهورن" القياسية في حدود $10^{-17}$ إلى $10^{-18}$، مما يؤكد أن التسريع لا يمس الدقة العددية.

الأهمية والادعاءات

تدعي الورقة أن FINOM تعالج اختناقاً حرجاً في تطبيق النقل الأمثل على المسائل العملية التي تتضمن شبكات غير منتظمة (الشائعة في ديناميكا السوائل الحسابية والتمويل). ومن خلال استعادة التعقيد الخطي، تتيح الطريقة للممارسين استخدام الشبكات غير المنتظمة لتقليل عدد نقاط الشبكة المطلوبة للدقة دون تحمل التكلفة الحسابية الباهظة $O(N^2)$ للخوارزميات القياسية.

يؤكد المؤلفون أن نهجهم ليس تقريبياً؛ بل هو تسريع لعملية "سينكهورن" الدقيقة. ويشيرون إلى أنه بينما التعقيد النظري هو خطي، فإن الأسس المرصودة في التجارب (مثل $N^{1.13}$) أعلى قليلاً من 1، ويرجع ذلك على الأرجاح إلى أعباء التنفيذ الإضافية، ولكن النمو يظل أكثر تسطحاً بكثير من النمو التربيعي أو الأعلى لـ "الطرق القياسية". يضع هذا العمل أساساً لنقل أمثل عالي الكفاءة والدقة على التجزئات العامة غير المنتظمة.