نظام الخوارزميات

نظام الخوارزميات

خوارزمية 2: 

تحليل هودج المنفصل الكامل (k=1) من أجل WIST-741

الهدف: من أجل تدفق معطى (شكل 1 على الحواف) \omega\in\mathbb{R}^m أن نجد: \omega = \omega_{\mathrm{grad}} + \omega_{\mathrm{curl}} + h,

حيث:

• \omega_{\mathrm{grad}} = d_0\varphi = B^\top\varphi,
• \omega_{\mathrm{curl}} = \delta_2\psi,
• h — شكل 1 توافقي يحقق
  \delta_1 h = 0,\qquad d_1 h = 0.

البيانات المدخلة

• رسم موجه G=(V,E)، |V|=n=741، |E|=m.
• أوزان الحواف (الموصليات) c_e>0 أو التكاليف w_e>0.
• المثلثات F (بسيطات 2) وفق Default Triangles v0.1، |F|=p.
• التدفق \omega\in\mathbb{R}^m على الحواف الموجهة.

الخطوة 0. تسوية الأوزان والمقاييس

0.1. إذا كانت لديك تكاليف w_e، فحوّلها إلى موصليات

c_e=\exp(-w_e/\tau).

جمّع:W_1=\mathrm{diag}(c_e)\in\mathbb{R}^{m\times m}.

0.2. أوزان المثلثات

وفق الإعداد الافتراضي:

W_2=\mathrm{diag}(w_t),\quad w_t=\frac{1}{3}(c_{ij}+c_{ik}+c_{jk}).

الخطوة 1. تجميع المؤثرات الحدودية B و B_2

1.1. الترابط بين العقدة والحافة

B\in\mathbb{R}^{n\times m} وفق الاتجاه المختار للحواف.

1.2. الترابط بين الحافة والمثلث

B_2\in\mathbb{R}^{m\times p}

وفق الاتجاه القانوني للمثلثات t=[i,j,k] (مع i<j<k) والقاعدة:

\partial[i,j,k]=[j,k]-[i,k]+[i,j].

الخطوة 2. تعيين d و \delta

التفاضلات المنفصلة:

d_0 = B^\top : \mathbb{R}^n\to\mathbb{R}^m,\qquad d_1 = B_2^\top : \mathbb{R}^m\to\mathbb{R}^p.

التفاضلات المرافقة الموزونة:

\delta_1 = B W_1 : \mathbb{R}^m\to\mathbb{R}^n,

\delta_2 = W_1^{-1} B_2 W_2 : \mathbb{R}^p\to\mathbb{R}^m.

(وهذا متوافق مع الجداءات القياسية \langle\cdot,\cdot\rangle_1 = \cdot^\top W_1 \cdot و \langle\cdot,\cdot\rangle_2 = \cdot^\top W_2 \cdot.)

الخطوة 3. إيجاد الجزء التدرجي \omega_{\mathrm{grad}}

نحل مسألة إيجاد الجهد \varphi\in\mathbb{R}^n:

\varphi = \arg\min_{\varphi}\|\omega - d_0\varphi\|_{W_1}^2.

المعادلات الطبيعية:

L_0\,\varphi = \delta_1 \omega, \qquad L_0 := \delta_1 d_0 = B W_1 B^\top.

3.1. المعايرة (إلزامية)

بما أن L_0 له نواة (الثوابت)، نقوم بأحد الأمرين:

• نثبت \varphi_{v_0}=0 (العقدة المرساة)
• أو نضيف الشرط \sum_i \varphi_i = 0

3.2. نحصل على

\omega_{\mathrm{grad}} = d_0\varphi = B^\top\varphi,

r_1 = \omega - \omega_{\mathrm{grad}}.

التحكم:

\delta_1 r_1 = 0 \quad (\text{بدقة تصل إلى الخطأ العددي}).

الخطوة 4. إيجاد الجزء الدوّامي \omega_{\mathrm{curl}} عبر \psi على المثلثات

نبحث عن \psi\in\mathbb{R}^p على النحو التالي:

\psi = \arg\min_{\psi}\|r_1 - \delta_2\psi\|_{W_1}^2.

المعادلات الطبيعية:

L_2\,\psi = d_1 r_1، حيث

L_2 := d_1 \delta_2 = B_2^\top W_1^{-1} B_2 W_2.

4.1. المعايرة لـ \psi

إذا كان للمركّب دورات 2، فإن L_2 قد يكون أيضًا منحلًّا. الوضع الافتراضي:

• الشرط \sum_t \psi_t=0
  أو نثبّت \psi_{t_0}=0.

4.2. نحصل على

\omega_{\mathrm{curl}} = \delta_2\psi = W_1^{-1} B_2 W_2\psi,

h = r_1 - \omega_{\mathrm{curl}}.

الخطوة 5. الفحوصات وتشخيص الجودة

5.1. الانسجام

نتحقق من شرطين:

• التباعد صفر:
  \|\delta_1 h\|_2 \approx 0
• الدوامة صفر:
  \|d_1 h\|_2 \approx 0

