Matrix Multiplication
Standard Matrix Multiplication
1969 में Volker Strassen ने यह दिखाया कि matrix multiplication को पारंपरिक O(n³) की तुलना में तेज़ी से, यानी O(n^2.8074) समय में किया जा सकता है। यह algorithm theoretical और practical दोनों दृष्टि से बहुत महत्वपूर्ण है।
Strassen algorithm एक Divide and Conquer strategy पर आधारित है, जिसमें बड़ी matrix को चार बराबर sub-matrices में divide किया जाता है। इसके बाद केवल 7 cleverly defined multiplications और कुछ additions/subtractions की मदद से final matrix प्राप्त की जाती है।
पारंपरिक divide & conquer method में 8 multiplications होते हैं, लेकिन Strassen में सिर्फ 7 multiplications होने के कारण यह अधिक efficient और तेज़ है।
Strassen’s Algorithm : The Divide and Conquer Strategy
Strassen’s Algorithm Divide and Conquer paradigm पर आधारित है। यह Standard Algorithm से अलग है क्योंकि यह sub-problems को clever तरीके से solve करता है।
मान लीजिए हमारे पास दो matrices A और B हैं — दोनों n × n, और n power of 2 (जैसे 2, 4, 8, 16, …) है।
Step 1 — Divide (विभाजन)
A और B को 4 sub‑matrices में बाँटते हैं, हर एक size = (n/2) × (n/2):
A = | A11 A12 |
| A21 A22 |
B = | B11 B12 |
| B21 B22 |
Step 2 — Compute 7 intermediate matrices (M1 … M7)
Strassen ने 7 specially defined combinations suggest किए:
M1 = (A11 + A22) × (B11 + B22)
M2 = (A21 + A22) × B11
M3 = A11 × (B12 – B22)
M4 = A22 × (B21 – B11)
M5 = (A11 + A12) × B22
M6 = (A21 – A11) × (B11 + B12)
M7 = (A12 – A22) × (B21 + B22)
Step 3 — Combine (जोड़कर पूरा result निकालना)
अब final product C को sub‑matrices C11, C12, C21, C22 में assemble करते हैं:
C11 = M1 + M4 – M5 + M7
C12 = M3 + M5
C21 = M2 + M4
C22 = M1 – M2 + M3 + M6
C = | C11 C12 |
| C21 C22 |
इस तरह पूरा matrix C मिल जाता है।
Time Complexity
1. Classical Matrix Multiplication (Naive Method)
दो n × n matrices को multiply करने के लिए traditional method :
C[i][j]=k=1∑nA[i][k]∗B[k][j]
- हर element compute करने के लिए n multiplications + (n–1) additions
- Total operations = n² × n ≈ O(n³)
2. Strassen Algorithm – Recurrence Relation
Strassen method divide-and-conquer approach use करता है।
- Matrix size n×n → 4 sub-matrices of size n/2 × n/2
- हर recursion level : 7 multiplications (instead of 8) + O(n²) additions
- Recurrence : T(n)=7⋅T(n/2)+O(n2)
- 7 recursive multiplications
- O(n²) additions/subtractions per level
Advantages (लाभ)
- Faster than Classical Method : Classical matrix multiplication की time complexity O(n³) होती है, जबकि Strassen algorithm की complexity लगभग O(n².8074) है। इसका मतलब है कि बड़े matrices के लिए यह पारंपरिक method से कहीं तेज़ काम करता है।
- Divide and Conquer Approach : Strassen algorithm Divide and Conquer strategy पर काम करता है। यह problem को छोटे sub-matrices में break करके solve करता है, जिससे algorithm का logical structure समझना आसान हो जाता है।
- Better for Large Matrices : जब matrices बड़ी होती हैं, Strassen method काफी कम multiplication operations करता है, जिससे performance improve होती है।
- Recursive Implementation Possible : Recursive approach होने के कारण इसे आसानी से programmatically implement किया जा सकता है।
Disadvantages (हानियाँ)
- Numerical Stability Issues : Strassen algorithm में extra additions और subtractions होती हैं, जिससे rounding errors बढ़ सकते हैं। यह numerical sensitive applications में problem create कर सकता है।
- Not Efficient for Small Matrices : Small matrices के लिए classical O(n³) method जल्दी और आसान होती है। Strassen की recursion overhead छोटे matrices में useless होती है।
- Memory Overhead : Algorithm में extra temporary matrices create करनी पड़ती हैं। इसलिए इसकी space complexity classical method से ज्यादा होती है।
- Implementation Complexity : Classical multiplication की तुलना में इसे implement करना थोड़ा ज्यादा complex है।
