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

Question

क्या कोई व्यक्ति सहज ज्ञान में मैट्रिक्स गुणा के लिए स्ट्रैसेन के एल्गोरिदम को समझा सकता है? मैं किताब और विकी में स्पष्टीकरण (अच्छी तरह से, जाने की कोशिश की) के माध्यम से चला गया है, लेकिन यह ऊपर की ओर क्लिक नहीं कर रहा है। वेब पर कोई भी लिंक जो औपचारिक नोटेशन इत्यादि के बजाय बहुत सी अंग्रेजी का उपयोग करता है, भी सहायक होगा। क्या कोई ऐसी रचनाएं हैं जो मुझे इस एल्गोरिदम को याद रखने के बिना स्क्रैच से बनाने में मदद कर सकती हैं?

Answer 1

विकिपीडिया पर एक त्वरित नज़र डालें और ऐसा लगता है कि यह एल्गोरिदम समीकरणों को पुन: व्यवस्थित करके आवश्यक गुणाओं की संख्या में मामूली कमी है।

यहां एक समानता है। x*x + 5*x + 6 में कितने गुणाएं हैं? दो, सही? (x+2)(x+3) में कितने गुणाएं हैं? एक, है ना? लेकिन वे एक ही अभिव्यक्ति हैं!

नोट, मुझे यह उम्मीद नहीं है कि यह एल्गोरिदम की गहरी समझ प्रदान करे, केवल एक अंतर्ज्ञानी तरीका जिसमें आप समझ सकें कि एल्गोरिदम संभावित रूप से गणना जटिलता में सुधार कैसे कर सकता है।

Answer 2

मेरी राय में 3 विचारों है कि आप प्राप्त करने की आवश्यकता नहीं है:

1. आप ब्लॉक में एक मैट्रिक्स विभाजित है और जैसे आप संख्या की मैट्रिक्स पर होगा ब्लॉकों के परिणामस्वरूप मैट्रिक्स पर काम कर सकते हैं। विशेष रूप से आप दो ऐसे ब्लॉक मैट्रिक्स को गुणा कर सकते हैं (बेशक जब तक एक में ब्लॉक पंक्तियों की संख्या दूसरे में ब्लॉक कॉलम की संख्या से मेल खाती है) और उसी परिणाम प्राप्त करें जैसे आप संख्याओं के मूल मैट्रिक्स गुणा करते हैं।

2. 2x2 ब्लॉक मैट्रिक्स गुणा के परिणाम को व्यक्त करने के लिए आवश्यक ब्लॉक के मूल सूत्र के मुकाबले कम गुणाओं में कंप्यूटिंग करने की अनुमति देने के लिए पर्याप्त सामान्य कारक हैं। यह Tony's answer में वर्णित चाल है।

3. रिकर्सन।

स्ट्रैसेन एल्गोरिदम केवल उपरोक्त का एक आवेदन है। इसकी जटिलता के विश्लेषण को समझने के लिए, आपको रोनाल्ड ग्राहम, डोनाल्ड Knuth, और ओरेन Patashnik या एक समान पुस्तक द्वारा "Concrete Mathematics" पढ़ने की जरूरत है। इस प्रकार

Answer 3

, दो 2x2 मैट्रिक्स गुणा पर विचार करें:

A B * E F = AE+BG AF+BH 
C D G H CE+DG CF+DH 

दाईं ओर गणना करने के लिए स्पष्ट तरीका 8 गुणा करता है और 4 अतिरिक्त करने के लिए बस है। लेकिन कल्पना करें कि गुणों की तुलना में गुणा अधिक महंगा है, इसलिए यदि संभव हो तो हम गुणाओं की संख्या को कम करना चाहते हैं। स्ट्रैसेन एक कम गुणा और बहुत अधिक जोड़ों (और कुछ घटाव) के साथ दाईं ओर की गणना करने के लिए एक चाल का उपयोग करता है।

M1 = (A + D) * (E + H) = AE + AH + DE + DH 
M2 = (A + B) * H = AH + BH 
M3 = (C + D) * E = CE + DE 
M4 = A * (F - H) = AF - AH 
M5 = D * (G - E) = DG - DE 
M6 = (C - A) * (E + F) = CE + CF - AE - AF 
M7 = (B - D) * (G + H) = BG + BH - DG - DH 

तो गणना करने के लिए एई + बीजी, एम 1 + M7 (जो हमें एई और बीजी शर्तों हो जाता है), तो/जोड़ने अन्य सुश्री से कुछ घटाना तक के साथ शुरू:

यहाँ 7 गुणा कर रहे हैं एई + बीजी हम सब के साथ छोड़ दिया गया है। चमत्कारी रूप से, एम को चुना जाता है ताकि एम 1 + एम 7-एम 2 + एम 5 काम करता है। अन्य 3 परिणामों के साथ ही आवश्यक है।

अब यह केवल 2x2 मैट्रिक्स के लिए ही काम नहीं करता है, लेकिन किसी भी (यहां तक ​​कि) आकार के मैट्रिस के लिए जहां ए..एच सबमिटरिस हैं।