ऊपरी-त्रिकोणीय मैट्रिक्स के eigenvectors: numpy.linalg.eig को सीधे चलाएँ

ऊपरी-त्रिकोणीय मैट्रिक्स पर eigenvectors निकालने का सबसे तेज़ तरीका: numpy.linalg.eig. QR चरण छोटा, LAPACK फास्ट-पाथ का लाभ; बेंचमार्क में 10–20x तक स्पीडअप. कोड उदाहरण भी

जब आपकी इनपुट मैट्रिक्स त्रिकोणीय होती है, तो गुणांक मान (eigenvalues) सीधे विकर्ण से “मुफ्त” में मिल जाते हैं। ऐसे में सामान्य-उद्देश्य रूटीनों को दरकिनार करके, विकर्णीकरण या eigenvectors निकालने के लिए कोई तेज़, कस्टम तरीका लिखने का मन हो सकता है। लेकिन बात यह है कि त्रिकोणीय मैट्रिक्स का विकर्णीकरण हमेशा संभव नहीं होता, और कई बार केवल eigenvectors चाहिए हों तब भी तैयार-उपलब्ध तरीका ही सबसे तेज़ निकलता है।

समस्या की रूपरेखा

उद्देश्य है—कई त्रिकोणीय मैट्रिसेज़ के eigenvectors निकालना, वह भी अनावश्यक ओवरहेड के बिना। चूंकि विकर्ण से eigenvalues तुरंत मिल जाती हैं, इसलिए हर λ के लिए (A − λI)x = 0 हल करना आकर्षक लग सकता है। मगर जब आपके पास सैकड़ों मैट्रिसेज़ हों और प्रत्येक में उतने ही eigenvalues हों, तो प्रति-eigenvalue हलों की लागत जल्दी ही बढ़ जाती है। व्यावहारिक सवाल यह है कि क्या numpy.linalg.eig यहाँ “बहुत जनरल” है, या यह पहले से ही त्रिकोणीय इनपुट के लिए अनुकूलित है।

कोड उदाहरण: तरीकों की बेंचमार्किंग

नीचे दिया स्निपेट घनी (dense) रैंडम मैट्रिसेज़ और उनकी ऊपरी-त्रिकोणीय प्रतियों पर, eigen-decomposition की प्रदर्शन क्षमता की तुलना QR और LU फैक्टराइज़ेशन से करता है।

import numpy as np
import scipy.linalg as sla
np.random.seed(42)

for dim in [100, 1000]:
    print(f"benchmark on size {dim}")
    mat = np.random.normal(size=(dim, dim))
    print("dense input")
    %timeit np.linalg.eig(mat)
    %timeit np.linalg.qr(mat)
    %timeit sla.lu_factor(mat)
    print("upper triangular input")
    tri = np.random.normal(size=(dim, dim))
    tri = np.triu(tri)
    %timeit np.linalg.eig(tri)
    %timeit np.linalg.qr(tri)
    %timeit sla.lu_factor(tri)

असल में क्या हो रहा है

कुशल एल्गोरिद्म जो eigenvectors निकालते हैं, वे अक्सर उसी प्रक्रिया में eigenvalues भी दे देते हैं; इसलिए एक ही रूटीन कॉल करने से कुछ खोता नहीं। व्यवहार में, numpy.linalg.eig तब भी अच्छी तरह ट्यून रहता है जब इनपुट पहले से ऊपरी-त्रिकोणीय हो। इम्प्लिमेंटेशन देखने पर पता चलता है कि OpenBLAS, ऊपरी-त्रिकोणीय रूप में लाने के लिए QR फैक्टराइज़ेशन करता है और फिर eigenvalues तथा eigenvectors पाने के लिए LAPACK की strevc3_ रूटीन का उपयोग करता है। अगर आप शुरुआत से ही ऊपरी-त्रिकोणीय मैट्रिक्स दें, तो QR वाला चरण विशेष रूप से तेज़ हो जाता है।

प्रायोगिक टाइमिंग भी यही दिखाती है। आकार 100 की ऊपरी-त्रिकोणीय इनपुट पर np.linalg.eig लगभग सैकड़ों माइक्रोसेकंड में पूरा हो जाता है, जबकि आकार 1000 पर यह लगभग सैकड़ों मिलीसेकंड लेता है। उसी सेटअप में, पूर्ण घनी मैट्रिक्स पर eig चलाने में आकार 100 के लिए करीब 11.7 ms और आकार 1000 के लिए लगभग 1.31 s लगते हैं। यानी, त्रिकोणीय इनपुट पर यह घनी इनपुट की तुलना में बड़ा स्पीडअप देता है।

