Как рассчитать матрицу диагональных градусов из огромной (scipy.sparse) матрицы? - PullRequest
Новая
       5

Как рассчитать матрицу диагональных градусов из огромной (scipy.sparse) матрицы?

3 голосов
/ 18 января 2012

Учитывая квадратичную матрицу размером 1 миллион, я хочу вычислить матрицу диагональных градусов.

Матрица диагональных градусов определяется как диагональная матрица, в которой в качестве записей указано количество ненулевых значений на строку.

Матрица, назовем ее A в формате scipy.sparse.csr_matrix.

Если бы у моей машины было достаточно мощности, я бы просто сделал 

diagonal_degrees = []
for row in A:
    diagonal_degrees.append(numpy.sum(row!=0))

Я даже пробовал это, но это приводит к 

ValueError: array is too big.

Поэтому я попытался использовать разреженную структуру scipy. Я думал об этом так: 

diagonal_degrees = []
CSC_format = A.tocsc() # A is in scipys CSR format.
for i in range(CSC_format.shape[0]):
    row = CSC_format.getrow(i)
    diagonal_degrees.append(numpy.sum(row!=0))

У меня есть два вопроса:

  1. Есть ли более эффективный способ, возможно, я упустил из виду?
  2. Пока документы о скудном разреженном состоянии :

Все преобразования между форматами CSR, CSC и COO являются эффективными операциями с линейным временем.

Почему я получаю 

SparseEfficiencyWarning: changing the sparsity structure of a csr_matrix is expensive. lil_matrix is more efficient.

при переходе с CSR на CSC?

1 Ответ

4 голосов
/ 18 января 2012

Если все, что вам нужно - это подсчитать ненулевые элементы, есть метод nonzero, который может быть полезен.

Точный код будет (с помощью Джо Кингтон и matehat ): 

diag_deg, _ = np.histogram(x.nonzero()[0], np.arange(x.shape[0]+1))

# generating a diagonal matrix with diag_deg
dim = x.shape[0]
diag_mat = np.zeros((dim**2, ))
diag_mat[np.arange(0, dim**2, dim+1)] = diag_deg
diag_mat.reshape((dim, dim))

Хотя для больших массивов (dim ~ 1 million), как отмечают Aufwind , np.zeros((dim**2, )) даетисключение: ValueError: Maximum allowed dimension exceeded.Альтернативный обходной путь - использовать разреженные матрицы: 

diag_mat = sparse.coo_matrix((dim, dim))
diag_mat.setdiag(diag_deg)
...