बेरिस एल्गोरिथ्म

गणित में, बेरिस एल्गोरिथ्म (बेरिस कलन विधि), जिसका नाम इरविन बेरेज़ के नाम पर रखा गया है, केवल पूर्णांक अंकगणित का उपयोग करके पूर्णांक प्रविष्टियों के साथ आव्यूह (गणित) के निर्धारक या सोपानक रूप की गणना करने के लिए एक एल्गोरिदम है; किया गया कोई भी विभाजन (गणित) सटीक होने की गारंटी है (कोई शेष नहीं है)। विधि का उपयोग (अनुमानित) वास्तविक संख्या प्रविष्टियों के साथ आव्यूह के निर्धारक की गणना करने के लिए भी किया जा सकता है, जिससे इनपुट में पहले से उपस्थित त्रुटियों से परे किसी भी राउंड-ऑफ त्रुटियों की प्रांरम्भ से बचा जा सके।

इतिहास

सामान्य बेरिस एल्गोरिदम टोएप्लिट्ज़ आव्यूह के लिए बेरिस एल्गोरिदम से अलग है।

कुछ स्पैनिश भाषी देशों में, इस एल्गोरिदम को बेरिस-मोंटांटे के नाम से भी जाना जाता है, क्योंकि मेक्सिको के यूनिवर्सिडैड ऑटोनोमा डी नुएवो लियोन के प्रोफेसर रेने मारियो मोंटेंटे पार्डो ने इस पद्धति को अपने छात्रों के बीच लोकप्रिय बनाया।

अवलोकन

निर्धारक परिभाषा में केवल गुणा, जोड़ और घटाव संक्रियाएँ होती हैं। यदि सभी आव्यूह प्रविष्टियाँ पूर्णांक हैं तो स्पष्ट रूप से निर्धारक पूर्णांक है। हालाँकि परिभाषा या लीबनिज़_फॉर्मूला_फॉर_डिटर्मिनेंट्स का उपयोग करके निर्धारक की वास्तविक गणना अव्यावहारिक है, क्योंकि इसके लिए O(n!) संचालन की आवश्यकता होती है।

गाऊसी_उन्मूलन कंप्यूटिंग_निर्धारकों में O(n³) है) सम्मिश्रता, लेकिन विभाजन का परिचय देती है, जिसके परिणामस्वरूप फ़्लोटिंग पॉइंट नंबरों का उपयोग करके कार्यान्वित किए जाने पर राउंड-ऑफ़ त्रुटियां होती हैं।

राउंड-ऑफ एरर (राउंड-ऑफ त्रुटियों) से बचा जा सकता है यदि सभी संख्याओं को फ्लोटिंग पॉइंट के बजाय पूर्णांक अंश के रूप में रखा जाए। लेकिन फिर प्रत्येक तत्व का आकार पंक्तियों की संख्या के साथ तेजी से बढ़ता है।

बेरिस मध्यवर्ती गुणांकों के परिमाण को यथोचित रूप से छोटा रखते हुए एक पूर्णांक-संरक्षण विलोपन करने का प्रश्न उठाता है। दो एल्गोरिदम सुझाए गए हैं:

1. डिवीजन-मुक्त एल्गोरिदम - बिना किसी डिवीजन ऑपरेशन के त्रिकोणीय रूप में आव्यूह कटौती करता है।
2. भिन्न-मुक्त एल्गोरिथ्म - मध्यवर्ती प्रविष्टियों को छोटा रखने के लिए विभाजन का उपयोग करता है, लेकिन सिल्वेस्टर की पहचान के कारण परिवर्तन अभी भी पूर्णांक-संरक्षित है (विभाजन में शून्य शेष है)।

पूर्णता के लिए बेरिस भिन्न-उत्पादक गुणन-मुक्त उन्मूलन विधियों का भी सुझाव देते हैं।

एल्गोरिदम

इस एल्गोरिदम की प्रोग्राम संरचना एक सरल ट्रिपल-लूप है, जैसा कि मानक गाऊसी उन्मूलन में होता है। हालाँकि इस स्थिति में आव्यूह को संशोधित किया गया है ताकि प्रत्येक M_k,k प्रविष्टि में प्रमुख प्रमुख माइनर_(रैखिक_बीजगणित) शामिल है [M]_k,k. एल्गोरिथम की शुद्धता आसानी से इंडक्शन द्वारा दिखाई जाती है k.

• इनपुट: M - एक n-वर्ग मैट्रिक्स
  इसके प्रमुख प्रमुख नाबालिगों को मानते हुए [M]_k,k सभी गैर-शून्य हैं.
• मान लीजिये M_0,0 = 1 (नोट: M_0,0 एक विशेष चर है)
• के लिए k 1 से n−1:
  • के लिए i से k+1 से n:
    • के लिए j से k+1 से n:
      • तय करना $M_{i,j}={\frac {M_{i,j}M_{k,k}-M_{i,k}M_{k,j}}{M_{k-1,k-1}}}$
• आउटपुट: आव्यूह को In-place_algorithm|in-place,
  प्रत्येक में संशोधित किया गया है M_k,k प्रविष्टि में प्रमुख लघु सम्मिलित है [M]_k,k,
  प्रविष्टि M_n,n में मूल का निर्धारक सम्मिलित है M.

यदि प्रमुख अवयस्कों के बारे में धारणा गलत साबित होती है, उदाहरण के लिए अगर M_k−1,k−1 = 0 और कुछ M_i,k−1 ≠ 0 (i = k,...,n) तो हम विनिमय कर सकते हैं k−1-वीं पंक्ति के साथ i-वीं पंक्ति और अंतिम उत्तर का चिह्न बदलें।

विश्लेषण

बेरिस एल्गोरिथ्म के निष्पादन के दौरान, गणना किया जाने वाला प्रत्येक पूर्णांक इनपुट आव्यूह के उपाव्यूह का निर्धारक होता है। यह हैडामर्ड असमानता का उपयोग करके, इन पूर्णांकों के आकार को सीमित करने की अनुमति देता है। अन्यथा, बेरिस एल्गोरिदम को गॉसियन उन्मूलन के एक प्रकार के रूप में देखा जा सकता है और इसके लिए लगभग समान संख्या में अंकगणितीय परिचालन की आवश्यकता होती है।

यह इस प्रकार है कि, अधिकतम (पूर्ण) मान 2^L के n × n आव्यूह के लिए प्रत्येक प्रविष्टि के लिए, बेरिस एल्गोरिथ्म बिग ओ नोटेशन O(n³) में चलता है) O(n^n/2 2^nL) के साथ प्रारंभिक संचालन आवश्यक मध्यवर्ती मूल्यों के पूर्ण मूल्य पर बाध्य है। इस प्रकार इसकी कम्प्यूटेशनल सम्मिश्रता O(n⁵ L²) (log(n)²+L²)) हैl प्राथमिक अंकगणित या O(n⁴L) (log(n) + L) log(log(n) + L))का उपयोग करते समय  तेज गुणन का उपयोग करके।