Самый быстрый способ вычисления собственных значений больших матриц

До сих пор я использовал numpy.linalg.eigval для вычисления собственных значений квадратичных матриц не менее чем с 1000 строк / столбцов и, в большинстве случаев, примерно пятая часть его записей ненулевые (я не знаю, следует ли это считать разреженная матрица). Я нашел еще одну тему, указывающую, что scipy может возможно, сделай лучше.

Однако, поскольку мне нужно вычислить собственные значения для сотен тысяч больших матриц увеличивающегося размера (возможно, до 20000 строк / столбцов и да, мне нужны ВСЕ их собственные значения), это всегда займет очень много времени. Если я смогу ускорить процесс, даже самый крошечный, это, скорее всего, того стоит.

Итак, мой вопрос: есть ли более быстрый способ вычислить собственные значения, если не ограничиваться питоном?


python performance sparse-matrix adjacency-matrix eigenvalue
person alice    schedule 04.07.2013    source источник
comment
Если python не является обязательным, тогда любой другой язык более низкого уровня (C ++ / даже C #) даст вам прирост скорости. Только вопрос подходящей реализации.   -  person ZorleQ    schedule 04.07.2013
comment
Что бы вы ни делали, помните, что большая часть numpy - это дружественная к Python оболочка для функций, написанных на таких языках, как C, Fortran, ассемблер. Из документации я вижу, что numpy.linalg.eigvals я оболочка для функций в библиотеке LINPACK. Это не означает, что вы не можете найти более быстрые решатели, но вам, возможно, придется выйти за рамки numpy, scipy и LAPACK, чтобы найти их.   -  person High Performance Mark    schedule 04.07.2013
comment
Вы используете итерационные методы? Если да, может быть, вы можете их распараллелить?   -  person Darek    schedule 25.07.2013

Ответы (2)


arrow_upward
5
arrow_downward

@HighPerformanceMark верен в комментариях, поскольку алгоритмы, лежащие в основе numpy (LAPACK и т.п.), являются одними из лучших, но, возможно, не самых современных численных алгоритмов для диагонализации полных матриц. Однако вы можете существенно ускорить процесс, если у вас есть:

Разреженные матрицы

Если ваша матрица разреженная, то есть количество заполненных записей равно k, таково, что k<<N**2, тогда вам следует посмотреть _ 2_.

Ленточные матрицы

Существует множество алгоритмов работы с матрицами определенной полосатой структуры. Ознакомьтесь с решателями в scipy.linalg.solve.banded.

Наибольшие собственные значения

В большинстве случаев вам действительно не нужны все собственные значения. Фактически, большая часть физической информации поступает из самых больших собственных значений, а остальная часть представляет собой просто высокочастотные колебания, которые являются временными. В этом случае вам следует изучить решения для собственных значений, которые быстро сходятся к самым большим собственным значениям / векторам, такие как алгоритм Ланцоша .

person Hooked    schedule 25.07.2013
comment
OP явно говорит, что им нужны все собственные значения и что матрицы примерно на 80% разрежены. Я не знаю, достаточно ли 80% разреженности для алгоритмов разреженных собственных значений, чтобы превзойти плотные алгоритмы, но попробовать стоит. - person Danica; 25.07.2013
comment
@Dougal Я знаю, что он думает, что ему нужны все собственные значения, но я узнал, что часто можно сделать отличное приближение только с самыми большими собственными значениями (по очевидным причинам!). Алгоритмы Ланкоша в конечном итоге сходятся к все меньшим и меньшим собственным значениям, и эта информация определенно лучше, чем отсутствие собственных значений вообще! - person Hooked; 25.07.2013
comment
Да, извините, я слишком быстро прочитал этот раздел вашего ответа и предположил, что вы действительно не читали вопрос - извините. :) Но замечание: имя пользователя alice и местоимение он обычно не сочетаются. Наверное, лучше придерживаться гендерно-нейтрального единственного числа они. - person Danica; 25.07.2013
comment
@Dougal, кто я такой, чтобы указывать пол в имени пользователя? Однако я думаю, что OP - подходящее местоимение для всех quieres Stack Exchange. Может быть, хороший вопрос для english.stackexchange.com? - person Hooked; 25.07.2013

arrow_upward
1
arrow_downward

Простой способ получить приличное ускорение без изменения кода (особенно на многоядерной машине) - это связать numpy с более быстрой библиотекой линейной алгебры, такой как MKL, ACML или OpenBLAS. Если вы связаны с академическим учреждением, отличный дистрибутив python Anaconda позволит вам легко подключиться к MKL для бесплатно; в противном случае вы можете выложить 30 долларов (в этом случае вам следует сначала попробовать 30-дневную пробную версию оптимизации) или сделай сам (слегка раздражающий процесс, но определенно выполнимый).

Тем не менее, я бы определенно попробовал решить проблему с разреженными собственными значениями.

person Danica    schedule 25.07.2013