एन के निर्धारक को लेने का कुशल तरीका! एक्स एन! मेपल में मैट्रिक्स

Question

मेरे पास एक बड़ा मैट्रिक्स है, एन! एक्स एन !, जिसके लिए मुझे निर्धारक लेने की जरूरत है। n के प्रत्येक क्रमचय के लिए, मैं सहयोगी

• लंबाई 2n का एक वेक्टर (यह आसान computationally है)
• 2n चर में का एक बहुपद (एन पर पुनरावर्ती अभिकलन रैखिक कारकों में से एक उत्पाद)

मैट्रिक्स वेक्टरों (पॉइंट्स के रूप में विचार) पर बहुपदों के लिए मूल्यांकन मैट्रिक्स है। तो सिग्मा, मैट्रिक्स (क्रमपरिवर्तन द्वारा अनुक्रमित) की ताऊ प्रविष्टि टाउ के लिए वेक्टर में मूल्यांकन सिग्मा के लिए बहुपद है।

उदाहरण: n=3 के लिए, यदि i वें बहुपद (x1 - 4)(x3 - 5)(x4 - 4)(x6 - 1) है और j वें बिंदु (2,2,1,3,5,2) है, तो मैट्रिक्स के (i,j) वीं प्रविष्टि (2 - 4)(1 - 5)(3 - 4)(2 - 1) = -8 हो जाएगा। यहां n=3, इसलिए अंक R^(3!) = R^6 में हैं और बहुपदों में 3!=6 चर हैं।

मेरा लक्ष्य यह निर्धारित करना है कि मैट्रिक्स नॉनसिंगुलर है या नहीं।

---

मेरे दृष्टिकोण अभी यह है:

• समारोह point एक क्रमचय ले जाता है और एक वेक्टर
• समारोह poly एक क्रमचय ले जाता है और एक बहुपद
• समारोह nextPerm देता आउटपुट आउटपुट लेक्सिकोग्राफिक ऑर्डर

में अगला क्रमपरिवर्तन

मेरी कोड के संक्षिप्त स्यूडोकोड संस्करण इस प्रकार है:

B := []; 
P := []; 
w := [1,2,...,n]; 
while w <> NULL do 
    B := B append poly(w); 
    P := P append point(w); 
    w := nextPerm(w); 
od; 

// BUILD A MATRIX IN MAPLE 
M := Matrix(n!, (i,j) -> eval(B[i],P[j])); 

// COMPUTE DETERMINANT IN MAPLE 
det := LinearAlgebra[Determinant](M); 

// TELL ME IF IT'S NONSINGULAR 
if det = 0 then return false; 
else return true; fi; 

मैं समारोह LinearAlgebra[Determinant] में बनाया का उपयोग कर मेपल में काम कर रहा हूँ, लेकिन सब कुछ एक कस्टम बनाया समारोह निम्न स्तर मेपल कार्यों का उपयोग करता है (उदाहरण के लिए seq, convert और cat)।

मेरी समस्या यह है कि यह बहुत लंबा लगता है, जिसका अर्थ है कि मैं धैर्य के साथ n=7 तक जा सकता हूं, लेकिन n=8 प्राप्त करने में दिन लगते हैं। आदर्श रूप में, मैं n=10 पर पहुंचने में सक्षम होना चाहता हूं।

क्या किसी के पास कोई विचार है कि मैं समय को कैसे सुधार सकता हूं? मैं एक अलग भाषा में काम करने के लिए खुला हूं, उदा। मैटलैब या सी, लेकिन मैपल के भीतर इसे गति देने का एक तरीका ढूंढना पसंद करेंगे।

मुझे एहसास है कि सभी गॉरी विवरणों के बिना जवाब देना मुश्किल हो सकता है, लेकिन प्रत्येक फ़ंक्शन के लिए कोड, उदा। point और poly, पहले से ही अनुकूलित किया गया है, इसलिए असली सवाल यह है कि अगर फ्लाई पर मैट्रिक्स का निर्माण करके निर्धारक को लेने का कोई तेज़ तरीका है, या ऐसा कुछ।

---

अद्यतन: यहाँ दो विचारों कि मुझे लगता है कि के साथ toyed है काम नहीं करते हैं:

1. मैं बहुआयामी पद स्टोर कर सकते हैं (क्योंकि वे कुछ समय ले गणना करने के लिए, मुझे नहीं पता

   

   : फिर से करना है कि मैं इसे) लंबाई n! का एक वेक्टर में मदद कर सकते हैं, और मक्खी पर अंक की गणना, और निर्धारक के लिए क्रमचय सूत्र में इन मूल्यों को प्लग चाहते हैं

   यहां समस्या यह है कि यह मैट्रिक्स के आकार में O(N!) है, इसलिए मेरे मामले के लिए यह O((n!)!) होगा। जब n=10, (n!)! = 3,628,800! जो कि करने के लिए भी बड़ा करने का तरीका है।

