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

في الرياضيات، تُعرف خوارزمية باريس ، نسبةً إلى إروين باريس ، بأنها خوارزمية لحساب محدد أو شكل المصفوفة المتدرجة لمصفوفة ذات عناصر صحيحة باستخدام العمليات الحسابية الصحيحة فقط؛ وتضمن هذه الخوارزمية دقة جميع عمليات القسمة (بدون باقٍ ). كما يمكن استخدام هذه الطريقة لحساب محدد المصفوفات ذات العناصر الحقيقية (المُقرّبة) ، مما يتجنب إدخال أي أخطاء تقريبية تتجاوز تلك الموجودة أصلاً في المدخلات.

يقتصر تعريف محدد المصفوفة على عمليات الضرب والجمع والطرح. لذا، يكون محدد المصفوفة عددًا صحيحًا عندما تكون جميع عناصرها أعدادًا صحيحة. مع ذلك، فإن حساب المحدد باستخدام التعريف أو صيغة لايبنيز غير عملي، إذ يتطلب O( n! ) عملية حسابية. أما طريقة الحذف الغاوسي، ^فتتميز بتعقيد زمني O( n³ )، لكنها تُدخل القسمة، مما يؤدي إلى أخطاء تقريب عند تطبيقها باستخدام الأعداد العشرية.

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

يطرح باريس مسألة إجراء عملية حذف تحافظ على الأعداد الصحيحة مع الحفاظ على قيم المعاملات الوسيطة صغيرة بشكل معقول. ويُقترح خوارزميتان: ^{[ 2 ] [ 3 ]}

1. خوارزمية خالية من القسمة - تقوم باختزال المصفوفة إلى شكل مثلثي دون أي عملية قسمة.
2. خوارزمية خالية من الكسور - تستخدم القسمة للحفاظ على المدخلات الوسيطة أصغر، ولكن بسبب هوية سيلفستر، فإن التحويل لا يزال يحافظ على الأعداد الصحيحة (القسمة لها باقي صفر).

ولإتمام الصورة، يقترح باريس أيضاً طرقاً للحذف لا تتطلب الضرب وتنتج كسوراً. ^{[ 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 وتغيير إشارة الإجابة النهائية.

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

يستنتج من ذلك أنه بالنسبة لمصفوفة من الرتبة n × n ذات قيمة قصوى (مطلقة) تساوي ^2L لكل عنصر، فإن خوارزمية Bareiss تعمل في ^O ( n³ ) من العمليات الحسابية الأولية ^، مع حد أقصى قدره O( n² ^{/ 2}  ) nL² للقيمة المطلقة للقيم الوسيطة المطلوبة. وبالتالي ^{، فإن} تعقيدها الحسابي هو O( n⁵L² (log( n ) ^² + L² ^{) ) عند استخدام العمليات الحسابية الأولية ،} أو O( n⁴L (log( n ) + L ) log(log( n ) + L ) ⁾ ) باستخدام الضرب السريع .         

لا تُستخدم خوارزمية Bareiss بشكل شائع للمصفوفات الصحيحة، لأن الحساب متعدد الأنماط يسمح بتعقيد مشابه لخوارزمية Bareiss مع الضرب السريع، وهو أبسط بكثير في التنفيذ.

من ناحية أخرى، يمكن استخدام خوارزمية Bareiss مع المدخلات في أي مجال تكاملي مزود بخوارزمية قسمة دقيقة، وعلى وجه الخصوص، لمصفوفات كثيرات الحدود.