خوارزمية بوخبيرغر

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

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

للاطلاع على خوارزميات أساس غروبنر الأخرى، انظر أساس غروبنر §  الخوارزميات والتطبيقات .

تتم النسخة الأولية من هذه الخوارزمية لإيجاد أساس للمثالي I لحلقة متعددة الحدود R على النحو التالي:

أدخل مجموعة من كثيرات الحدود F التي تولد I

إخراج أساس غروبنر G لـ I

1. G  := F
2. لكل f _i ، f _j في G ، نرمز بـ g _i إلى الحد الرئيسي لـ f _i بالنسبة لترتيب أحادي الحد المعطى ، وبـ a _ij إلى المضاعف المشترك الأصغر لـ g _i و g _j .
3. اختر كثيرتي حدود في G ولتكن S _ij = ⁠ a _ij / g _i ⁠ f _i − ⁠ a _ij / g _j ⁠ f _j (ستلغى الحدود الرئيسية هنا عن طريق البناء) .
4. قلّل قيمة S _{_ij} باستخدام خوارزمية القسمة متعددة المتغيرات بالنسبة للمجموعة G حتى يصبح الناتج غير قابل للاختزال أكثر. إذا كان الناتج غير صفري، فأضفه إلى G.
5. كرر الخطوات من 2 إلى 4 حتى يتم النظر في جميع الأزواج الممكنة، بما في ذلك تلك التي تتضمن كثيرات الحدود الجديدة المضافة في الخطوة 4.
6. الناتج G

تُعرف كثيرة الحدود S_{_ij} عادةً باسم كثيرة الحدود S ، حيث تشير S إلى الطرح (بوخبيرغر) أو الاقتران (آخرون). ويُشار عادةً إلى زوج كثيرات الحدود المرتبط بها باسم الزوج الحرج .

توجد طرق عديدة لتحسين هذه الخوارزمية بما يتجاوز ما ذُكر أعلاه. على سبيل المثال، يمكن اختزال جميع العناصر الجديدة في F بالنسبة لبعضها البعض _قبل جمعها. إذا لم تشترك الحدود الرئيسية لـ fᵢ _و fⱼ في أي متغيرات، فإن Sᵢⱼ _{ستُختزل} دائمًا إلى 0 (إذا استُخدمت fᵢ _و fⱼ فقط للاختزال)، وبالتالي لا داعي لحسابها _على الإطلاق .

تنتهي الخوارزمية لأنها تزيد باستمرار من حجم المثالي الأحادي الناتج عن الحدود الرئيسية لمجموعتنا F ، وتضمن ليمّة ديكسون (أو نظرية أساس هيلبرت ) أن أي سلسلة تصاعدية من هذا القبيل يجب أن تصبح ثابتة في النهاية.

يصعب تقدير التعقيد الحسابي لخوارزمية بوخبيرغر نظرًا لكثرة الخيارات التي قد تُغير وقت الحساب بشكل كبير. ومع ذلك، فقد أثبت تي دبليو دوبيه ^{[ 1 ]} أن درجات عناصر أساس غروبنر المُختزل تكون دائمًا محدودة بـ

${\displaystyle 2\left({\frac {d^{2}}{2}}+d\right)^{2^{n-1}}}$،

حيث n هو عدد المتغيرات، و d هي الدرجة الكلية القصوى لكثيرات الحدود المدخلة. وهذا يسمح، نظريًا، باستخدام الجبر الخطي على فضاء المتجهات لكثيرات الحدود ذات الدرجة المحدودة بهذه القيمة، للحصول على خوارزمية ذات تعقيد ${\displaystyle d^{2^{n+o(1)}}}$.

من ناحية أخرى، هناك أمثلة ^{[ 2 ]} حيث تحتوي قاعدة غروبنر على عناصر من الدرجة

${\displaystyle d^{2^{\Omega (n)}}}$،

والحد الأعلى المذكور أعلاه للتعقيد هو الأمثل. ومع ذلك، فإن مثل هذه الأمثلة نادرة للغاية.

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

تم إثبات صحة تطبيق واحد على الأقل لخوارزمية بوخبيرغر ضمن برنامج المساعدة في البرهان Rocq (المعروف سابقًا باسم Coq). ^{[ 3 ]}

في مكتبة SymPy للغة بايثون ، يتم تنفيذ خوارزمية Buchberger (المحسّنة) على النحو التالي sympy.polys.polytools.groebner(). ^{[ 4 ]}

• خوارزمية إكمال كنوت-بنديكس
• خوارزمية كوين-مكلوسكي – خوارزمية مماثلة للجبر البولياني

• بوخبيرغر، ب. ( أغسطس 1976). "الأساس النظري لاختزال كثيرات الحدود إلى أشكال قانونية". نشرة ACM SIGSAM . 10 (3). ACM: 19-29 . doi : 10.1145/1088216.1088219 . MR 0463136. S2CID 15179417 .  
• ديفيد كوكس، جون ليتل، ودونالد أوشيا (1997). المُثُل، والأنواع، والخوارزميات: مقدمة في الهندسة الجبرية الحاسوبية والجبر التبادلي ، سبرينغر. ISBN 0-387-94680-2.
• فلاديمير ب. جيردت، يوري أ. بلينكوف (1998). الأسس الضمنية للمثاليّات متعددة الحدود ، الرياضيات والحواسيب في المحاكاة، 45: 519 وما بعدها

• "خوارزمية بوخبيرجر" ، موسوعة الرياضيات ، دار نشر EMS ، 2001 [1994]
• خوارزمية بوخبيرغر على موقع سكولاربيديا
• وايسشتاين، اريك دبليو “خوارزمية بوخبرجر” . عالم الرياضيات .