LOBPCG

📅 آخر تحديث: ٢ أغسطس ٢٠٢٦
✍️ نُشر في: ٢ أغسطس ٢٠٢٦
📷 يحتوي على 45 صور
الموسوعة الحرة

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

أx=λبx،{\displaystyle Ax=\lambda Bx,}

بالنسبة لزوج معين(أ،ب){\displaystyle (A,B)}من المصفوفات الهرميتية المعقدة أو المصفوفات المتناظرة الحقيقية ، حيث المصفوفةب{\displaystyle B}ويُفترض أيضاً أنها موجبة تماماً .

خلفية

اقترح كانتوروفيتش في عام 1948 حساب أصغر قيمة ذاتيةλ1{\displaystyle \lambda _{1}}لمصفوفة متناظرةأ{\displaystyle A}عن طريق الانحدار الأشد باستخدام اتجاهر=أx-λ(x)x{\displaystyle r=Ax-\lambda (x)x}من تدرج مُقاس لحاصل رايليλ(x)=⟨x،أx⟩/⟨x،x⟩{\displaystyle \lambda (x)=\langle x,Ax\rangle /\langle x,x\rangle }في حاصل ضرب قياسي⟨x،y⟩=xتيy{\displaystyle \langle x,y\rangle =x^{\mathsf {T}}y}، حيث يتم حساب حجم الخطوة عن طريق تقليل حاصل قسمة رايلي في المدى الخطي للمتجهاتx{\displaystyle x}ور{\displaystyle r}أي بطريقة مثلى محليًا. اقترح ساموكيش [ 1 ] تطبيق مُهيئ مسبقتي{\displaystyle T}إلى متجه الباقير{\displaystyle r}لتوليد الاتجاه المشروط مسبقًاw=تير{\displaystyle w=Tr}والمقاربة المشتقة، كماx{\displaystyle x}يقترب من المتجه الذاتي ، وحدود معدل التقارب. اقترح دياكونوف [ 2 ] التكييف المسبق المكافئ طيفيًا واستنتج حدودًا غير تقاربية لمعدل التقارب. وُصفت طريقة الانحدار الأسرع متعدد الخطوات الأمثل محليًا للكتلة لمسائل القيم الذاتية في [ 3 ] . ظهر التصغير المحلي لحاصل رايلي على الفضاء الفرعي الذي يمتد عليه التقريب الحالي، والباقي الحالي، والتقريب السابق، بالإضافة إلى نسخته الكتلية، في [ 4 ] . تم تحليل النسخة المُكيَّفة مسبقًا في [ 5 ] و [ 6 ] .

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

المصدر: [ 7 ]

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

الخوارزمية

نسخة المتجه الواحد

مقدمة: انحدار التدرج لمسائل القيم الذاتية

تُجري هذه الطريقة عملية تعظيم (أو تصغير) متكررة لمعامل رايلي المعمم

ρ(x):=ρ(أ،ب؛x):=xتيأxxتيبx،{\displaystyle \rho (x):=\rho (A,B;x):={\frac {x^{\mathsf {T}}Ax}{x^{\mathsf {T}}Bx}},}

مما يؤدي إلى إيجاد أكبر (أو أصغر) أزواج القيم الذاتية لـأx=λبx.{\displaystyle Ax=\lambda Bx.}

اتجاه الانحدار الأشد، وهو ميل حاصل قسمة رايلي المعمم، يتناسب طرديًا مع المتجه

ر:=أx-ρ(x)بx،{\displaystyle r:=Ax-\rho (x)Bx,}

يُطلق عليه اسم الباقي المتجه الذاتي . إذا كان هناك مُهيئ مسبقتي{\displaystyle T}إذا كانت متاحة، يتم تطبيقها على الباقي وتعطي المتجه

w:=تير،{\displaystyle w:=Tr,}

يُطلق عليه اسم الباقي المُهيأ مسبقًا. بدون تهيئة مسبقة، نُحددتي:=أنا{\displaystyle T:=I}وهكذاw:=ر{\displaystyle w:=r}طريقة تكرارية

xأنا+1:=xأنا+αأناتي(أxأنا-ρ(xأنا)بxأنا)،{\displaystyle x^{i+1}:=x^{i}+\alpha ^{i}T\left(Ax^{i}-\rho (x^{i})Bx^{i}\right),}

أو باختصار،

xأنا+1:=xأنا+αأناwأنا،wأنا:=تيرأنا،رأنا:=أxأنا-ρ(xأنا)بxأنا،{\displaystyle {\begin{aligned}x^{i+1}&:=x^{i}+\alpha ^{i}w^{i},\,\\w^{i}&:=Tr^{i},\,\\r^{i}&:=Ax^{i}-\rho (x^{i})Bx^{i},\end{aligned}}}

يُعرف هذا باسم الصعود (أو الهبوط) الأكثر انحدارًا المشروط مسبقًا، حيث يكون العدد القياسيαأنا{\displaystyle \alpha ^{i}}يُطلق عليه حجم الخطوة. ويمكن تحديد حجم الخطوة الأمثل من خلال تعظيم معامل رايلي، أي

xأنا+1:=arg⁡الأعلىy∈فترة⁡{xأنا،wأنا}ρ(y){\displaystyle x^{i+1}:=\arg \max _{y\in \operatorname {span} \{x^{i},w^{i}\}}\rho (y)}