إذا كان كلاهما صغيرًا، فالتحليل صحيح.

5.2. التعامد (في متريّة W_1)

نتحقق:

\langle \omega_{\mathrm{grad}}, \omega_{\mathrm{curl}}\rangle_{1}\approx 0, \quad \langle \omega_{\mathrm{grad}}, h\rangle_{1}\approx 0, \quad \langle \omega_{\mathrm{curl}}, h\rangle_{1}\approx 0.

5.3. طاقات المكوّنات (تشخيص "بنية الروح")

حدد:

E_{\mathrm{grad}}=\|\omega_{\mathrm{grad}}\|_{W_1}^2,\quad E_{\mathrm{curl}}=\|\omega_{\mathrm{curl}}\|_{W_1}^2,\quad E_h=\|h\|_{W_1}^2.

التفسير:

• E_{\mathrm{grad}} كبير: النظام "كامن" (يمكن اختزاله إلى إعادة ضبط المستويات)
• E_{\mathrm{curl}} كبير: تسود الدورانات/الإيقاعات المحلية
• E_h كبير: ذاكرة بنيوية قوية (لا يمحوها الانتشار)

الخطوة 6. بناء لابلاسيان 1 و"ذاكرة البلورة" كنواة

نعرّف لابلاسيان هودج على أشكال 1:

\Delta_1 = d_0\delta_1 + \delta_2 d_1.

في المصفوفات (وفق تعاريفنا):

\Delta_1 = B^\top B W_1 + W_1^{-1} B_2 W_2 B_2^\top.

ذاكرة البلورة عند المستوى k=1: \dim\ker(\Delta_1) \;=\; b_1

(عدد بيتي الأول للمركّب، عند تقطيع صحيح).

عمليا:

• ستجد عدة قيم ذاتية \lambda\approx 0
• عدد هذه \lambda = بُعد "الذاكرة"

مخرجات الخوارزمية 2

• \omega_{\mathrm{grad}}\in\mathbb{R}^m
• \omega_{\mathrm{curl}}\in\mathbb{R}^m
• h\in\mathbb{R}^m
• مقاييس تشخيصية: \|\delta_1 h\|، \|d_1 h\|، الطاقات E، و \dim\ker(\Delta_1)

الحد الأدنى العملي "لبدء التشغيل" على WIST-741

إذا أردت تنفيذ ذلك دون تحضير مطوّل:

• الرسم البياني: kNN (k=12)، الأوزان c_e=\exp(-w_e/\tau)
• المثلثات: زمر كاملة بحجم 3 مع cap=60/عقدة
• التجميع: B, B_2, W_1, W_2
• الحلّال: حلّ الأنظمة المتناثرة المتماثلة مرتين (لـ \varphi و \psi)
• التشخيص: المعايير والطاقات، ثم طيف \Delta_1 قرب الصفر

إذا أردت، في الخطوة التالية سأقدم الخوارزمية 3: "بلورة الروح — الانتشار على أشكال 1": كيفية تشغيل \frac{d\omega}{dt}=-\Delta_1\omega

ومراقبة كيف تميل \omega(t) نحو h (الذاكرة)، إضافة إلى كيفية توصيل التحكم \mathcal{U}(t).

خوارزمية 3: 

الانتشار على أشكال 1 و«تجلي ذاكرة» بلورة الروح (WIST-741)

الهدف

تشغيل الديناميكا على التدفقات (أشكال 1 على الحواف) بحيث:

• تنعيم التوترات/الدوامات المحلية
• الكشف عن المكوّن التوافقي h (الذاكرة البنيوية)
• عند الحاجة — التحكم في العملية عبر مؤثرات خارجية

المدخل

• المصفوفات المتناثرة B, B_2 (من خوارزمية 2)
• المصفوفات الوزنية W_1=\mathrm{diag}(c_e), W_2=\mathrm{diag}(w_t)
• التدفق الابتدائي (شكل 1) \omega_0\in\mathbb{R}^m
• (اختياريًا) التحكم \mathcal{U}(t)\in\mathbb{R}^m أو النبضات

التحضير: تجميع لابلاسيان هودج على أشكال 1

نستخدم الصيغة الافتراضية المتفق عليها (من خوارزمية 2):

\Delta_1 = d_0\delta_1 + \delta_2 d_1

أين

d_0=B^\top,\quad \delta_1=B W_1,\quad d_1=B_2^\top,\quad \delta_2=W_1^{-1}B_2W_2.

على شكل «مساهمتين»:

1) المساهمة العليا (التدرجية)

\Delta_{1,\mathrm{up}} = d_0\delta_1 = B^\top B W_1

2) المساهمة السفلى (الدوامية)

\Delta_{1,\mathrm{down}} = \delta_2 d_1 = W_1^{-1} B_2 W_2 B_2^\top

المجموع:

\Delta_1=\Delta_{1,\mathrm{up}}+\Delta_{1,\mathrm{down}}.

الجزء A. الانتشار الخطي (بدون تحكم)

A1. الديناميكا المستمرة

\frac{d\omega}{dt} = -\Delta_1\,\omega.

