Strassen's Matrix Multiplication Algorithm in Hindi | स्ट्रासेन का मैट्रिक्स गुणा एल्गोरिदम

स्ट्रासेन का मैट्रिक्स गुणा एल्गोरिदम क्या है? (Strassen's Matrix Multiplication Algorithm in Hindi)

स्ट्रासेन का एल्गोरिदम (Strassen's Algorithm) एक प्रभावी मैट्रिक्स गुणा (Matrix Multiplication) तकनीक है, जिसे 1969 में वोल्कर स्ट्रासेन (Volker Strassen) द्वारा विकसित किया गया था। यह डिवाइड एंड कॉन्कर (Divide and Conquer) पद्धति पर आधारित है और पारंपरिक मैट्रिक्स गुणा की तुलना में तेज़ काम करता है।

स्ट्रासेन के एल्गोरिदम की आवश्यकता (Need for Strassen's Algorithm)

सामान्यतः, दो n × n मैट्रिक्स को गुणा करने के लिए पारंपरिक एल्गोरिदम O(n³) समय जटिलता (Time Complexity) में कार्य करता है। लेकिन स्ट्रासेन का एल्गोरिदम इसे O(n^2.81) तक घटा सकता है, जिससे यह बड़े मैट्रिक्स के लिए अधिक प्रभावी होता है।

स्ट्रासेन एल्गोरिदम की प्रक्रिया (Process of Strassen's Algorithm)

स्ट्रासेन का एल्गोरिदम निम्नलिखित चरणों में कार्य करता है:

• चरण 1 (Matrix Division): मैट्रिक्स A और B को 4 छोटे उप-मैट्रिक्स में विभाजित करें।
• चरण 2 (Recursion): मैट्रिक्स के इन भागों पर 7 मैट्रिक्स गुणा गणनाएँ करें।
• चरण 3 (Combination): प्राप्त परिणामों को जोड़कर अंतिम मैट्रिक्स तैयार करें।

स्ट्रासेन एल्गोरिदम का सूत्र (Strassen's Formula)

माना कि हमारे पास दो मैट्रिक्स A और B हैं:

स्ट्रासेन एल्गोरिदम 7 मैट्रिक्स गुणा की गणना करता है:

• P₁ = (A₁₁ + A₂₂) × (B₁₁ + B₂₂)
• P₂ = (A₂₁ + A₂₂) × B₁₁
• P₃ = A₁₁ × (B₁₂ - B₂₂)
• P₄ = A₂₂ × (B₂₁ - B₁₁)
• P₅ = (A₁₁ + A₁₂) × B₂₂
• P₆ = (A₂₁ - A₁₁) × (B₁₁ + B₁₂)
• P₇ = (A₁₂ - A₂₂) × (B₂₁ + B₂₂)

इसके बाद, अंतिम मैट्रिक्स C को संगठित किया जाता है:

• C₁₁ = P₁ + P₄ - P₅ + P₇
• C₁₂ = P₃ + P₅
• C₂₁ = P₂ + P₄
• C₂₂ = P₁ - P₂ + P₃ + P₆

स्ट्रासेन एल्गोरिदम की समय जटिलता (Time Complexity of Strassen's Algorithm)

• Best Case (सबसे अच्छा केस): O(n^2.81)
• Average Case (औसत केस): O(n^2.81)
• Worst Case (सबसे खराब केस): O(n^2.81)

स्ट्रासेन बनाम पारंपरिक मैट्रिक्स गुणा (Strassen vs Traditional Matrix Multiplication)

स्ट्रासेन एल्गोरिदम के लाभ (Advantages of Strassen's Algorithm)

• यह बड़े मैट्रिक्स के लिए अधिक कुशल है।
• पारंपरिक O(n³) एल्गोरिदम की तुलना में तेज़ है।
• डिवाइड एंड कॉन्कर दृष्टिकोण के कारण तेजी से निष्पादित होता है।

स्ट्रासेन एल्गोरिदम के नुकसान (Disadvantages of Strassen's Algorithm)

• यह छोटे मैट्रिक्स के लिए प्रभावी नहीं होता।
• अतिरिक्त स्थान (Extra Space) की आवश्यकता होती है।
• गणना अधिक जटिल होती है।

निष्कर्ष

स्ट्रासेन का मैट्रिक्स गुणा एल्गोरिदम पारंपरिक गुणा की तुलना में अधिक प्रभावी है, विशेष रूप से बड़े मैट्रिक्स के लिए। हालाँकि, छोटे मैट्रिक्स के लिए पारंपरिक एल्गोरिदम अधिक उपयुक्त हो सकता है।