(أوarg⁡مين{\displaystyle \arg \min }في حالة التقليل)، وفي هذه الحالة تسمى الطريقة الأمثل محليًا.

تكرار ثلاث فترات

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

xأنا+1:=arg⁡الأعلىy∈فترة⁡{xأنا،wأنا،xأنا-1}ρ(y){\displaystyle x^{i+1}:=\arg \max _{y\in \operatorname {span} \{x^{i},w^{i},x^{i-1}\}}\rho (y)}

(يستخدمarg⁡مين{\displaystyle \arg \min }في حالة التصغير). يمكن إجراء تعظيم/تصغير حاصل قسمة رايلي في فضاء فرعي ثلاثي الأبعاد عدديًا باستخدام طريقة رايلي-ريتز . إضافة المزيد من المتجهات، انظر على سبيل المثال، استقراء ريتشاردسون ، لا يؤدي إلى تسريع ملحوظ [ 8 ] ولكنه يزيد من تكاليف الحساب، لذا لا يُنصح به عمومًا.

تحسينات في الاستقرار العددي

مع تقارب التكرارات، تصبح المتجهاتxأنا{\displaystyle x^{i}}وxأنا-1{\displaystyle x^{i-1}}تصبح هذه المتغيرات مرتبطة خطيًا تقريبًا ، مما يؤدي إلى فقدان الدقة ويجعل طريقة رايلي-ريتز غير مستقرة عدديًا في وجود أخطاء التقريب. ويمكن تجنب فقدان الدقة عن طريق استبدال المتجه.xأنا-1{\displaystyle x^{i-1}}مع متجهصأنا{\displaystyle p^{i}}، والتي قد تكون أبعد منxأنا{\displaystyle x^{i}}، في أساس الفضاء الفرعي ثلاثي الأبعادفترة⁡{xأنا،wأنا،xأنا-1}{\displaystyle \operatorname {span} \{x^{i},w^{i},x^{i-1}\}}مع الحفاظ على الفضاء الجزئي دون تغيير وتجنب التعامد أو أي عمليات إضافية أخرى. [ 8 ] علاوة على ذلك، قد يكون من الضروري تعامد أساس الفضاء الجزئي ثلاثي الأبعاد في مسائل القيم الذاتية سيئة التكييف لتحسين الاستقرار والدقة الممكنة.

نظائر فضاء كريلوف الجزئي

هذه نسخة أحادية المتجه من طريقة LOBPCG، وهي إحدى التعميمات الممكنة لحلول التدرج المترافق الخطي المُهيأ مسبقًا لحالة مسائل القيم الذاتية المتناظرة . [ 8 ] حتى في الحالة البسيطةتي=أنا{\displaystyle T=I}وب=أنا{\displaystyle B=I}التقريب الناتج معأنا>3{\displaystyle i>3}سيكون مختلفًا عن ذلك الذي تم الحصول عليه بواسطة خوارزمية لانكزوس ، على الرغم من أن كلا التقريبين سينتميان إلى نفس فضاء كريلوف الفرعي .

سيناريوهات الاستخدام العملي

إن البساطة الشديدة والكفاءة العالية لإصدار المتجه الواحد من LOBPCG تجعله جذابًا للتطبيقات المتعلقة بالقيم الذاتية في ظل قيود الأجهزة الشديدة، بدءًا من الكشف عن الشذوذ في الوقت الحقيقي القائم على التجميع الطيفي عبر تقسيم الرسم البياني على ASIC أو FPGA المضمنة وصولًا إلى نمذجة الظواهر الفيزيائية ذات التعقيد الحسابي القياسي على أجهزة الكمبيوتر العملاقة TOP500 ذات الأداء الفائق .

نسخة الكتلة

ملخص

يمكن حساب أزواج القيم الذاتية اللاحقة واحدًا تلو الآخر باستخدام خوارزمية LOBPCG أحادية المتجه مع إضافة انكماش متعامد، أو بشكل متزامن كوحدة واحدة. في الطريقة الأولى، تؤثر عدم الدقة في القيم الذاتية التقريبية المحسوبة مسبقًا بشكل تراكمي على دقة القيم الذاتية المحسوبة لاحقًا، مما يزيد الخطأ مع كل عملية حساب جديدة. يسمح تكرار عدة قيم ذاتية تقريبية معًا في وحدة واحدة بطريقة مثلى محليًا في نسخة LOBPCG [ 8 ] بحساب سريع ودقيق وموثوق للقيم الذاتية، بما في ذلك تلك التي تتوافق مع القيم الذاتية المتعددة تقريبًا، حيث تعاني خوارزمية LOBPCG أحادية المتجه من بطء التقارب. يمكن ضبط حجم الوحدة لتحقيق التوازن بين الاستقرار العددي وسرعة التقارب وتكاليف الحوسبة لعمليات التعامد وطريقة رايلي-ريتز في كل تكرار.

التصميم الأساسي

