ในทางคณิตศาสตร์อัลกอริทึมของแบร์เรส (Bareiss algorithm)ซึ่งตั้งชื่อตามเออร์วิน แบร์เรสเป็นอัลกอริทึมที่ใช้คำนวณดีเทอร์มิแนนต์หรือรูปแบบขั้นบันไดของเมทริกซ์ที่มี สมาชิกเป็น จำนวนเต็มโดยใช้เพียงการคำนวณเลขจำนวนเต็มเท่านั้นการหาร ใดๆ ที่ดำเนินการจะรับประกันได้ว่าแม่นยำ (ไม่มีเศษเหลือ ) วิธีนี้ยังสามารถใช้ในการคำนวณดีเทอร์มิแนนต์ของเมทริกซ์ที่มีสมาชิกเป็น จำนวนจริง (โดยประมาณ) ได้อีกด้วยโดยหลีกเลี่ยงการเกิดข้อผิดพลาดจากการปัดเศษนอกเหนือจากที่เกิดขึ้นแล้วในข้อมูลป้อนเข้า

นิยามของดีเทอร์มิแนนต์ของเมทริกซ์เกี่ยวข้องกับการดำเนินการคูณ บวก และลบเท่านั้น ดังนั้นดีเทอร์มิแนนต์ของเมทริกซ์จะเป็นจำนวนเต็มก็ต่อเมื่อสมาชิกทุกตัวเป็นจำนวนเต็ม อย่างไรก็ตาม การคำนวณดีเทอร์มิแนนต์จริงโดยใช้นิยามหรือสูตรของไลบ์นิซนั้นทำได้ยากในทางปฏิบัติ เนื่องจากต้องใช้การดำเนินการ O( n! ) การกำจัดแบบเกาส์เซียนมีความซับซ้อน O( n³ ⁾แต่จะมีการหารเข้ามาเกี่ยวข้อง ซึ่งส่งผลให้เกิดข้อผิดพลาดจากการปัดเศษเมื่อนำไปใช้กับตัวเลขทศนิยม

ข้อผิดพลาดจากการปัดเศษสามารถหลีกเลี่ยงได้หากตัวเลขทั้งหมดถูกเก็บเป็นเศษส่วนจำนวนเต็มแทนที่จะเป็นเลขทศนิยม แต่ขนาดของแต่ละองค์ประกอบจะเพิ่มขึ้นแบบทวีคูณตามจำนวนแถว^{[ 1 ]}

Bareiss หยิบยกประเด็นเรื่องการกำจัดแบบรักษาจำนวนเต็มไว้ในขณะที่รักษาขนาดของสัมประสิทธิ์ตัวกลางให้มีขนาดเล็กพอสมควร มีการเสนออัลกอริทึมสองแบบ: ^{[ 2 ] [ 3 ]}

1. อัลกอริทึมที่ไม่ต้องหาร — ทำการลดรูปเมทริกซ์ให้อยู่ในรูปสามเหลี่ยมโดยไม่ต้องดำเนินการหารใดๆ
2. อัลกอริทึมที่ไม่เหลือเศษ — ใช้การหารเพื่อให้ค่ากลางมีขนาดเล็ก แต่เนื่องจากเอกลักษณ์ของซิลเวสเตอร์การแปลงจึงยังคงรักษาจำนวนเต็มไว้ (การหารมีเศษเหลือเป็นศูนย์)

เพื่อความสมบูรณ์ Bareiss ยังแนะนำวิธีการกำจัดที่ไม่ต้องคูณซึ่งสร้างเศษส่วนอีกด้วย^{[ 2 ]}

โครงสร้างโปรแกรมของอัลกอริทึมนี้เป็นลูปสามชั้นแบบง่ายๆ เช่นเดียวกับการกำจัดแบบเกาส์เซียนมาตรฐาน อย่างไรก็ตาม ในกรณีนี้ เมทริกซ์จะถูกแก้ไขเพื่อให้แต่ละรายการM _k,kประกอบด้วยไมเนอร์ หลักชั้นนำ [ M ] _k,kความถูกต้องของอัลกอริทึมสามารถแสดงได้ง่ายโดยการเหนี่ยวนำบนk ^{[ 4 ]}

หากสมมติฐานเกี่ยวกับไมเนอร์หลักกลายเป็นเท็จ เช่น ถ้าM _{k −1, k −1} = 0 และM _{i , k −1} ≠ 0 บางค่า ( i = k ,..., n ) เราสามารถสลับ แถวที่ k −1 กับแถวที่iและเปลี่ยนเครื่องหมายของคำตอบสุดท้ายได้

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

ดังนั้น สำหรับ เมทริกซ์ n × nที่มีค่าสูงสุด (สัมบูรณ์) 2 ^Lสำหรับแต่ละรายการ อัลกอริทึมของ Bareiss จะทำงานด้วย การดำเนินการพื้นฐาน O( n ³ )ครั้ง โดยมีขอบเขต O( n ^{n /2}  2 ^nL ) สำหรับค่าสัมบูรณ์ของค่ากลางที่จำเป็นความซับซ้อนในการคำนวณจึงเป็น O( n ⁵ L ²  (log( n ) ²  +  L ² )) เมื่อใช้เลขคณิตพื้นฐาน หรือ O( n ⁴ L  (log( n ) +  L ) log(log( n ) +  L ))) เมื่อใช้การ คูณแบบเร็ว

อัลกอริทึมของ Bareiss ไม่ค่อยได้ใช้กับเมทริกซ์จำนวนเต็ม เนื่องจากเลขคณิตแบบมัลติโมดูลาร์ช่วยให้ได้ความซับซ้อนที่คล้ายกับอัลกอริทึมของ Bareiss พร้อมกับการคูณที่รวดเร็ว และยังง่ายต่อการใช้งานมากกว่ามาก

ในทางกลับกัน อัลกอริทึมของ Bareiss สามารถใช้ได้กับค่าต่างๆ ในโดเมนจำนวนเต็ม ใดๆ ที่มีอัลกอริทึมการหารที่แม่นยำ และโดยเฉพาะอย่างยิ่งสำหรับเมทริกซ์ของพหุนาม