Я работаю над разделением разреженного графика, который у меня есть, и пока я доволен результатами, которые я видел, в настоящее время он слишком медленный. График имеет около 200 000 узлов, а scipy.sparse.linalg.eigsh занимает порядка часов. Я пробовал использовать режим смены-инвертирования и различные инициализации, а также линейный спектральный сдвиг, но для моего i7-4770k все еще требуется много часов. Существуют ли какие-либо трюки для инициализации или альтернативные алгоритмы, которые быстрее подходят для разреженных графиков определенной структуры?Выполнение спектрального разделения графиков в Python?
Часть моей надежды на это улучшение по производительности является то, что NVIDIA имеет тесты для некоторых из их GPU подходит для подобных графиков, работающих в порядке секунд: https://devblogs.nvidia.com/parallelforall/fast-spectral-graph-partitioning-gpus/
Конечно, это на GPU, а не на CPU, как у меня сейчас, но это кажется огромным пробелом для чего-то, что не является особенно параллелизуемым (матрично-векторные продукты). Может быть, это все, что есть, но я пытаюсь избежать добавления зависимости GPU на данный момент, но могу, если это то, что нужно.
Я скажу, что я пытаюсь использовать scipy.sparse.linalg.lobpcg с некоторыми предварительными условиями - надеюсь, это и делает трюк. – Michael
Это хороший и довольно технический вопрос (по крайней мере, по сравнению с другими на SO), который может быть более уместным @ [это место] (http://scicomp.stackexchange.com/). Но сначала проверьте правила вопроса, и перекрестная проводка может быть запрещена, поэтому, возможно, потребуется перенастройка модератором. – sascha
Вы пытались вызвать 'scipy.sparse.linalg.eigsh' (ARPACK) с необязательным аргументом' which = 'SA''? Полагаю, вы только пытаетесь получить наименьшие «k» собственные значения/векторы лапласианной матрицы графа, и этот вариант лучше использует его симметрию и тот факт, что ее собственные значения являются вещественными и неотрицательными. Вы можете найти варианты решателя [здесь] (https://docs.scipy.org/doc/scipy-0.18.1/reference/tutorial/arpack.html) – dafinguzman