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()
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