डीएए - स्ट्रैसेन का मैट्रिक्स गुणन

इस अध्याय में, पहले हम मैट्रिक्स गुणन की सामान्य विधि के बारे में चर्चा करेंगे और बाद में हम स्ट्रैसेन के मैट्रिक्स गुणन एल्गोरिथम पर चर्चा करेंगे।

समस्या का विवरण

आइए हम दो मैट्रिक्स पर विचार करें X तथा Y। हम परिणामी मैट्रिक्स की गणना करना चाहते हैंZ गुणा करके X तथा Y।

Nave विधि

सबसे पहले, हम भोली विधि और इसकी जटिलता पर चर्चा करेंगे। यहां, हम गणना कर रहे हैंZ = X × Y। Na Usingve विधि, दो मैट्रिसेस का उपयोग करना (X तथा Y) इन गुणकों के क्रम को गुणा किया जा सकता है p × q तथा q × r। निम्नलिखित एल्गोरिथ्म है।

Algorithm: Matrix-Multiplication (X, Y, Z) 
for i = 1 to p do 
   for j = 1 to r do 
      Z[i,j] := 0 
      for k = 1 to q do 
         Z[i,j] := Z[i,j] + X[i,k] × Y[k,j]

जटिलता

यहाँ, हम मान लेते हैं कि पूर्णांक संचालनों को लेते हैं O(1)समय। वहा तीन हैforइस एल्गोरिथ्म में छोरों और एक दूसरे में निहित है। इसलिए, एल्गोरिथ्म लेता हैO(n³) अमल करने का समय।

स्ट्रैसन का मैट्रिक्स गुणन एल्गोरिथम

इस संदर्भ में, स्ट्रैसन मैट्रिक्स मैट्रिक्स एल्गोरिथ्म का उपयोग करते हुए, समय की खपत को थोड़ा सुधार किया जा सकता है।

स्ट्रैसन की मैट्रिक्स गुणन पर ही प्रदर्शन किया जा सकता है square matrices कहाँ पे n एक है power of 2। दोनों मैट्रिसेस के ऑर्डर हैंn × n।

फूट डालो X, Y तथा Z नीचे दिए गए अनुसार चार (n / 2) × (n / 2) मैट्रीस -

$ Z = \ start {bmatrix} I और J \\ K & L \ end {bmatrix} $ $ X = \ start {bmatrix} A & B \\ C & D \ end {bmatrix} $ और $ Y = शुरू {bmatrix} E & F \\ G & H \ end {bmatrix} $

स्ट्रैसेन के एल्गोरिथ्म का उपयोग निम्नलिखित की गणना करता है -

$ $ M_ {1} \: \ colon = (A + C) \ टाइम्स (E + F) $$

$ $ M_ {2} \: \ colon = (B + D) \ गुना (G + H) $ $

$ $ M_ {3} \: \ colon = (AD) \ गुना (E + H) $ $

$ $ M_ {4} \: \ colon = A \ टाइम्स (FH) $ $

$$ M_ {5} \: \ colon = (C + D) \ गुना (E) $ $

$ $ M_ {6} \: \ colon = (A + B) \ गुना (H) $ $

$ $ M_ {7} \: \ colon = D \ टाइम्स (GE) $ $

फिर,

$ $ I \: \ colon = M_ {2} + M_ {3} - M_ {6} - M_ {{}}

$ $ J \: \ colon = M_ {4} + M_ {6} $ $

$ $ K \: \ colon = M_ {5} + M_ {7} $ $