يستبدل أسلوب الكتل في LOBPCG المتجهات المفردةxأنا،wأنا،{\displaystyle x^{i},\,w^{i},}وصأنا{\displaystyle p^{i}}باستخدام متجهات الكتل، أي المصفوفاتXأنا،دبليوأنا،{\displaystyle X^{i},\,W^{i},}وPأنا{\displaystyle P^{i}}، حيث، على سبيل المثال، كل عمود منXأنا{\displaystyle X^{i}}يُقارب أحد المتجهات الذاتية. يتم تكرار جميع الأعمدة في وقت واحد، ثم يتم إنشاء مصفوفة المتجهات الذاتية التقريبية التالية.Xأنا+1{\displaystyle X^{i+1}}يتم تحديدها بواسطة طريقة رايلي-ريتز على الفضاء الجزئي الممتد بواسطة جميع أعمدة المصفوفاتXأنا،دبليوأنا،{\displaystyle X^{i},\,W^{i},}وPأنا{\displaystyle P^{i}}كل عمود مندبليوأنا{\displaystyle W^{i}}يتم حسابها ببساطة على أنها الباقي المشروط مسبقًا لكل عمود منXأنا.{\displaystyle X^{i}.}المصفوفةPأنا{\displaystyle P^{i}}يتم تحديدها بحيث تكون الفضاءات الفرعية التي تمتد عليها أعمدة[Xأنا،Pأنا]{\displaystyle [X^{i},\,P^{i}]}و من[Xأنا،Xأنا-1]{\displaystyle [X^{i},\,X^{i-1}]}هما متماثلان.

الاستقرار العددي مقابل الكفاءة

تُحدد نتيجة طريقة رايلي-ريتز بواسطة الفضاء الجزئي الذي تشكله جميع أعمدة المصفوفات.Xأنا،دبليوأنا،{\displaystyle X^{i},\,W^{i},}وPأنا{\displaystyle P^{i}}حيث يمكن نظريًا أن تكون قاعدة الفضاء الجزئي اختيارية. مع ذلك، في الحساب الحاسوبي غير الدقيق، تصبح طريقة رايلي-ريتز غير مستقرة عدديًا إذا كانت بعض متجهات القاعدة مرتبطة خطيًا تقريبًا. عادةً ما تحدث حالات عدم الاستقرار العددي، على سبيل المثال، إذا وصلت بعض المتجهات الذاتية في الكتلة التكرارية إلى دقة قابلة للتحقيق لدقة حاسوبية معينة، وتكون هذه الحالات بارزة بشكل خاص في الدقة المنخفضة، مثل الدقة المفردة .

يكمن فنّ تطبيق خوارزمية LOBPCG في ضمان الاستقرار العددي لطريقة رايلي-ريتز بأقل تكلفة حسابية ممكنة، وذلك باختيار أساس جيد للفضاء الجزئي. ويُعدّ النهج الأكثر استقرارًا، والذي يتمثل في جعل متجهات الأساس متعامدة، كما في عملية غرام-شميدت ، الأكثر تكلفة حسابية. فعلى سبيل المثال، تستخدم تطبيقات LOBPCG [ 9 ] و [ 10 ] تحليل تشوليسكي غير المستقر ولكنه فعال للمصفوفة العادية ، والذي يُجرى فقط على المصفوفات الفردية.دبليوأنا{\displaystyle W^{i}}وPأنا{\displaystyle P^{i}}بدلاً من ذلك، على كامل المساحة الفرعية. تسمح الزيادة المستمرة في حجم ذاكرة الحاسوب بأحجام كتل نموذجية في الوقت الحاضر في103-104{\displaystyle 10^{3}-10^{4}}النطاق، حيث تبدأ النسبة المئوية لوقت الحوسبة الذي يقضيه في عمليات التعامد وطريقة رايلي-ريتز في السيطرة.

تثبيت المتجهات الذاتية المتقاربة سابقًا

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

يمكن تطبيق آلية القفل بطرق مختلفة مع الحفاظ على الدقة العددية والاستقرار وتقليل تكاليف الحساب. على سبيل المثال، تتبع تطبيقات LOBPCG [ 9 ] [ 10 ] [ 8 ] [ 11 ] الفصل بين القفل الصارم، أي الانكماش عن طريق التقييد، حيث تعمل المتجهات الذاتية المقفلة كمدخل للبرنامج ولا تتغير، والقفل المرن، حيث لا تشارك المتجهات المقفلة في الخطوة التكرارية الأكثر تكلفة عادةً لحساب البواقي، ولكنها تشارك بشكل كامل في طريقة رايلي-ريتز، وبالتالي يُسمح بتغييرها بواسطة هذه الطريقة.

التعديلات، LOBPCG II

تتضمن LOBPCG جميع أعمدة المصفوفاتXأنا،دبليوأنا،{\displaystyle X^{i},\,W^{i},}وPأنا{\displaystyle P^{i}}في طريقة رايلي-ريتز مما ينتج عنه ما يصل إلى3ك{\displaystyle 3k}-بواسطة-3ك{\displaystyle 3k}مسألة القيم الذاتية التي يجب حلها وما يصل إلى9ك2{\displaystyle 9k^{2}}يتم حساب حاصل الضرب النقطي في كل تكرار، حيثك{\displaystyle k}يشير إلى حجم الكتلة - عدد الأعمدة. بالنسبة لأحجام الكتل الكبيرةك{\displaystyle k}يبدأ هذا في السيطرة على تكاليف الحوسبة والإدخال/الإخراج والحد من التوازي، حيث تعمل أجهزة الحوسبة المتعددة في وقت واحد.

