Hierarchical proximal Galerkin: a fast $hp$-FEM solver for variational problems with pointwise inequality constraints

ملخص تقني: طريقة غاليركين القريبة الهرمية (hpG)

بيان المشكلة
تتناول الورقة البحثية الحل العددي للمسائل التباينية التي تتضمن قيود عدم تساوٍ نقطية، وتحديداً مسألة العائق ($u \leq \phi$) ومسألة التواء المرونة واللدونة المعممة (قيود من نوع التدرج، $|\nabla u| \leq \phi$). تنشأ هذه المسائل في مجالات متنوعة مثل التحكم الأمثل، وتحسين الطوبولوجيا، ونظرية المرونة. ويتمثل التحدي الكبير في حل هذه المسائل في المحدودية في انتظام الحل ($u \in H^s$ حيث $s < 5/2$)، حتى عندما تكون النطاق والبيانات سلسة. لقد فضل هذا السقف من الانتظام تقليدياً طرق العناصر المحدودة (FEM) منخفضة الرتبة، حيث كان يُنظر إلى الطرق عالية الرتبة على أنها تعاني من زيادة التكاليف الحسابية، وفقدان التشتت (sparsity)، ومعدلات تقارب تعتمد على الشبكة. علاوة على ذلك، تعتمد النهج عالية الرتبة الموجودة لهذه القيود غالباً على حلول مباشرة أو تظهر أعداد تكرار تعتمد على الشبكة، مما يحد من قابليتها للتوسع.

المنهجية
يقترح المؤلف خوارزمية غاليركين القريبة الهرمية (hpG)، وهي محلل عالي الرتبة يستفيد من طريقة النقطة القريبة للمتغيرات الكامنة (LVPP) التي قدمها كيث وسوروييك. وتتضمن المنههجية الجوهرية ما يلي:

1. استراتيجية التجزئة (Discretization): يتم تجزئة أنظمة نقطة السرج (saddle-point) الخاصة بـ LVPP باستخدام أساس FEM هرمي-p.

   • يتم تجزئة المتغير الأصلي $u$ في فضاء متصل متوافق مع $H^1$ باستخدام دوال شكل هرمية (متعددات حدود جاكوبي الموزونة والدوال القبعية).
   • يتم تججئة المتغير الكامن $\psi$ في فضاء غير متصل متوافق مع $L^2$ باستخدام متعددات حدود ليجاندر الموزونة والمترجمة.
   • تم اختيار هذا الاقتران المحدد (متصل $p$ لـ $u$، وغير متصل $p-2$ أو $p-1$ لـ $\psi$) لتحقيق استقرار inf-sup مع الحفاظ على التشتت.

2. خطيّة نيوتن (Newton Linearization): يتم خطيّة الأنظمة غير الخطية الناتجة عبر طريقة نيوتن، مما ينتج أنظمة خطية متناظرة لنقطة السرج. ومن الأهمية بمكان أن اختيار الأساس غير المتصل لـ $\psi$ يضمن أن تؤدي خطيّة الحد غير الخطي إلى مصفوفة ذات هيكل قطري كتلي، مما يمنع مصفوفات الصلابة والكتلة من أن تصبح كثيفة مع زيادة درجة متعدد الحدود $p$.

3. المُمهدات والمحللات (Preconditioning and Solvers):

   • يتم حل الأنظمة الخطية باستخدام طريقة الفضاء الجزئي كرينلوف (Krylov subspace) ذات الممهد الكتلي (FGMRES للدورة الخارجية، وGMRES لحلول مكمل شير (Schur complement) الداخلية).
   • يتم إنشاء ممهد قطري كتلي لمكمل شير. بالنسبة لمسائل العائق، يتضمن ذلك تقريب مكمل شير باستخدام أساس غاليركين طيفي للحفاظ على التشتت. بالنسبة لقيود نوع التدرج، يتم استخدام تقريب أبسط.
   • يستغل المحلل التحويلات السريعة (عبر تحويل جيب التمام المنفصل - DCT) لتجميع وتطبيق المصفوفات، لا سيال الأساس غير المتصل، محققاً تعقيداً شبه أمثل.
   • تدعم الطريقة التكيفية $hp$، باستخدام مقدرات الخطأ اللاحقة (a posteriori error estimators) لتوجيه تحسين الشبكة وزيادة درجة متعدد الحدود.

المساهمات الرئيسية
تقدم الورقة البحثية المساهمات المحددة التالية:

• أول الممهدات للقيود عالية الرتبة: طور المؤلف أول الممهدات لأنظمة نيوتن الناشئة عن طرق غاليركين القريبة لمسائل العائق وقيود نوع التدرج. وقد ثبت أن هذه الممهدات فعالة للغاية.
• الحفاظ على التشتت (Sparsity Preservation): من خلال استخدام اقتران أساس هرمي محدد، تحتفظ الطريقة بالتشتت في أنظمة نيوتن المجزأة حتى مع اقتراب $p$ من اللانهاية، مما يتغلب على حاجز رئيسي أمام الطرق عالية الرتبة.
• القوة تجاه $hp$($hp$-Robustness): تظهر الخوارزمية استقلالية في عدد تكرارات نيوتن (غير الخطية) المطلوبة للتقارب فيما يتعلق بالشبكة ($h$) ودرجة متعدد الحدود ($p$). وتظهر تكرارات كرينلوف الداخلية نمواً لوغاريتمياً متعدد الحلقات (polylogarithmic) فقط فيما يتعلق بـ $h \to 0$ و $p \to \infty$.
• الأداء التنافسي: تقدم الورقة أول مقارنات زمن تنفيذ (wall-clock timing) تنافسية مسجلة تظهر أن التجزئات عالية الرتبة يمكن أن تكون أسرع بكثير من نظيراتها منخفضة الرتبة لهذه المسائل، خاصة عندما تظهر المسألة بنية ضرب تنسوري (tensor-product structure).
• القدرة على الدرجات العالية: يتعامل المحلل بنجاح مع التجزئات ذات درجات متعدد حدود عالية جداً (تصل إلى $p=82$ في كل عنصر، مما ينتج إجمالي درجات تصل إلى 164 في 2D)، وهو ما كان غير قابل للتحقيق سابقاً لمثل هذه المسائل المقيدة باستخدام المحللات التكرارية.

النتائج
يتحقق المؤلف من صحة خوارزمية hpG من خلال خمسة أمثلة عددية:

1. مسألة العائق التذبذبية في 1D: توضح أن استراتيجيات التكيف $hp$تحقق معدلات تقارب قدرها$O((h/p)^{10})$، مما يتفوق بشكل كبير على التحسين المنتظم. يتطلب المحلل عدداً محدوداً من تكرارات نيوتن بغض النظر عن التحسين.
2. مسألة العائق في 2D: تظهر أن التجزئات عالية الرتبة تحقق أخطاء أصغر لكل درجة حرية (dof) ولكل وحدة زمن تنفيذ مقارنة بالطرق منخفضة الرتبة ($p=1$). لوحظ أن محلل hpG أسرع بما يصل إلى 24 مرة في كل عملية حل خطي من استراتيجية المجموعة النشطة الثنائية الأصلية (PDAS) منخفضة الرتبة للوصول إلى نفس حد الخطأ.
3. قيد من نوع التدرج في 2D: تؤكد القوة تجاه $hp$(74–78 تكرار نيوتن) والتقارب الفائق ($O(h^p)$) عندما تتماشى الشبكة مع عدم استمرارية القيد. وُجد أن الطرق عالية الرتبة ($p > 1$) أسرع بنحو 100 مرة من الطرق منخفضة الرتبة للوصول إلى خطأ محدد.
4. مسألة التشكيل الحراري شبه التباينية (QVI): يطبق المحلل على مسألة QVI معقدة من نوع العائق مع تكرار النقطة الثابتة. تتعامل الطريقة بنجاح مع أعلى تجزئة من نوع العائق لـ QVI تم تسجيلها في الأدبيات حتى الآن ($p=82$).
5. مسألة العائق في 3D: توسع الطريقة نطاقها إلى ثلاثة أبعاد، موضحة أنه بينما يصبح تحليل تشوليسكي (Cholesky factorization) غير قابل للتنفيذ للأنظمة الكبيرة، فإن المحلل التكراري المقترح مع ممهد AMG يظل فعالاً.

الأهمية والادعاءات
تدعي الورقة أن خوارزمية hpG تتحدى بشكل أساسي المفهوم السائد بأن التجزئات منخفضة الرتبة هي الخيار الوحيد الممكن للمسائل ذات القيود النقطية بسبب حدود انتظام الحل. ويؤكد المؤلف أن:

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

يظل المؤلف متواضعاً فيما يتعلق بالتعميمات، مشيراً إلى أن التنفيذ الحالي يعتمد على شبكات الضرب التنسوري (Cartesian)، وأن التوسعات إلى خلايا غير كارتيزية أو استراتيجيات $p$-multigrid تظل مجالات مفتوحة للعمل المستقبلي.