ในทฤษฎีพหุนามหลายตัวแปร อัลกอริทึมของบุชเบอร์เกอร์เป็นวิธีการแปลงชุดพหุนามที่กำหนดให้เป็นฐานกรุบเนอร์ซึ่งเป็นชุดพหุนามอีกชุดหนึ่งที่มีรากร่วมกันและสะดวกกว่าในการดึงข้อมูลเกี่ยวกับรากร่วมเหล่านั้น อัลกอริทึมนี้ได้รับการแนะนำโดยบรูโน บุชเบอร์เกอร์พร้อมกับการนิยามฐานกรุบเนอร์

อัลกอริทึมแบบยุคลิด สำหรับการคำนวณ ตัวหารร่วมมากของพหุนามเป็นกรณีพิเศษของอัลกอริทึมของบุชเบอร์เกอร์ที่จำกัดเฉพาะพหุนามตัวแปรเดียวการกำจัดแบบ เกาส์เซียน ของระบบสมการเชิงเส้นเป็นอีกกรณีพิเศษหนึ่งที่ระดับดีกรีของพหุนามทั้งหมดเท่ากับหนึ่ง

สำหรับอัลกอริธึมฐาน Gröbner อื่นๆ โปรดดูที่ ฐาน Gröbner § อัลกอริธึมและการนำไปใช้

วิธีการแบบง่ายๆ ของอัลกอริธึมนี้ในการหาฐานสำหรับไอเดียลIของวงแหวนพหุนามRดำเนินการดังนี้:

อินพุตชุดของพหุนามFที่สร้างI

เอาต์พุตฐานGröbner GสำหรับI

1. จี  := เอฟ
2. สำหรับทุกf _i , f _jในGให้g _i แทน พจน์นำของf _iตาม ลำดับ เอกนาม ที่กำหนด และให้a _ijแทนตัวคูณร่วมน้อยที่สุดของg _iและg _j
3. เลือกพหุนามสองตัวในGและให้S _ij = ⁠เอไอ_เจ/จี_ไอ⁠ f _i − ⁠เอไอ_เจ/จี_เจ⁠ f _j (คำนำหน้าในที่นี้จะหักล้างกันเองโดยโครงสร้าง) .
4. ลดS _ijโดยใช้อัลกอริทึมการหารหลายตัวแปรเทียบกับเซตGจนกว่าผลลัพธ์จะไม่สามารถลดทอนได้อีกต่อไป หากผลลัพธ์ไม่เป็นศูนย์ ให้เพิ่มผลลัพธ์นั้นลงในG
5. ทำซ้ำขั้นตอนที่ 2–4 จนกว่าจะพิจารณาคู่ที่เป็นไปได้ทั้งหมด รวมถึงคู่ที่เกี่ยวข้องกับพหุนามใหม่ที่เพิ่มเข้ามาในขั้นตอนที่ 4 ด้วย
6. เอาต์พุตG

พหุนามS _ijมักถูกเรียกว่า พหุนาม Sโดยที่Sหมายถึงการลบ (Buchberger) หรือsyzygy (อื่นๆ) คู่ของพหุนามที่เกี่ยวข้องกับพหุนาม S นี้มักถูกเรียกว่าคู่วิกฤต

มีหลายวิธีที่จะปรับปรุงอัลกอริธึมนี้ให้ดียิ่งขึ้นไปกว่าที่ได้กล่าวไว้ข้างต้น ตัวอย่างเช่น สามารถลดรูปองค์ประกอบใหม่ทั้งหมดของFให้สัมพันธ์กันก่อนที่จะนำมาบวกกัน หากพจน์นำของf _iและf _jไม่มีตัวแปรที่เหมือนกันS _ijจะลดลงเหลือ 0 เสมอ (หากใช้เพียง f _iและf _jในการลดรูป) ดังนั้นจึงไม่จำเป็นต้องคำนวณเลย

อัลกอริทึมจะสิ้นสุดลงเนื่องจากขนาดของอุดมคติเอกนามที่สร้างขึ้นจากพจน์นำหน้าของเซตF ของเราเพิ่มขึ้นอย่างต่อเนื่อง และทฤษฎีบทของดิกสัน (หรือทฤษฎีบทฐานของฮิลเบิร์ต ) รับประกันว่าลำดับการเพิ่มขึ้นดังกล่าวจะต้องคงที่ในที่สุด