تصف الورقة الأصلية لـ LOBPCG [ 8 ] تعديلًا يُسمى LOBPCG II، لمعالجة هذه المشكلة عن طريق تشغيل نسخة المتجه الواحد من طريقة LOBPCG لكل زوج ذاتي مطلوب مع إجراء Rayleigh-Ritz لحلك{\displaystyle k}من مسائل القيم الذاتية المسقطة 3×3. إجراء رايلي-ريتز العالمي لجميعك{\displaystyle k}يتم حساب القيم الذاتية في كل تكرار ولكن فقط على أعمدة المصفوفةXأنا{\displaystyle X^{i}}وبالتالي تقليل عدد عمليات الضرب النقطي اللازمة لـك2+3ك{\displaystyle k^{2}+3k}من9ك2{\displaystyle 9k^{2}}وحجم مسألة القيم الذاتية المتوقعة العالمية لـك{\displaystyle k}-بواسطة-ك{\displaystyle k}من3ك{\displaystyle 3k}-بواسطة-3ك{\displaystyle 3k}في كل تكرار. يذهب المرجع [ 12 ] إلى أبعد من ذلك، حيث يطبق خوارزمية LOBPCG على كل متجه ذاتي تقريبي على حدة، أي تشغيل النسخة غير المحظورة من طريقة LOBPCG لكل زوج ذاتي مطلوب لعدد ثابت من التكرارات. لا تحتاج إجراءات رايلي-ريتز في هذه العمليات إلا إلى حل مجموعة من مسائل القيم الذاتية المسقطة 3 × 3. يتم تطبيق إجراء رايلي-ريتز الشامل لجميع الأزواج الذاتية المطلوبة بشكل دوري فقط في نهاية عدد ثابت من تكرارات LOBPCG غير المحظورة.

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

نظرية التقارب وتطبيقها

يضمن تصميم خوارزمية LOBPCG [ 8 ] تقليل حاصل قسمة رايلي بمعدل لا يقل عن معدل انحدار التدرج الكتلي ، الذي يتمتع بنظرية تقارب شاملة. كل متجه ذاتي هو نقطة ثابتة لحاصل قسمة رايلي ، حيث ينعدم التدرج . وبالتالي، قد يتباطأ انحدار التدرج في جوار أي متجه ذاتي ، إلا أنه من المضمون إما أن يتقارب إلى هذا المتجه بمعدل تقارب خطي، أو إذا كان هذا المتجه نقطة سرجية ، فمن المرجح أن ينخفض ​​حاصل قسمة رايلي التكراري إلى ما دون القيمة الذاتية المقابلة ويبدأ بالتقارب خطيًا إلى القيمة الذاتية التالية. وقد حُددت أسوأ قيمة لمعدل التقارب الخطي [ 8 ] ، وهي تعتمد على الفجوة النسبية بين القيمة الذاتية وبقية طيف المصفوفة ، وعلى جودة المُهيئ المسبق ، إن وُجد.

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

على عكس طريقة لانكزوس ، نادراً ما تُظهر طريقة LOBPCG تقاربًا فائق الخطية في الممارسة العملية.

تحليل المكونات الرئيسية الجزئية (PCA) وتحليل القيم المفردة (SVD)

يمكن تكييف خوارزمية LOBPCG بسهولة لحساب عدة قيم مفردة كبيرة ومتجهاتها المفردة المقابلة (تحليل القيم المفردة الجزئي)، على سبيل المثال، للحساب التكراري لتحليل المكونات الرئيسية (PCA) لمصفوفة بيانات D ذات متوسط ​​صفري، دون الحاجة إلى حساب مصفوفة التغاير D<sub> T</sub> D صراحةً ، أي بطريقة لا تعتمد على المصفوفات . تتمثل العملية الحسابية الرئيسية في تقييم دالة حاصل ضرب D<sub> T</sub> ( D<sub> X</sub> ) لمصفوفة التغاير D<sub> T </sub> D ومتجه الكتلة X ، والتي تُقارب بشكل تكراري المتجهات المفردة المطلوبة. يحتاج تحليل المكونات الرئيسية (PCA) إلى أكبر القيم الذاتية لمصفوفة التغاير، بينما تُنفذ خوارزمية LOBPCG عادةً لحساب أصغرها. يتمثل الحل البسيط في عكس إشارة الدالة، باستبدال −D <sub> T</sub> ( D<sub> X</sub> ) بـ D <sub>T</sub> ( D<sub> X</sub> ) ، وبالتالي عكس ترتيب القيم الذاتية، لأن خوارزمية LOBPCG لا تُعنى بما إذا كانت مصفوفة مسألة القيم الذاتية موجبة التحديد أم لا. [ 9 ]

تم تطبيق LOBPCG لـ PCA و SVD في SciPy منذ الإصدار 1.4.0 [ 13 ]

تطبيقات البرمجيات العامة

قام مخترع LOBPCG، أندرو كنيازيف ، بنشر تطبيق مرجعي يسمى Block Locally Optimal Preconditioneigenvalue Xolvers (BLOPEX) [ 14 ] [ 15 ] مع واجهات لـ PETSc و hypre و Parallel Hierarchical Adaptive MultiLevel method (PHAML). [ 16 ] تتوفر تطبيقات أخرى في، على سبيل المثال، GNU Octave ، [ 17 ] MATLAB (بما في ذلك المصفوفات الموزعة أو المتراصة)، [ 9 ] Java ، [ 18 ] Anasazi ( Trilinos )، [ 19 ] SLEPc ، [ 20 ] [ 21 ] SciPy ، [ 10 ] Julia ، [ 22 ] MAGMA، [ 23 ] Pytorch ، [ 24 ] Rust ، [ 25 ] OpenMP و OpenACC ، [ 26 ] CuPy ( مكتبة مصفوفات متوافقة مع NumPy مُسرّعة بواسطة CUDA )، [ 27 ] Google JAX ، [ 28 ] و NVIDIA AMGX. [ 29 ] تم تنفيذ LOBPCG، [ 30 ] ولكنها غير مُضمنة، في TensorFlow .

