कम मैट्रिक्स गुणन घातांक

विज्ञान समाचार: मैट्रिक्स का आकार अब जानते हैं कि कैसे गुणा करना है । दूसरे शब्दों में, यह साबित होता है कि जहाँ - मैट्रिक्स गुणन का घातांक । हाल ही में, वर्जीनिया वासिलेव्स्का-विलियम्स ने इसे साबित किया, जिससे अनुमान में सुधार हुआ 1987 में Coppersmith और Grapes द्वारा प्राप्त किया गया। मैं इस एल्गोरिथ्म के महत्व के बारे में काफी थोड़ा लिखूंगा। जो लोग अधिक सीखने में रुचि रखते हैं, उन्हें स्कॉट आरोनसन , रिचर्ड लिप्टन और बिल गैसार्च के पदों को पढ़ने के लिए आमंत्रित किया जाता है।

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

कुछ और उदाहरण:

• सभी जोड़े के बीच अंतर (सभी जोड़े सबसे छोटा रास्ता)।
  एक अनवटी ग्राफ में सभी जोड़े के बीच के सबसे छोटे रास्ते समय में मिल सकते हैं । ऐसा करने के लिए, हम आसन्न मैट्रिक्स को पावर n (इसलिए, o (1) रेंगने की शक्ति तक) बढ़ाते हैं, साथ ही साथ सबसे छोटे रास्तों की गणना करते हैं। आप विवरण, साथ ही कई अन्य इसी तरह के सुरुचिपूर्ण एल्गोरिदम से पता लगा सकते हैं
  उरी ज़्विक द्वारा उत्कृष्ट प्रस्तुति।
• अधिकतम 2-व्यवहार्यता समस्या (MAX-2-SAT)।
  इस कार्य के लिए एकमात्र ज्ञात एल्गोरिथ्म जो विस्तृत खोज की तुलना में तेजी से काम करता है ( ), मैट्रिक्स गुणन पर भी आधारित है। उनके काम का समय बराबर है और यह घातीय मेमोरी का उपयोग करता है। संक्षेप में, विचार यह है: इनपुट फॉर्मूला का उपयोग करके, हम एक विशाल ग्राफ (पर) का निर्माण करते हैं वर्टिकल) और तेज मैट्रिक्स गुणन का उपयोग करके हम यह देखने के लिए जांचते हैं कि क्या इसमें कोई त्रिकोण है। यह उल्लेखनीय है कि उन्होंने अपने पति वर्जीनिया - रेयान विलियम्स का आविष्कार किया था।
• हैमिल्टनियन वे (हैमिल्टनियन चक्र)।
  अभी भी एक ऐसा मज़ेदार उदाहरण है जिसमें यह इतना महत्वपूर्ण नहीं है कि हम कितने मैट्रिसेस को गुणा कर सकते हैं, लेकिन फिर भी। समय में हैमिल्टनियन मार्ग खोजने के लिए एक एल्गोरिथ्म और बहुपद मेमोरी (ध्यान दें कि इस समस्या के लिए प्रसिद्ध हेल्ड-कार्प एल्गोरिदम गतिशील प्रोग्रामिंग पर आधारित है और घातीय मेमोरी की आवश्यकता है): यह ऊपर बताए गए ट्रिक का उपयोग करके ग्राफ वर्टिकल के सभी सबसेट पर लंबाई n-1 के रास्तों की संख्या की गणना करता है; इसके बाद, समावेशन-बहिष्करण सूत्र आपको मिली संख्याओं को योग करने की अनुमति देता है ताकि केवल लंबाई n-1 के सरल पथों की संख्या बनी रहे (और यह हैमिल्टन मार्ग है)।