मैटलैब एक स्पैर मैट्रिक्स कैसे ट्रांसफर करता है?

Question

मैं थोड़ी देर के लिए इस प्रश्न के बारे में सोच रहा हूं लेकिन संदर्भ नहीं मिल रहा है: मैटलैब एक स्पैर मैट्रिक्स को इतनी तेजी से कैसे स्थानांतरित करता है, यह देखते हुए कि यह सीएससी (संपीड़ित स्पैस कॉलम) प्रारूप में संग्रहीत है?

इसके अलावा its documentation विरल मैट्रिक्स स्थानांतरण की दक्षता की पुष्टि करता है:

इस (पंक्ति द्वारा तक पहुँचने पंक्ति) करने के लिए, आप मैट्रिक्स स्थानांतरित कर सकते हैं, स्तंभों पर कार्रवाई करने, और उसके बाद परिणाम retranspose ... समय मैट्रिक्स को स्थानांतरित करने के लिए आवश्यक नगण्य है।

फ़ॉलो-अप (के रूप में @Mikhail ने सुझाव दिया संशोधित):

मैं @Roger और @Milhail साथ सहमत हैं कि एक ध्वज की स्थापना के मामले में इस तरह के BLAS या विरल BLAS संचालन के रूप में कई कार्यों के लिए पर्याप्त है उनके इंटरफेस। लेकिन मुझे ऐसा लगता है कि मैटलैब "वास्तविक" पारदर्शिता करता है। उदाहरण के लिए, मैं के साथ आकार मीटर * एन = 7984 * 12411 एक विरल मैट्रिक्स एक्स है, और मुझे प्रत्येक स्तंभ और प्रत्येक पंक्ति पैमाने पर करने के हैं:

% scaling each column 
t = 0; 
for i = 1 : 1000 
    A = X; t0 = tic; 
    A = bsxfun(@times, A, rand(1,n)); 
    t = t + toc(t0); 
end 

टी = 0.०,२३,६३६ सेकंड

% scaling each row 
t = 0; 
for i = 1 : 1000 
    A = X; t0 = tic; 
    A = bsxfun(@times, A, rand(m,1)); 
    t = t + toc(t0); 
end 

टी = 138.3586 सेकंड

% scaling each row by transposing X and transforming back 
t = 0; 
for i = 1 : 1000 
    A = X; t0 = tic; 
    A = A'; A = bsxfun(@times, A, rand(1,m)); A = A'; 
    t = t + toc(t0); 
end 

टी = 19.5433 सेकंड

इस परिणाम का मतलब है कि स्तंभ से स्तंभ तक पहुँचने की तुलना में तेजी है पंक्ति से पंक्ति का उपयोग करना। यह समझ में आता है क्योंकि स्पैर मैट्रिस कॉलम द्वारा कॉलम संग्रहीत किया जाता है। तो एक्स 'के कॉलम स्केलिंग की तेज़ गति के लिए एकमात्र कारण यह होना चाहिए कि एक्स को वास्तव में ध्वज स्थापित करने के बजाय एक्स को स्थानांतरित किया जाना चाहिए।

इसके अलावा, यदि प्रत्येक स्पैर मैट्रिक्स सीएससी प्रारूप में संग्रहीत है, तो बस ध्वज सेट करने से एक्स 'सीएससी प्रारूप में नहीं हो सकता है।

कोई टिप्पणी? अग्रिम में धन्यवाद।

Answer 1

मैं रोजर रोवलैंड ने टिप्पणियों में क्या उल्लेख किया है उससे सहमत हूं। इस सुझाव को ग्राउंड करने के लिए आप बीएलएएस इंटरफेस से कुछ फ़ंक्शन देख सकते हैं, जो मैटलैब मैट्रिक्स ऑपरेशंस के लिए उपयोग करता है। मुझे यकीन नहीं है कि यह किस कार्यान्वयन का उपयोग करता है, लेकिन चूंकि वे छवि हैंडलिंग के लिए इंटेल आईपीपी का उपयोग करते हैं, मुझे लगता है कि वे मैट्रिक्स परिचालन को तेजी से बनाने के लिए इंटेल एमकेएल का भी उपयोग कर सकते हैं।

और यहां mkl_?cscsv फ़ंक्शन के लिए प्रलेखन है, जो सीएससी प्रारूप में एक स्पैर मैट्रिक्स के लिए रैखिक समीकरणों की एक प्रणाली को हल करता है। transa इनपुट ध्वज नोट करें, जो स्पष्ट रूप से परिभाषित करता है कि प्रदान किए गए मैट्रिक्स को ट्रांसपोज़ड के रूप में माना जाना चाहिए या नहीं।

Answer 2

एक हफ्ते की खोज के बाद, मैट्रिक्स को ट्रांसपोज़ करने की आंतरिक तंत्र के बारे में मेरा अनुमान सॉर्टिंग है।

मान लीजिए A, एक विरल मैट्रिक्स है

[I, J, S] = find(A); 
[sorted_I, idx] = sort(I); 
J = J(idx); 
S = S(idx); 
B = sparse(J, sorted_I, S); 

फिर BA की पक्षांतरित है।

उपरोक्त कार्यान्वयन में मेरी मशीन पर मैटलैब के अंतर्निहित transpose की लगभग आधा दक्षता है।Matlab के अंतर्निर्मित कार्यों को ध्यान में रखते हुए बहु-थ्रेडेड हैं, मेरा अनुमान उचित हो सकता है।

Answer 3