ความซับซ้อนในการคำนวณของอัลกอริทึมของ Buchberger นั้นประเมินได้ยากมาก เนื่องจากมีตัวเลือกมากมายที่อาจเปลี่ยนแปลงเวลาในการคำนวณอย่างมาก อย่างไรก็ตาม TW Dubé ได้พิสูจน์แล้ว^{[ 1 ]}ว่าระดับขององค์ประกอบของฐาน Gröbner ที่ลดลงนั้นจะถูกจำกัดโดยเสมอ

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

โดยที่nคือจำนวนตัวแปร และd คือ ดีกรีรวมสูงสุดของพหุนามอินพุต ในทางทฤษฎีแล้ว วิธีนี้ช่วยให้สามารถใช้พีชคณิตเชิงเส้นบนปริภูมิเวกเตอร์ ของพหุนามที่มีดีกรีจำกัดด้วยค่านี้ เพื่อสร้างอัลกอริทึม ที่ มีความซับซ้อน ${\displaystyle d^{2^{n+o(1)}}}$

ในทางกลับกัน มีตัวอย่าง^{[ 2 ]}ที่ฐาน Gröbner ประกอบด้วยองค์ประกอบที่มีระดับ

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

และขีดจำกัดสูงสุดของความซับซ้อนที่กล่าวมาข้างต้นนั้นถือว่าเหมาะสมที่สุดแล้ว อย่างไรก็ตาม ตัวอย่างเช่นนี้พบได้น้อยมาก

นับตั้งแต่การค้นพบอัลกอริทึมของ Buchberger ได้มีการนำอัลกอริทึมแบบต่างๆ มาปรับปรุงประสิทธิภาพมากมาย ปัจจุบัน อัลกอริทึม F4 และ F5 ของ Faugèreเป็นอัลกอริทึมที่มีประสิทธิภาพสูงสุดสำหรับการคำนวณฐาน Gröbner และช่วยให้สามารถคำนวณฐาน Gröbner ที่ประกอบด้วยพหุนามหลายร้อยตัว ซึ่งแต่ละตัวมีพจน์หลายร้อยพจน์และสัมประสิทธิ์หลายร้อยหลักได้อย่างเป็นประจำ

อย่างน้อยหนึ่งการใช้งานของอัลกอริทึมของ Buchberger ได้รับการพิสูจน์ว่าถูกต้องภายในตัวช่วยพิสูจน์Rocq (เดิมชื่อ Coq) ^{[ 3 ]}

ใน ไลบรารี SymPyสำหรับPythonอัลกอริทึม Buchberger (ที่ได้รับการปรับปรุง) จะถูกนำไปใช้sympy.polys.polytools.groebner()เป็น^{[ 4 ]}

• อัลกอริทึมการเติมเต็ม Knuth–Bendix
• อัลกอริทึมควิน-แมคคลัสกี้ – อัลกอริทึมที่คล้ายคลึงกันสำหรับพีชคณิตบูลีน

• Buchberger, B. (สิงหาคม 1976). "พื้นฐานทางทฤษฎีสำหรับการลดรูปพหุนามเป็นรูปแบบมาตรฐาน". ACM SIGSAM Bulletin . 10 (3). ACM: 19– 29. doi : 10.1145/1088216.1088219 . MR  0463136 . S2CID  15179417 .
• David Cox, John Little และ Donald O'Shea (1997). Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra , Springer. ISBN 0-387-94680-2.
• Vladimir P. Gerdt, Yuri A. Blinkov (1998). ฐานผกผันของอุดมคติพหุนาม , คณิตศาสตร์และคอมพิวเตอร์ในการจำลอง, 45:519ff

• "อัลกอริทึมของบุชเบอร์เกอร์" , สารานุกรมคณิตศาสตร์ , EMS Press , 2001 [1994]
• อัลกอริทึมของ Buchbergerบน Scholarpedia
• ไวส์สไตน์, เอริก ดับเบิลยู. "อัลกอริทึมของบุชเบอร์เกอร์" . แมทเวิลด์ .