Нахождение наибольшего собственного значения огромной разреженной матрицы

Question

Я пытаюсь найти наибольшее собственное значение невероятно разреженной матрицы смежности.Я попытался использовать все доступные мне подходы:

mat = scipy.io.mmread(f)
mat = scipy.sparse.csr_matrix(mat)
G = nx.to_networkx_graph(mat)
mat = None

# compute largest eigenvalue
L = nx.normalized_laplacian_matrix(G)

# impl 1
e = numpy.linalg.eigvals(L.A)
# impl 2
e, _ = scipy.sparse.linalg.eigs(L.A, k=1, which='LA')
# impl 3
e, _ = scipy.sparse.linalg.eigs(L.A)

Все три из этих реализаций в какой-то момент сталкиваются с похожей ошибкой памяти:

 e, _ = scipy.sparse.linalg.eigs(L.A)
 File "/usr/lib64/python3.7/site-packages/scipy/sparse/base.py", line 674, in __getattr__
return self.toarray()
File "/usr/lib64/python3.7/site-packages/scipy/sparse/compressed.py", line 947, in toarray
out = self._process_toarray_args(order, out)
File "/usr/lib64/python3.7/site-packages/scipy/sparse/base.py", line 1184, in _process_toarray_args
return np.zeros(self.shape, dtype=self.dtype, order=order)
MemoryError
Uncaught exception. Entering post mortem debugging
Running 'cont' or 'step' will restart the program
> /usr/lib64/python3.7/site packages/scipy/sparse/base.py(1184)_process_toarray_args()
-> return np.zeros(self.shape, dtype=self.dtype, order=order)

(Pdb) print(self.shape)
(14259278, 14259278)

после попытки генерировать 1.6PBмассив numpy, предположительно для плотного представления матрицы.Ясно, что у меня нет памяти для этого.У меня довольно много (128 ГБ).Есть ли какая-то реализация или альтернатива, которая не требует генерации плотной матрицы?Это не обязательно должен быть Python.

Answer 1

Вместо использования networkx используйте scipy.sparse.csgraph.laplacian(..., normed=True).Как отметили другие, L.A дает вам плотный массив.

Answer 2

Единственная причина, по которой SciPy пытается создать плотное представление, заключается в том, что вы специально запросили его:

L.A

Прекратите это делать.scipy.sparse.linalg.eigs принимает разреженную матрицу.Вам не нужен плотный массив, который производит .A.Кроме того, 'LA' не является одним из допустимых значений which в документах;вы, вероятно, хотели 'LM' (по умолчанию).