2. LU अपघटन का उपयोग करके निर्धारक की गणना करें। सौभाग्य से, मेरे मैट्रिक्स का मुख्य विकर्ण nonzero है, इसलिए यह व्यवहार्य है। चूंकि यह मैट्रिक्स के आकार में O(N^3) है, यह O((n!)^3) बन जाता है जो कि करने योग्य के करीब है। हालांकि, समस्या यह है कि मुझे पूरे मैट्रिक्स को स्टोर करने की आवश्यकता है, जो स्मृति पर गंभीर तनाव डालता है, रन टाइम को कभी नहीं रोकता है। तो यह कम से कम कुछ और चतुरता के बिना कम से कम काम नहीं करता है। कोई विचार?

Answer 1

सुनिश्चित नहीं है कि मैंने आपकी समस्या का पालन किया है; क्या यह निम्नलिखित है (या इसे कम करता है)?

आप n संख्या के दो वैक्टर, उन्हें फोन x और c, तो मैट्रिक्स तत्व प्रत्येक पंक्ति/स्तंभ x और c के विशिष्ट orderings करने के लिए इसी के साथ (x_k+c_k) की k से अधिक उत्पाद है, है?

यदि ऐसा है, तो मुझे विश्वास है कि जब भी x या c में दोहराए गए मान होते हैं, तो मैट्रिक्स एकवचन होगा, क्योंकि मैट्रिक्स में पंक्तियों/स्तंभों को दोहराया जाएगा। यदि यह मामला गैर विलक्षण सामान्य रूप में देखने के लिए x और c के विशिष्ट मूल्यों के साथ एक छोटे n पर मोंटे कार्लो के का एक समूह का प्रयास करें - यह काफी संभावना है कि अगर 6 के लिए सच है, यह 10

के लिए सच हो जाएगा जहां तक ​​जानवर बल चला जाता है, अपने विधि:

1. एक गैर स्टार्टर
2. अधिक तेजी से काम करेगा (n=7 के लिए कुछ ही सेकंड होना चाहिए), हालांकि LU के बजाय आप SVD की कोशिश करना चाहते हो सकता है है , जो आपको यह बताने का एक बेहतर काम करेगा कि आपका मैट्रिक्स कितना अच्छा व्यवहार करता है।

Answer 2

यदि आपकी समस्या स्थान या समय है तो यह मुझे स्पष्ट नहीं है। स्पष्ट रूप से दो व्यापार आगे और आगे। यदि आप केवल यह जानना चाहते हैं कि निर्धारक सकारात्मक है या नहीं, तो आपको निश्चित रूप से LU अपघटन के साथ जाना चाहिए। कारण यह है कि निर्धारित करने के लिए करता है, तो A = LUL कम त्रिकोणीय और U ऊपरी त्रिकोणीय, तो

det(A) = det(L) det(U) = l_11 * ... * l_nn * u_11 * ... * u_nn 

साथ ताकि आप केवल जरूरत है L या U की मुख्य विकर्ण प्रविष्टियों में से किसी 0 है।

आगे सरलीकृत करने के लिए, डूलिटल के एल्गोरिदम का उपयोग करें, जहां l_ii = 1। यदि किसी भी समय एल्गोरिदम टूट जाता है, तो मैट्रिक्स एकवचन होता है ताकि आप रुक सकें।

for k := 1, 2, ..., n do { 
    for j := k, k+1, ..., n do { 
    u_kj := a_kj - sum_{s=1...k-1} l_ks u_sj; 
    } 
    for i = k+1, k+2, ..., n do { 
    l_ik := (a_ik - sum_{s=1...k-1} l_is u_sk)/u_kk; 
    } 
} 

कुंजी आप U की i वीं पंक्ति और एक ही समय में L की i वें स्तंभ की गणना कर सकते हैं, और आप केवल आगे बढ़ने के लिए पिछले पंक्ति/स्तंभ पता करने की जरूरत: यहाँ सार है । इस तरह आप उतनी ही प्रक्रिया को जितना कर सकते हैं उतना ही उतना ही कर सकते हैं जितना आप चाहते हैं। चूंकि आप आवश्यकतानुसार a_ij प्रविष्टियों की गणना कर सकते हैं, इसके लिए आपको n की लंबाई के दो वैक्टरों को स्टोर करने की आवश्यकता होती है जबकि लंबाई के दो और वैक्टर n (U की पंक्तियां, L के कॉलम) उत्पन्न करते हैं। एल्गोरिदम n^2 समय लेता है। आप कुछ और चालें पा सकते हैं, लेकिन यह आपके स्पेस/टाइम ट्रेड ऑफ पर निर्भर करता है।