मुझे एहसास है कि मुझे खेल में थोड़ा देर हो चुकी है, लेकिन मैंने सोचा कि मैं इस सवाल पर कुछ प्रकाश डालने में मदद कर सकता हूं। एक स्पैर मैट्रिक्स का स्थानांतरण वास्तव में एक सीधा काम है जिसे इनपुट मैट्रिक्स में nonzero तत्वों की संख्या के आनुपातिक समय में पूरा किया जा सकता है। मान लीजिए कि एक एक MXN सीएससी प्रारूप, यानी में संग्रहीत मैट्रिक्स है, एक तीन सरणियों द्वारा परिभाषित किया गया है:

1. elemsA, लंबाई nnz (ए), कि, एक
2. prowA में अशून्य तत्व संग्रहीत करता लंबाई की की nnz (ए), जो
3. पीओएलएए, लंबाई एन + 1 में गैर-शून्य तत्वों के पंक्ति सूचकांक को संग्रहीत करता है, जैसे कि ए के कॉलम जे में सभी nonzero तत्वों को श्रेणी [pcola (j), pcola (j + 1))

यदि बी ए के हस्तांतरण को इंगित करता है, तो हमारा लक्ष्य समेकित सरणी elemsB, prowb, pcolb को परिभाषित करना है। ऐसा करने के लिए, हम इस तथ्य का उपयोग करते हैं कि ए की पंक्तियां बी के कॉलम बनाती हैं। Tmp को एक सरणी दें जैसे कि tmp (1) = 0 और tmp (i + 1) ए के पंक्ति I में तत्वों की संख्या है मैं = 1, ..., एम। फिर यह इस प्रकार है कि टीएमपी (i + 1) बी के कॉलम i में तत्वों की संख्या है। इसलिए, टीएमपी का संचयी योग पीएलसीबी जैसा ही है। अब मान लीजिए कि टीएमपी को इसके संचयी योग से अधिलेखित किया गया है। तब elemsB और prowB रूप

for j = 1,...,n 
     for k = pcolA(j),...,pcolA(j + 1) - 1 
      prowB(tmp(prowA(k))) = j 
      elemsB(tmp(prowA(k))) = elemsA(k) 
      tmp(prowA(k)) = tmp(prowA(k)) + 1 
     end 
    end 

इस प्रकार है जब एक नया तत्व जोड़ सरणी tmp prowB और elemsB में सूचकांक के लिए प्रयोग किया जाता है और फिर उसके अनुसार अद्यतन किया जाता है से भरा जा सकता। इस पूरी तरह लाना, हम सी में एक MEX फ़ाइल ++ कि पक्षांतरित एल्गोरिथ्म को लागू करता है लिख सकते हैं:

#include "mex.h" 
#include <vector> 
void mexFunction(int nlhs, mxArray *plhs[], int nrhs, const mxArray *prhs[]) {  
    // check input output 
    if (nrhs != 1) 
     mexErrMsgTxt("One input argument required"); 
    if (nlhs > 1) 
     mexErrMsgTxt("Too many output arguments"); 

    // get input sparse matrix A 
    if (mxIsEmpty(prhs[0])) { // is A empty? 
     plhs[0] = mxCreateSparse(0, 0, 0, mxREAL); 
     return; 
    } 
    if (!mxIsSparse(prhs[0]) || mxIsComplex(prhs[0])) // is A real and sparse? 
     mexErrMsgTxt("Input matrix must be real and sparse"); 
    double* A = mxGetPr(prhs[0]);   // real vector for A 
    mwIndex* prowA = mxGetIr(prhs[0]);  // row indices for elements of A 
    mwIndex* pcolindexA = mxGetJc(prhs[0]); // index into the columns 
    mwSize M = mxGetM(prhs[0]);    // number of rows in A 
    mwSize N = mxGetN(prhs[0]);    // number of columns in A 

    // allocate memory for A^T 
    plhs[0] = mxCreateSparse(N, M, pcolindexA[N], mxREAL); 
    double* outAt = mxGetPr(plhs[0]); 
    mwIndex* outprowAt = mxGetIr(plhs[0]); 
    mwIndex* outpcolindexAt = mxGetJc(plhs[0]); 

    // temp[j + 1] stores the number of nonzero elements in row j of A 
    std::vector<mwSize> temp(M + 1, 0); 
    for(mwIndex i = 0; i != N; ++i) { 
     for(mwIndex j = pcolindexA[i]; j < pcolindexA[i + 1]; ++j) 
      ++temp[prowA[j] + 1]; 
    } 
    outpcolindexAt[0] = 0; 
    for(mwIndex i = 1; i <= M; ++i) { 
     outpcolindexAt[i] = outpcolindexAt[i - 1] + temp[i]; 
     temp[i] = outpcolindexAt[i]; 
    } 
    for(mwIndex i = 0; i != N; ++i) { 
     for(mwIndex j = pcolindexA[i]; j < pcolindexA[i + 1]; ++j) { 
      outprowAt[temp[prowA[j]]] = i; 
      outAt[temp[prowA[j]]++] = A[j]; 
     } 
    } 
} 

पक्षांतरित की मैटलैब के कार्यान्वयन के साथ इस एल्गोरिथ्म की तुलना करना, हम इसी तरह के निष्पादन समय का निरीक्षण। ध्यान दें कि इस एल्गोरिदम को अस्थायी सरणी को खत्म करने के लिए एक सीधा तरीके से संशोधित किया जा सकता है।