1

I have a list of columns and values for the Upper Triangle of a matrix, I would like to convert this to a symmetric matrix. For example, I have 

UpperTriangle = [[[0, 5], [6.0, 4.0]],
                 [[1, 3], [9.0, 6.0]],
                 [[2, 4, 6], [9.0, 6.0, 6.0]],
                 [[3], [4.0]],
                 [[4, 6], [4.0, 4.0]],
                 [[5], [2.6666666666666665]],
                 [[6], [4.0]]]

And I would like to convert it to 

Symmetric = [[[0, 5], [6.0, 4.0]],
             [[1, 3], [9.0, 6.0]],
             [[2, 4, 6], [9.0, 6.0, 6.0]],
             [[1, 3], [6.0, 4.0]],
             [[2, 4, 6], [6.0, 4.0, 4.0]],
             [[0, 5], [4.0, 2.6666666666666665]],
             [[2, 4, 6], [6.0, 4.0, 4.0]]]

The first list pertains to the first row of the matrix, the first list in the list gives column indices and the second list gives the values pertaining to the column indices. The second list pertains to the second row, and so forth. In the example above (row=0, column=0) has value 6.0, (row=0, column=5) has value 4.0, (row=1, column=1) has value 9.0, (row=1, column=3) has value 6.0.

One way to do this is by creating a numpy matrix, and then use the following to create a symmetric matrix.

W = np.maximum( A, A.transpose() )

But this is infeasible because the actual problem involves a matrix with 350,000 rows and columns, building a numpy matrix A takes up too much memory and transforming it takes too much time.

What would be the fastest Python way to transform the UpperTriangle to Symmetric without resorting to building a numpy matrix (using Python 2.7)? (within reasonable memory bounds).

The problem arose in the context of using IBM's Cplex Python API, where you need to insert a symmetric matrix to set the quadratic. 

import cplex
my_prob = cplex.Cplex()
my_prob.objective.set_quadratic(Symmetric)
my_prob.solve()
rkersh
  • 4,447
  • 2
  • 22
  • 31
user58925
  • 1,537
  • 5
  • 19
  • 28
  • Have you tried using [scipy.sparse.csr_matrix](https://docs.scipy.org/doc/scipy/reference/generated/scipy.sparse.csr_matrix.html)? Perhaps that combined with the answer to [this](https://stackoverflow.com/questions/2572916) stackoverflow question will suit your needs? – rkersh Sep 17 '18 at 22:08

1 Answers1

1

The CSR presentation of the input here is highly convenient. As you consider each row, you of course learn about a column of the symmetric matrix. When you reach each row, you already know the contents of all the columns omitted from its upper-triangular form. You even learn about those values in the order they appear in that row!

It’s then just a simple matter of programming:

def sym(up):        # alters 'up' in place
  pfx=[([],[]) for _ in up]  # to be added to each row
  for r,((cc,vv),(pc,pv)) in enumerate(zip(up,pfx)):
    for c,v in zip(cc,vv):
      if c>r:       # store off-diagonal for later row
        cr,cv=pfx[c]
        cr.append(r); cv.append(v)
    cc[:0]=pc; vv[:0]=pv     # prepend to preserve order
Davis Herring
  • 36,443
  • 4
  • 48
  • 76
  • This works well for me, but takes time. Is there a way to achieve the same thing. Perhaps at the cost of using more memory. In some cases I work with smaller matrix with plenty of memory to spare....Thanks – user58925 Sep 20 '18 at 13:27
  • @user58925: This algorithm visits each entry of the CSR input just once, creates the desired output structure directly, and allocates only as many lists as necessary. I’m not sure it can be made faster, even given license to use more memory. – Davis Herring Sep 20 '18 at 13:29
  • One more question, if I may. I see that using the sym function takes up considerable memory. I was under the impression that making a matrix symmetric would require at most twice as much memory as the original matrix (since the upper triangle already includes the diagonal). But using sym, the memory taken up by the matrix increases by more than 4 folds. Do you know why this happens? Perhaps because Python lists allocate extra space with append. Is there a way to avoid this problem? – user58925 Sep 20 '18 at 16:27