O(n log n) ए टोग्लिट्ज मैट्रिक्स के उत्पाद के लिए एल्गोरिदम और सही लंबाई का वेक्टर अच्छी तरह से जाना जाता है: इसे एक परिसंचरण मैट्रिक्स में डाल दें, इसे वेक्टर (और बाद के शून्य) से गुणा करें, और शीर्ष n तत्वों को वापस करें उत्पाद।दो Toeplitz matrices का उत्पाद?
मुझे एक ही आकार के दो टोप्लिट्ज मैट्रिक्स को गुणा करने के लिए सर्वश्रेष्ठ (समय-वार) एल्गोरिदम खोजने में परेशानी हो रही है।
क्या कोई मुझे इसके लिए एल्गोरिदम दे सकता है?
यहां एक ओ (एन^2) -टाइम एल्गोरिदम है।
उत्पाद मैट्रिक्स के विकर्णों में से किसी एक की गणना करने के लिए, हमें लॉकस्टेप में स्लाइडिंग की लंबाई-(2 एन -1) सूचियों की लंबाई-एन विंडो पर डॉट उत्पादों की गणना करने की आवश्यकता है। दो लगातार प्रविष्टियों के बीच अंतर समय ओ (1) में गणना की जा सकती है।
उदाहरण के लिए,
e f g h i o p q r s
d e f g h m o p q r
c d e f g l m o p q
b c d e f k l m o p
a b c d e j k l m o
के उत्पाद 1,1 प्रविष्टि eo + fm + gl + hk + ij है पर विचार करें। 2,2 प्रविष्टि dp + eo + fm + gl + hk है, या 1,1 प्रविष्टि शून्य ij प्लस dp है। 3,3 प्रविष्टि cq + dp + eo + fm + gl है, या 2,2 प्रविष्टि शून्य hk प्लस cq है। 4,4 प्रविष्टि br + cq + dp + eo + fm, आदि
यदि आप इसे फ़्लोटिंग पॉइंट में कार्यान्वित करते हैं, तो catastrophic cancellation पर ध्यान रखें।
Toeplitz matrices का उत्पाद जरूरी नहीं है Toeplitz। आउटपुट का प्रतिनिधित्व कैसे किया जाता है? –
एक एनएक्सएन मैट्रिक्स के रूप में, क्योंकि कोई अन्य प्रतिनिधित्व नहीं है जो इस मामले में सभी प्रासंगिक डेटा प्रदर्शित करेगा। मैं एक एल्गोरिदम नहीं मांग रहा हूं जो 'ओ (एन^2)' से तेज़ चलता है, मैं केवल इस बात में सोच रहा हूं कि इस मामले में मानक मैट्रिक्स गुणात्मक दिनचर्या की तुलना में तेज़ एल्गोरिदम है या नहीं। –
एक ओ (एन^2 लॉग एन) एल्गोरिदम है जो एन मैट्रिक्स-वेक्टर गुणा करता है। अगर कोई ओ (एन^2) एल्गोरिदम था तो मुझे आश्चर्य नहीं होगा, लेकिन मैं नहीं कह सकता कि मैं इसे ढूंढने के लिए उत्सुक हूं। –