ट्रेस (एबी^{- 1}) की कुशल गणना ने ए और बी

Question

दिया है मेरे पास दो स्क्वायर मैट्रिस ए और बी ए सममित है, बी सममित सकारात्मक निश्चित है। मैं $ ट्रेस (एबी^{- 1}) $ गणना करना चाहता हूं। अभी के लिए, मैं बी के Cholesky अपघटन की गणना, समीकरण $ ए = सीबी $ में सी के लिए हल और विकर्ण तत्वों को जोड़।

क्या आगे बढ़ने का एक और अधिक प्रभावी तरीका है?

मैं ईजिन का उपयोग करने की योजना बना रहा हूं। यदि मैट्रिस स्पैस हैं तो ए कार्यान्वयन प्रदान कर सकता है (ए अक्सर विकर्ण हो सकता है, बी अक्सर बैंड-विकर्ण होता है)?

Answer 1

तो B विरल है, यह कुशल हो सकता है (अर्थात हे (एन), B की अच्छी स्थिति संख्या संभालने)

B x_i = a_i 

में x_i के लिए हल करने के लिए (नमूना Conjugate Gradient कोड विकिपीडिया पर दिया जाता है)। A के कॉलम वैक्टर होने के लिए, आपको O (n^2) में मैट्रिक्स B^{-1} A मिलता है। फिर आप ट्रेस प्राप्त करने के लिए विकर्ण तत्वों को जोड़ सकते हैं। आम तौर पर, eigenvalues ​​का पूरा सेट प्राप्त करने के बजाय इस स्पैस उलटा गुणा करना आसान है। तुलना के लिए, Cholesky decomposition ओ (एन^3) है। (चोरस्की के बारे में डैरेन Engwirda की टिप्पणी नीचे देखें)।

आप केवल पता लगाने के लिए एक सन्निकटन की जरूरत है, तो आप वास्तव हे (क्यू एन) के लिए लागत q यादृच्छिक वैक्टर r से अधिक

r^T (A B^{-1}) r 

औसत से कम कर सकते हैं। आमतौर पर q << n। यह प्रदान की है कि यादृच्छिक वेक्टर r के घटकों को संतुष्ट

< r_i r_j > = \delta_{ij} 

जहां <...>r के वितरण पर एक औसत इंगित करता है एक निष्पक्ष अनुमान है। उदाहरण के लिए, घटक r_i यूनिट भिन्नता के साथ वितरित स्वतंत्र गाऊशियन हो सकता है। या वे + -1 से समान रूप से चुना जा सकता है। आमतौर पर ओ (एन) जैसे ट्रेस स्केल और ओ (वर्ग (एन/क्यू)) जैसे ट्रेस अनुमान स्केल में त्रुटि, इसलिए सापेक्ष ओ (वर्ग (1/एनक्यू) के रूप में त्रुटि स्केल)।

Answer 2

यदि सामान्यीकृत ईजिनेंग्यू गणना करने के लिए अधिक कुशल हैं, तो आप सामान्यीकृत eigenvalues, A*v = lambda* B *v की गणना कर सकते हैं और फिर सभी lambdas को जोड़ सकते हैं।