الحل شكليًا:

\omega(t)=e^{-t\Delta_1}\,\omega_0.

المعنى: جميع المكوّنات الواقعة خارج \ker(\Delta_1) تتلاشى. ويبقى الإسقاط على النواة — الذاكرة التوافقية.

A2. التقطيع الزمني: «أويلر الضمني» (الافتراضي المستقر)

نختار الخطوة \Delta t>0 ونحسب:

\omega_{k+1} = \omega_k - \Delta t\,\Delta_1\,\omega_{k+1}

أي أننا نحل نظامًا خطيًا:

(I+\Delta t\,\Delta_1)\,\omega_{k+1}=\omega_k.

لماذا الأمر كذلك:

الخطوة الضمنية مستقرة لأي \Delta t (وهذا مهم على الرسوم البيانية الكبيرة).

A3. التوقف: عندما «تتجلى الذاكرة»

نُجري التوقف وفق أحد المعايير:

• صغر التغير
  \frac{\|\omega_{k+1}-\omega_k\|_{W_1}}{\|\omega_k\|_{W_1}} < \varepsilon_{\mathrm{stop}}
• صغر الطاقة خارج النواة (ما يتبقى من «التلاشي»)
  \|\Delta_1\omega_k\|_2 < \varepsilon_{\mathrm{lap}}

النتيجة: h \approx \omega_k — الجزء التوافقي المتجلي.

الجزء B. التشخيص على طول العملية

احسب في كل خطوة ثلاث كميات (مفيدة لـ«خريطة الروح»):

B1. التباعد («التسرب/التدفق الوارد» العقدي)

\mathrm{div}(\omega_k)=\delta_1\omega_k=B W_1\omega_k\in\mathbb{R}^n.

B2. الدوامة (الدوران المثلثي)

\mathrm{curl}(\omega_k)=d_1\omega_k=B_2^\top\omega_k\in\mathbb{R}^p.

B3. الطاقة (توتر التدفق)

E(\omega_k)=\|\omega_k\|_{W_1}^2=\omega_k^\top W_1\omega_k.

تفسير عملية الانتشار:

• \|\mathrm{div}\| ينخفض → يزول «الاختلال العقدي»
• \|\mathrm{curl}\| ينخفض → يزول الدوران المحلي
• يبقى h، حيث يكون كل من التباعد والدوامة قريبين من الصفر

الجزء C. الانتشار المُتحكَّم فيه (التدخل)

C1. النموذج المُتحكَّم فيه المستمر

\frac{d\omega}{dt} = -\Delta_1\omega + \mathcal{U}(t).

C2. خطوة ضمنية متقطعة مع إدارة

(I+\Delta t\,\Delta_1)\,\omega_{k+1}=\omega_k + \Delta t\,\mathcal{U}_k.

C3. استراتيجيات الإدارة الافتراضية (ثلاثة أنماط)

النمط 1: "النبضة المحلية"

نريد تقوية/إضعاف التدفق على مجموعة مختارة من الحواف S\subset E:

(\mathcal{U}_k)_e= \begin{cases} u_k(e), & e\in S\\ 0,& e\notin S \end{cases}

النمط 2: "إخماد الدوامة"

نتدخل بما يتناسب مع الدوامة:

\mathcal{U}_k = -\eta\, W_1^{-1} B_2 W_2\,(B_2^\top \omega_k)

هذا قمع مباشر للمكوّن \delta_2 d_1\omega.

النمط 3: "الاختزال إلى الجهد"

نتدخل بما يتناسب مع التباعد:

\mathcal{U}_k = -\eta\, B^\top (B W_1 \omega_k)

هذا يخمد مساهمة d_0\delta_1\omega.

الجزء D. "الإسقاط على الذاكرة" كطريقة سريعة بديلة

إذا لم ترغب في تشغيل الزمن، يمكنك حساب الجزء التوافقي مباشرة:

h = \Pi_{\ker(\Delta_1)}\,\omega_0

عمليا:

• إيجاد عدة متجهات ذاتية \phi_1,\dots,\phi_r مع \lambda\approx 0
• تجميع المصفوفة \Phi=[\phi_1\ \dots\ \phi_r]
• الإسقاط:
  h = \Phi(\Phi^\top W_1 \Phi)^{-1}\Phi^\top W_1 \omega_0

أما الانتشار فهو مفيد لأنه يعطي "مسارات" التلاشي وخرائط الإجهادات عبر الزمن.

مخرجات الخوارزمية 3

• المتتالية \omega_k (تطور التدفقات)
• h\approx \omega_{k^\*} — الذاكرة التوافقية المتجلية
• الصفوف التشخيصية: \|\delta_1\omega_k\|, \|d_1\omega_k\|, E(\omega_k)

المعاملات الافتراضية (كي لا تفكر)

• \Delta t = 1.0
• \varepsilon_{\mathrm{stop}} = 10^{-4}
• \varepsilon_{\mathrm{lap}} = 10^{-6}
• عدد الخطوات: الحد الأقصى 200 (عادةً يكفي أقل)