Numpy 'smart' symmetric matrix

Question

क्या कोई स्मार्ट और स्पेस-कुशल सममित मैट्रिक्स numpy में है जो स्वचालित रूप से (और पारदर्शी रूप से) [j][i] पर स्थिति भरता है जब [i][j] लिखा जाता है?

import numpy 
a = numpy.symmetric((3, 3)) 
a[0][1] = 1 
a[1][0] == a[0][1] 
# True 
print(a) 
# [[0 1 0], [1 0 0], [0 0 0]] 

assert numpy.all(a == a.T) # for any symmetric matrix 

एक स्वचालित Hermitian भी अच्छा होगा, हालांकि मुझे लिखने के समय इसकी आवश्यकता नहीं होगी।

Answer 1

तुम सिर्फ गणना करने से पहले मैट्रिक्स सुडौल बनाना करने के लिए खर्च कर सकते हैं, तो निम्न यथोचित तेजी से किया जाना चाहिए:

def symmetrize(a): 
    return a + a.T - numpy.diag(a.diagonal()) 

इस तरह के symmetrize चलाने से पहले दोनों a[0, 1] = 42 और विरोधाभासी a[1, 0] = 123 नहीं कर के रूप में उचित मान्यताओं (तहत काम करता है)।

तुम सच में एक पारदर्शी समभागीकरण की जरूरत है, तो आप numpy.ndarray उपवर्गीकरण और बस __setitem__ को पुनर्परिभाषित करने की सोच सकते हैं:

class SymNDArray(numpy.ndarray): 
    def __setitem__(self, (i, j), value): 
     super(SymNDArray, self).__setitem__((i, j), value)      
     super(SymNDArray, self).__setitem__((j, i), value)      

def symarray(input_array): 
    """ 
    Returns a symmetrized version of the array-like input_array. 
    Further assignments to the array are automatically symmetrized. 
    """ 
    return symmetrize(numpy.asarray(input_array)).view(SymNDArray) 

# Example: 
a = symarray(numpy.zeros((3, 3))) 
a[0, 1] = 42 
print a # a[1, 0] == 42 too! 

(या सरणियों के बजाय मैट्रिक्स के साथ बराबर है, अपनी आवश्यकताओं के आधार पर)। यह दृष्टिकोण a[:, 1] = -1 जैसे अधिक जटिल असाइनमेंट को भी संभालता है, जो a[1, :] तत्वों को सही ढंग से सेट करता है।

ध्यान दें कि अजगर 3, इसलिए कोड थोड़ा अजगर 3 के साथ चलाने से पहले अनुकूलित किया जाना है def …(…, (i, j),…) लेखन की संभावना हटाया: def __setitem__(self, indexes, value): (i, j) = indexes ...

Answer 2

numpy में सममित मैट्रिक्स के इष्टतम उपचार के अधिक सामान्य मुद्दा मुझे भी bugged ।

इसे देखने के बाद, मुझे लगता है कि उत्तर शायद यह है कि समरूप कुछ समरूप मैट्रिक्स के लिए अंतर्निहित बीएलएएस रूटीन द्वारा समर्थित स्मृति लेआउट द्वारा बाधित है।

जबकि कुछ बीएलएएस दिनचर्या सममित मैट्रिक्स पर कंप्यूशन को गति देने के लिए समरूपता का फायदा उठाते हैं, फिर भी वे n(n+1)/2 के बजाय n^2 स्थान के समान स्मृति संरचना का उपयोग करते हैं। बस उन्हें बताया गया कि मैट्रिक्स सममित है और केवल ऊपरी या निचले त्रिकोण में मानों का उपयोग करना है।

scipy.linalg दिनचर्या में से कुछ झंडे स्वीकार करते हैं (जैसे linalg.solve पर sym_pos=True) जो DSYRK (सममित रैंक कश्मीर अद्यतन) की तरह दिनचर्या के लिए BLAS दिनचर्या को पारित करने के लिए, हालांकि numpy में इस के लिए और अधिक समर्थन अच्छा होगा, विशेष रूप से रैपर में , जो ग्राम मैट्रिक्स को डॉट (एमटी, एम) की तुलना में थोड़ा तेज गणना करने की अनुमति देगा।

(समय और/या अंतरिक्ष पर 2x निरंतर कारक के अनुकूलन के बारे में चिंता करने के लिए नाटकीय लग सकता है, लेकिन यह उस सीमा के लिए एक अंतर डाल सकता है कि आप एक मशीन पर कितनी बड़ी समस्या का प्रबंधन कर सकते हैं ...)

Answer 3

यह सादा अजगर और numpy नहीं है, लेकिन मैं सिर्फ एक साथ एक नियमित फेंक दिया एक सममित मैट्रिक्स (और एक परीक्षण कार्यक्रम यकीन है कि यह सही है) को भरने के लिए:

import random 

# fill a symmetric matrix with costs (i.e. m[x][y] == m[y][x] 
# For demonstration purposes, this routine connect each node to all the others 
# Since a matrix stores the costs, numbers are used to represent the nodes 
# so the row and column indices can represent nodes 

def fillCostMatrix(dim):  # square array of arrays 
    # Create zero matrix 
    new_square = [[0 for row in range(dim)] for col in range(dim)] 
    # fill in main diagonal 
    for v in range(0,dim): 
     new_square[v][v] = random.randrange(1,10) 

    # fill upper and lower triangles symmetrically by replicating diagonally 
    for v in range(1,dim): 
     iterations = dim - v 
     x = v 
     y = 0 
     while iterations > 0: 
      new_square[x][y] = new_square[y][x] = random.randrange(1,10) 
      x += 1 
      y += 1 
      iterations -= 1 
    return new_square 