التطبيقات

استخراج البيانات

تستخدم حزم البرامج scikit-learn وMegaman [ 31 ] خوارزمية LOBPCG لتوسيع نطاق التجميع الطيفي [ 32 ] وتعلم التنوع [ 33 ] عبر خرائط لابلاس الذاتية لمجموعات البيانات الكبيرة. وقد قامت NVIDIA بتطبيق [ 34 ] خوارزمية LOBPCG في مكتبة nvGRAPH الخاصة بها، والتي تم تقديمها في CUDA 8. أما Sphynx [ 35 ] ، وهو مُقسِّم رسوم بيانية متوازي هجين يدعم الذاكرة الموزعة والمشتركة - وهو أول أداة لتقسيم الرسوم البيانية تعمل على وحدات معالجة الرسومات في بيئات الذاكرة الموزعة - فيستخدم التجميع الطيفي لتقسيم الرسوم البيانية ، حيث يحسب المتجهات الذاتية على مصفوفة لابلاس للرسم البياني باستخدام خوارزمية LOBPCG من حزمة Anasazi .

علوم المواد

تم تطبيق خوارزمية LOBPCG في برنامج ABINIT [ 36 ] (بما في ذلك إصدار CUDA ) وبرنامج Octopus [ 37 ] . وقد استُخدمت هذه الخوارزمية لحساب مصفوفات ضخمة بحجم مليارات المليارات من قِبل الباحثين المتأهلين للتصفيات النهائية لجائزة غوردون بيل ، على حاسوب Earth Simulator العملاق في اليابان [ 38 ] [ 39 ] . كما يستخدم نموذج هوبارد لأنظمة الإلكترونات ذات الارتباط القوي، لفهم آلية الموصلية الفائقة ، خوارزمية LOBPCG لحساب الحالة الأرضية للهاميلتوني على حاسوب K [ 40 ] وأنظمة متعددة وحدات معالجة الرسومات [ 41 ] .

توجد نسخ من برنامج LOBPCG مكتوبة بلغة MATLAB [ 42 ] ولغة Julia [ 43 ] [ 44 ] لحل معادلات كون-شام ونظرية الكثافة الوظيفية (DFT) باستخدام أساس الموجة المستوية. وتشمل التطبيقات الحديثة TTPY [ 45 ] ، وPlatypus-QM [ 46 ] ، وMFDn [ 47 ] ، وACE-Molecule [ 48 ] ، وLACONIC [ 49 ] .

الميكانيكا والسوائل​

تُستخدم مكتبة LOBPCG من BLOPEX لإعداد المُهيئ في مكتبة BDDCML لحل المعادلات متعددة المستويات لتحليل المجال بواسطة القيود (BDDC)، والمدمجة في مكتبة OpenFTL ( مكتبة قوالب العناصر المحدودة المفتوحة ) ومحاكي Flow123d لتدفق المياه الجوفية، وانتقال المواد المذابة والحرارة في الأوساط المسامية المتشققة . وقد تم تطبيق LOBPCG [ 50 ] في LS-DYNA وبشكل غير مباشر في ANSYS [ 51 ] .

معادلات ماكسويل

يُعدّ LOBPCG أحد خوارزميات حلّ القيم الذاتية الأساسية في برنامج PYFEMax وبرنامج Netgen/NGSolve عالي الأداء للعناصر المحدودة متعددة الفيزياء. وقد دُمج LOBPCG من شركة hypre في مكتبة MFEM مفتوحة المصدر، وهي مكتبة C ++ خفيفة الوزن وقابلة للتوسع ، تُستخدم في العديد من المشاريع، بما في ذلك BLAST وXBraid و VisIt وxSDK ومعهد FASTMath في SciDAC ومركز التصميم المشترك لتقسيمات الحوسبة فائقة السرعة (CEED) ضمن مشروع الحوسبة فائقة السرعة .

إزالة الضوضاء

يمكن استخدام مرشح التمرير المنخفض التقريبي القائم على LOBPCG التكراري لإزالة الضوضاء ؛ انظر، [ 52 ] على سبيل المثال، لتسريع إزالة الضوضاء بالتغير الكلي .

تجزئة الصور

تُجري عملية تجزئة الصور باستخدام التجميع الطيفي تضمينًا منخفض الأبعاد باستخدام مصفوفة تقارب بين البكسلات، يليه تجميع مكونات المتجهات الذاتية في الفضاء منخفض الأبعاد، على سبيل المثال، باستخدام لابلاس الرسم البياني للمرشح الثنائي . وقد طُرحت تجزئة الصور باستخدام تقسيم الرسم البياني الطيفي بواسطة LOBPCG مع التكييف المسبق متعدد الشبكات لأول مرة في [ 53 ] ، وتم اختبارها فعليًا في [ 54 ] و [ 55 ] . ثم طُبّق هذا النهج الأخير لاحقًا في بايثون باستخدام مكتبة scikit-learn [ 56 ] ، والتي تستخدم LOBPCG من SciPy مع التكييف المسبق الجبري متعدد الشبكات لحل مشكلة القيم الذاتية للابلاس الرسم البياني.