समाधान: त्रिकोणीय इनपुट पर सीधे numpy.linalg.eig इस्तेमाल करें

यदि आपके पास पहले से ऊपरी-त्रिकोणीय मैट्रिक्स है, तो eig को सीधे कॉल करें। इस तरह प्रति-eigenvalue हलों का ओवरहेड बचता है और फास्ट-पाथ का लाभ मिलता है। नीचे न्यूनतम उपयोग का उदाहरण है।

import numpy as np
np.random.seed(42)

n = 1000
tri = np.triu(np.random.normal(size=(n, n)))
vals, vecs = np.linalg.eig(tri)

विस्तृत परीक्षणों में, समान आकार की घनी मैट्रिसेज़ की तुलना में ऊपरी-त्रिकोणीय मैट्रिसेज़ पर यह तरीका लगभग 10x–20x तेज़ रहा है। पहले दिए बेंचमार्क में भी यही रुझान दिखता है, जहाँ त्रिकोणीय इनपुट पर eig आकार 100 के लिए लगभग 438 µs बनाम 11.7 ms में पूरा होता है, और आकार 1000 के लिए लगभग 157 ms बनाम 1.31 s।

यदि आप Python से strevc3_ को सीधे कॉल करने का सोच रहे हैं, तो इसका आसान रास्ता नहीं है। SciPy और NumPy में भीतर से strevc3_ या dtrevc3 रूटीन मौजूद तो हैं, लेकिन किसी भी लाइब्रेरी में इनके लिए कोई सार्वजनिक Python-स्तरीय रैपर उपलब्ध नहीं है।

विकर्णीकरण पर एक ज़रूरी चेतावनी

eigenvectors निकालने और किसी मैट्रिक्स का विकर्णीकरण करने में महत्वपूर्ण फर्क है। हर त्रिकोणीय मैट्रिक्स विकर्णीकरण-योग्य नहीं होती। एक सरल प्रत्युदाहरण है [[1, 1], [0, 1]]: इसमें केवल एक eigenvalue है और आधार बनाने के लिए पर्याप्त रैखिक रूप से स्वतंत्र eigenvectors नहीं हैं, इसलिए इसका विकर्णीकरण संभव नहीं। यदि आपका अंतिम लक्ष्य सख्ती से विकर्णीकरण है, तो पहले यह सुनिश्चित करें कि यह सैद्धांतिक रूप से संभव है; वरना, eigenvectors कितनी भी जल्दी क्यों न निकालें, विकर्ण रूप बनाना विफल ही होगा।

यह क्यों मायने रखता है

जब बहुत-सी मैट्रिसेज़ प्रोसेस करनी हों, तो स्थिर कारकों में थोड़ी-सी कटौती भी रनटाइम को नाटकीय रूप से बदल देती है। अच्छी तरह अनुकूलित eigen-decomposition अपनाने से त्रिकोणीय इनपुट के लिए फास्ट-पाथ मिलते हैं और प्रति-eigenvalue हलों का अतिरिक्त ओवरहेड नहीं जुड़ता। इससे आपका कोड भी छोटा और आसान-से-देखरेख योग्य रहता है, प्रदर्शन से समझौता किए बिना।

मुख्य निष्कर्ष

यदि आपकी मैट्रिक्स ऊपरी-त्रिकोणीय है, तो numpy.linalg.eig को सीधे कॉल करें और वही त्रिकोणीय डेटा पास करें। हर eigenvalue के लिए अलग-अलग हल निकालकर समय बर्बाद न करें। यह भी याद रखें कि त्रिकोणीय होना, विकर्णीकरण-योग्य होने की गारंटी नहीं देता; उदाहरण [[1, 1], [0, 1]] दिखाता है कि भले ही eigenvalues विकर्ण से आसानी से पढ़ी जा सकती हों, विकर्णीकरण फिर भी असंभव हो सकता है। और यदि आप Python से strevc3_ जोड़ने की सोच रहे थे, तो ध्यान दें कि रूटीन भीतर मौजूद है, लेकिन NumPy या SciPy में इसके लिए कोई सीधा सार्वजनिक रैपर नहीं है।