# sanity test 
def test_symmetry(square): 
    dim = len(square[0]) 
    isSymmetric = '' 
    for x in range(0, dim): 
     for y in range(0, dim): 
      if square[x][y] != square[y][x]: 
       isSymmetric = 'NOT' 
    print "Matrix is", isSymmetric, "symmetric" 

def showSquare(square): 
    # Print out square matrix 
    columnHeader = ' ' 
    for i in range(len(square)): 
     columnHeader += ' ' + str(i) 
    print columnHeader 

    i = 0; 
    for col in square: 
     print i, col # print row number and data 
     i += 1 

def myMain(argv): 
    if len(argv) == 1: 
     nodeCount = 6 
    else: 
     try: 
      nodeCount = int(argv[1]) 
     except: 
      print "argument must be numeric" 
      quit() 

    # keep nodeCount <= 9 to keep the cost matrix pretty 
    costMatrix = fillCostMatrix(nodeCount) 
    print "Cost Matrix" 
    showSquare(costMatrix) 
    test_symmetry(costMatrix) # sanity test 
if __name__ == "__main__": 
    import sys 
    myMain(sys.argv) 

# vim:tabstop=8:shiftwidth=4:expandtab 

Answer 4

अच्छी तरह से की एक संख्या हैं सममित मैट्रिक्स को संग्रहीत करने के ज्ञात तरीके इसलिए उन्हें n^2 स्टोरेज तत्वों पर कब्जा करने की आवश्यकता नहीं है। इसके अलावा, भंडारण के इन संशोधित साधनों तक पहुंचने के लिए सामान्य संचालन को फिर से लिखना संभव है।निश्चित काम गोल्ब और वैन लोन है, मैट्रिक्स कम्प्यूटेशंस, तीसरा संस्करण 1 99 6, जॉन्स हॉपकिन्स यूनिवर्सिटी प्रेस, खंड 1.27-1.2.9। उदाहरण के लिए, उन्हें फॉर्म (1.2.2) से उद्धृत करते हुए, एक सममित मैट्रिक्स में केवल A = [a_{i,j} ] को i >= j के लिए स्टोर करने की आवश्यकता है। फिर, यह सोचते हैं वेक्टर मैट्रिक्स पकड़े वी निरूपित किया जाता है, और कहा कि एक एन-से-एन है,

V[(j-1)n - j(j-1)/2 + i] 

इसका मतलब यह है 1 अनुक्रमण में a_{i,j} डाल दिया।

गोल्ब और वैन लोन एक एल्गोरिदम 1.2.3 प्रदान करता है जो दिखाता है कि y = V x + y की गणना करने के लिए ऐसे संग्रहित वी तक कैसे पहुंचे।

गोलब और वैन लोन भी विकर्ण प्रभावशाली रूप में एक मैट्रिक्स संग्रहीत करने का एक तरीका प्रदान करते हैं। यह भंडारण को सहेजता नहीं है, लेकिन कुछ अन्य प्रकार के संचालन के लिए तैयार पहुंच का समर्थन करता है।

Answer 5

[i][j] में पाइथोनिक रूप से भरना मुश्किल है यदि [j][i] भरा हुआ है। भंडारण प्रश्न थोड़ा और दिलचस्प है। कोई packed विशेषता के साथ numpy सरणी वर्ग को बढ़ा सकता है जो भंडारण को बचाने और बाद में डेटा को पढ़ने के लिए उपयोगी होता है।

class Sym(np.ndarray): 

    # wrapper class for numpy array for symmetric matrices. New attribute can pack matrix to optimize storage. 
    # Usage: 
    # If you have a symmetric matrix A as a shape (n,n) numpy ndarray, Sym(A).packed is a shape (n(n+1)/2,) numpy array 
    # that is a packed version of A. To convert it back, just wrap the flat list in Sym(). Note that Sym(Sym(A).packed) 


    def __new__(cls, input_array): 
     obj = np.asarray(input_array).view(cls) 

     if len(obj.shape) == 1: 
      l = obj.copy() 
      p = obj.copy() 
      m = int((np.sqrt(8 * len(obj) + 1) - 1)/2) 
      sqrt_m = np.sqrt(m) 

      if np.isclose(sqrt_m, np.round(sqrt_m)): 
       A = np.zeros((m, m)) 
       for i in range(m): 
        A[i, i:] = l[:(m-i)] 
        A[i:, i] = l[:(m-i)] 
        l = l[(m-i):] 
       obj = np.asarray(A).view(cls) 
       obj.packed = p 

      else: 
       raise ValueError('One dimensional input length must be a triangular number.') 

     elif len(obj.shape) == 2: 
      if obj.shape[0] != obj.shape[1]: 
       raise ValueError('Two dimensional input must be a square matrix.') 
      packed_out = [] 
      for i in range(obj.shape[0]): 
       packed_out.append(obj[i, i:]) 
      obj.packed = np.concatenate(packed_out) 

     else: 
      raise ValueError('Input array must be 1 or 2 dimensional.') 

     return obj 

    def __array_finalize__(self, obj): 
     if obj is None: return 
     self.packed = getattr(obj, 'packed', None) 

`` `