مراجع

  1. ↑ ساموكيش، بكالوريوس (1958). "طريقة الانحدار الأسرع لمسألة القيم الذاتية ذات المؤثرات شبه المحدودة". إزفستيا فوزوف، الرياضيات (5): 105-114 .
  2. ↑ دياكونوف، إي جي (1996). التحسين في حل المسائل الإهليلجية . مطبعة سي آر سي. ص 592. ISBN  978-0-8493-2872-5.
  3. ↑ كولوم، جين ك .؛ ويلوبي، رالف أ. (2002). خوارزميات لانكزوس لحسابات القيم الذاتية المتناظرة الكبيرة. المجلد 1 (إعادة طبع للأصل الصادر عام 1985) . جمعية الرياضيات الصناعية والتطبيقية .
  4. ↑ كنيازيف، أندرو ف. (1987). "تقديرات معدل التقارب للطرق التكرارية لمسألة القيم الذاتية المتناظرة للشبكة". المجلة السوفيتية للتحليل العددي والنمذجة الرياضية . 2 (5): 371-396 . doi : 10.1515/rnam.1987.2.5.371 . S2CID 121473545 . 
  5. ↑ كنيازيف، أ. ف. (1991). "طريقة التدرج المترافق المُهيأة لمسائل القيم الذاتية وتطبيقها في فضاء جزئي". في: ألبريشت، ج.؛ كولاتز، ل.؛ هاغيدورن، ب.؛ فيلت، و. (محررون). المعالجة العددية لمسائل القيم الذاتية، المجلد 5. السلسلة الدولية للرياضيات العددية. المجلد 96. الصفحات 143-154 . doi : 10.1007/978-3-0348-6332-2_11 . ISBN   978-3-0348-6334-6.
  6. ↑ كنيازيف، أندرو ف. (1998). "حلول القيم الذاتية المُهيأة مسبقًا - تناقض ظاهري؟". المعاملات الإلكترونية في التحليل العددي . 7 : 104-123 .
  7. ↑ كنيازيف، أندرو (2017). "التطبيقات والتوسعات الحديثة لطريقة التدرج المترافق المُهيأ مسبقًا للكتل الأمثل محليًا (LOBPCG)". arXiv : 1708.08354 [ cs.NA ].
  8. 1 2 3 4 5 6 7 8 كنيازيف، أندرو ف. (2001). "نحو الحل الأمثل للمعادلات الذاتية المُهيأة مسبقًا: طريقة التدرج المترافق المُهيأة مسبقًا محليًا". مجلة SIAM للحوسبة العلمية . 23 (2): 517-541 . Bibcode : 2001SJSC...23..517K . doi : 10.1137/S1064827500366124 . S2CID 7077751 . 
  9. 1 2 3 4 دالة تبادل الملفات في MATLAB LOBPCG
  10. 1 2 3 دالة الجبر الخطي المتفرق في SciPy lobpcg
  11. ↑ كنيازيف، أ. (2004). القفل الصلب والقفل المرن في الطرق التكرارية لمسائل القيم الذاتية المتناظرة . المؤتمر الثامن لجبل النحاس حول الطرق التكرارية، 28 مارس - 2 أبريل 2004. doi : 10.13140/RG.2.2.11794.48327 .
  12. ↑ فيتشارينسكي، إي.؛ يانغ، سي.؛ باسك، جيه إي (2015). "خوارزمية التدرج المترافق المُهيأ مسبقًا لحساب العديد من أزواج القيم الذاتية القصوى لمصفوفة هيرميتية" . مجلة الفيزياء الحاسوبية . 290 : 73-89 . arXiv : 1407.7506 . Bibcode : 2015JCoPh.290...73V . doi : 10.1016/j.jcp.2015.02.030 . S2CID 43741860 . 
  13. ↑ LOBPCG لـ SVDS في SciPy
  14. ↑ GitHub BLOPEX
  15. ↑ كنيازيف، أ. ف.؛ أرجنتاتي، م. إ.؛ لاشوك، إ.؛ أوفتشينيكوف، إ. إ. (2007). "حلول القيم الذاتية المُهيأة محليًا الأمثلية للكتل (BLOPEX) في Hypre وPETSc". مجلة SIAM للحوسبة العلمية . 29 (5): 2224. arXiv : 0705.2626 . Bibcode : 2007SJSC...29.2224K . doi : 10.1137/060661624 . S2CID 266 . 
  16. ↑ واجهة PHAML BLOPEX إلى LOBPCG
  17. ↑ دالة الجبر الخطي في أوكتاف lobpcg
  18. ↑ جافا LOBPCG في جوجل كود
  19. ↑ مجموعة أدوات Anasazi Trilinos LOBPCG على GitHub
  20. ↑ Native SLEPc LOBPCG
  21. ↑ واجهة SLEPc BLOPEX إلى LOBPCG
  22. ↑ جوليا LOBPCG على GitHub
  23. ↑ أنزت، هارتويغ؛ توموف، ستانيمير؛ دونغارا، جاك (2015). "تسريع طريقة LOBPCG على وحدات معالجة الرسومات باستخدام ضرب متجه المصفوفة المتفرقة المحظورة" . وقائع ندوة الحوسبة عالية الأداء (HPC '15). الجمعية الدولية لمحاكاة الحاسوب، سان دييغو، كاليفورنيا، الولايات المتحدة الأمريكية . HPC '15: 75-82 . ISBN 9781510801011.
  24. ↑ Pytorch LOBPCG على GitHub
  25. ↑ Rust LOBPCG على GitHub
  26. ↑ رابي، فازلاي؛ دالي، كريستوفر س.؛ أكتولغا، حسن م.؛ رايت، نيكولاس ج. (2019). تقييم نماذج برمجة وحدة معالجة الرسومات القائمة على التوجيهات على محلل القيم الذاتية الكتلية مع مراعاة المصفوفات المتفرقة الكبيرة (ملف PDF) . ورشة العمل السابعة حول برمجة المسرعات باستخدام التوجيهات، SC19: المؤتمر الدولي للحوسبة عالية الأداء والشبكات والتخزين والتحليل .
  27. ↑ CuPy: مكتبة مصفوفات متوافقة مع NumPy مُسرّعة بواسطة CUDA LOBPCG على GitHub
  28. ↑ دمج Google JAX LOBPCG الأولي على GitHub
  29. ↑ NVIDIA AMGX LOBPCG على GitHub
  30. ↑ راخوبا، مكسيم؛ نوفيكوف، ألكسندر؛ أوسيديليتس، إيفان (2019). "حل القيم الذاتية الريمانية منخفضة الرتبة لهاملتونيان عالي الأبعاد" . مجلة الفيزياء الحاسوبية . 396 : 718-737 . arXiv : 1811.11049 . Bibcode : 2019JCoPh.396..718R . doi : 10.1016/j.jcp.2019.07.003 . S2CID 119679555 . 
  31. ↑ ماكوين، جيمس؛ وآخرون (2016). "ميغامان: تعلم متعدد الأبعاد قابل للتوسع في بايثون" . مجلة أبحاث تعلم الآلة . 17 (148): 1-5 . Bibcode : 2016JMLR...17..148M . 
  32. ↑ "Sklearn.cluster.SpectralClustering — توثيق scikit-learn 0.22.1" .
  33. ↑ "Sklearn.manifold.spectral_embedding — توثيق scikit-learn 0.22.1" .
  34. ↑ ناوموف، ماكسيم (2016). "تقسيم الرسم البياني الطيفي السريع على وحدات معالجة الرسومات" . مدونة مطوري NVIDIA .
  35. ↑ "تقسيم الرسم البياني باستخدام Sphynx" .
  36. ↑ وثائق ABINIT: خوارزمية تحسين دالة الموجة
  37. ↑ "دليل مطوري Octopus: LOBPCG" . مؤرشف من الأصل بتاريخ 29-07-2018 . تم الاطلاع عليه بتاريخ 29-07-2018 .
  38. ↑ يامادا، س.؛ إمامورا، ت.؛ ماتشيدا، م. (2005). 16.447 تيرافلوب و159 مليار بُعد من التدوير القطري الدقيق لنموذج هوبارد للفيرميون المحصور على محاكي الأرض . وقائع مؤتمر ACM/IEEE للحوسبة الفائقة (SC'05) . ص 44. doi : 10.1109/SC.2005.1 . ISBN  1-59593-061-2.
  39. ↑ يامادا، س.؛ إمامورا، ت.؛ كانو، ت.؛ ماتشيدا، م. (2006). المرشحون النهائيون لجائزة غوردون بيل 1 - الحوسبة عالية الأداء للأساليب العددية الدقيقة لمسائل الكم متعددة الأجسام على محاكي الأرض . وقائع مؤتمر ACM/IEEE للحوسبة الفائقة (SC '06). ص 47. doi : 10.1145/1188455.1188504 . ISBN  0769527000.
  40. ↑ يامادا، س.؛ إمامورا، ت.؛ ماتشيدا، م. (2018). طريقة LOBPCG عالية الأداء لحل القيم الذاتية المتعددة لنموذج هوبارد: كفاءة الاتصال مع تجنب مُهيئ توسيع نيومان . المؤتمر الآسيوي حول آفاق الحوسبة الفائقة. يوكوتا، ر.، وو، و. (محرران) آفاق الحوسبة الفائقة. SCFA 2018. سلسلة محاضرات في علوم الحاسوب، المجلد 10776. سبرينغر، تشام . الصفحات 243-256 . doi : 10.1007/978-3-319-69953-0_14 . 
  41. ↑ يامادا، س.؛ إمامورا، ت.؛ ماتشيدا، م. (2022). طريقة LOBPCG المتوازية عالية الأداء لهاملتونيان كبير مشتق من نموذج هوبارد على أنظمة متعددة وحدات معالجة الرسومات . الحوسبة الفائقة في آسيا (SCA).
  42. ↑ يانغ، سي.؛ ميزا، جيه سي؛ لي، بي.؛ وانغ، إل-دبليو. (2009). "KSSOLV - مجموعة أدوات MATLAB لحل معادلات كون-شام". معاملات ACM للبرمجيات الرياضية. 36 ( 2): 1-35 . doi : 10.1145/1499096.1499099 . S2CID 624897 . 
  43. ↑ فتح الرحمن، فجار؛ أغوستا، محمد كمال؛ سابوترو، أديتيا غانداريوس؛ ديبوجونو، هيرماوان كريسنو (2020). “PWDFT.jl: حزمة جوليا لحساب البنية الإلكترونية باستخدام نظرية الكثافة الوظيفية وأساس الموجة المستوية”. فيزياء الكمبيوتر والاتصالات . 256 107372. بيب كود : 2020CoPhC.25607372F . دوى : 10.1016/j.cpc.2020.107372 . S2CID 219517717 . 
  44. ↑ مجموعة أدوات نظرية الكثافة الوظيفية (DFTK). نظرية الكثافة الوظيفية للموجات المستوية في لغة جوليا
  45. ↑ راخوبا، مكسيم؛ أوسيليديتس، إيفان (2016). "حساب الأطياف الاهتزازية للجزيئات باستخدام تحليل سلسلة الموترات". مجلة الفيزياء الكيميائية . 145 (12): 124101. arXiv : 1605.08422 . Bibcode : 2016JChPh.145l4101R . doi : 10.1063/1.4962420 . PMID: 27782616. S2CID : 44797395 .  
  46. ↑ تاكانو، يو؛ ناكاتا، كازوتو؛ يونيزاوا، ياسوشيغي؛ ناكامورا، هاروكي (2016). "تطوير برنامج محاكاة ديناميكيات جزيئية متعدد المستويات واسع النطاق، بلاتيبوس (منصة لمحاكاة ديناميكيات البروتين الموحدة)، لتوضيح وظائف البروتين" . مجلة الكيمياء الحاسوبية . 37 (12): 1125-1132 . doi : 10.1002 / jcc.24318 . PMC 4825406. PMID 26940542 .  
  47. ↑ شاو، مييو؛ وآخرون (2018). "تسريع حسابات تفاعل التكوين النووي من خلال خوارزمية حل القيم الذاتية التكرارية المُهيأة مسبقًا". مجلة اتصالات الفيزياء الحاسوبية . 222 (1): 1-13 . arXiv : 1609.01689 . Bibcode : 2018CoPhC.222....1S . doi : 10.1016/j.cpc.2017.09.004 . S2CID 13996642 .  
  48. ↑ كانغ، سونغوو؛ وآخرون (2020). "ACE-Molecule: حزمة برمجية مفتوحة المصدر للكيمياء الكمومية في الفضاء الحقيقي" . مجلة الفيزياء الكيميائية . 152 (12) 124110. Bibcode : 2020JChPh.152l4110K . doi : 10.1063/5.0002959 . PMID 32241122. S2CID 214768088 .   
  49. ↑ باتشيفسكي، أندرو ديفيد؛ بريكسون، ميتشل إيان؛ كامبل، كوين؛ جاكوبسون، نوح توبياس؛ ماورر، ليون (2020-09-01). معالج تناظري كمي لمحاكاة أنظمة الإلكترونات المترابطة (تقرير). الولايات المتحدة: مختبر سانديا الوطني (SNL-NM). doi : 10.2172/1671166 . OSTI 1671166 . 
  50. ↑ دراسة استقصائية لطرق حل القيم الذاتية في برنامج LS-DYNA . المؤتمر الدولي الخامس عشر لبرنامج LS-DYNA، ديترويت. 2018.
  51. ↑ "التطورات الأخيرة في LS-DYNA 2024R1 (R15.0)" (ملف PDF) . 2024. ص 15. 
  52. ↑ كنيازيف، أ.؛ مالشيف، أ. (2015). مرشحات متعددة الحدود الطيفية المعجلة القائمة على الرسوم البيانية . ورشة عمل IEEE الدولية الخامسة والعشرون حول التعلم الآلي لمعالجة الإشارات (MLSP)، بوسطن، ماساتشوستس. ص 1-6 . arXiv : 1509.02468 . doi : 10.1109/MLSP.2015.7324315 . 
  53. ↑ كنيازيف، أندرو ف. (2003). بولي؛ ديلون؛ غوش؛ كوجان (محررون). خوارزميات الحلول الذاتية المُهيأة الحديثة لتجزئة الصور الطيفية وتقسيم الرسوم البيانية . تجميع مجموعات البيانات الكبيرة؛ المؤتمر الدولي الثالث لمعهد مهندسي الكهرباء والإلكترونيات حول استخراج البيانات (ICDM 2003)، ملبورن، فلوريدا: جمعية الحاسبات التابعة لمعهد مهندسي الكهرباء والإلكترونيات. الصفحات 59-62 . 
  54. ↑ كنيازيف، أندرو ف. (2006). تجزئة الصور الطيفية متعددة المقاييس: التكييف المسبق متعدد المقاييس لحساب القيم الذاتية لمصفوفات لابلاس في تجزئة الصور . ورشة عمل التعلم السريع للمتشعبات، WM Williamsburg، VA. doi : 10.13140/RG.2.2.35280.02565 .
  55. ↑ كنيازيف، أندرو ف. (2006). تقسيم الرسم البياني الطيفي متعدد المقاييس وتجزئة الصور . ورشة عمل حول الخوارزميات لمجموعات البيانات الضخمة الحديثة، جامعة ستانفورد وياهو! للأبحاث.
  56. ↑ "التجميع الطيفي - وثائق scikit-learn" .