Efficient way to create a sparse matrix

[Oskar Rasmusson]

Hi!

I'm trying to create a sparse matrix based on a pattern. I'm doing this using list comprehension and I was wondering if it could be done faster. 

The columns follow a pattern like (i is an integer)

{i}, {i, i + 17}, {i, i+17 , i + 17 + 17}, {i, i + 17, i + 17 + 17, i + 17 + 17 + 17},

But the pattern occurs twice, which means that the resulting list will look like

cols_index_temp = [i, i, i + 17, i, i + 17 , i + 34, i, i + 17, i + 34, i + 51, i, i, i + 17, i, i + 17 , i + 34, i, i + 17, i + 34, i + 51]

The rows follow pattern like (j is an integer)

{j} {j+1, j+1}, {j+2, j+2, j+2}, {j+3, j+3, j+3, j+3}

This pattern also occours twice but with a shift which means that the resulting list will look like

rows_index_temp = [j, j+1, j+1, j+2, j+2, j+2, j+3, j+3, j+3, j+3, j+shift, j+1+shift, j+1+shift, j+2+shift, j+2+shift, j+2+shift, j+3+shift, j+3+shift, j+3+shift, j+3+shift,

The elements is basically -1 and 1. It starts with -1 up intill the columns restarts it patterns which is the same time as the rows restarts it patterns but with a shift. So basically the first half of the length is -1 and second half is 1. So it would be

ones_temp = [-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 

                          1,  1,  1,  1,   1,  1,  1,  1,  1,  1]

Currently I'm doing this as

from cvxopt import spmatrix

numb_of_hours = 3
numb_prod_per_hour = 17
i = 2
j = 0

numb_of_ones = int(numb_of_hours*(numb_of_hours + 1)/2)
ones_temp = numb_of_ones * [-1]

cols_index_temp = [numb_prod_per_hour * x + i for b in range(numb_of_hours + 1) for x in range(b)]
arithemic_list = [k for k in range(numb_of_hours + 1)]
rows_index_temp = [item -1 + numb_of_hours * j * 2 for item, count in zip(arithemic_list, arithemic_list) for k in range(count)]
ones_temp += [1 for elem in ones_temp]
rows_index_temp += [numb_of_hours + elem for elem in rows_index_temp]
cols_index_temp += cols_index_temp

matrix = spmatrix(ones_temp, rows_index_temp, cols_index_temp)

When numb_of_hours is large (>4000) this takes some time. Any suggestion on how to improve it?

[Martin]

It looks like you're building the index lists row-by-row. This would be the ideal approach if the CVXOPT sparse matrix were based on "compressed row sparse" storage. However, the CVXOPT sparse matrices use "compressed column sparse" storage, and hence it is faster to construct a sparse matrix if the lists are ordered in a column-wise manner. Before you start rewriting your code, try changing the last line:

matrix = spmatrix(ones_temp, cols_index_temp, rows_index_temp).T