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

Ответ 1

Большинство алгоритмов вычисления собственных значений масштабируются до больших-Oh (n ^ 3), где n - размер строки /col (симметричной и квадратной) матрицы.

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

Но даже если вы предполагаете худший случай, вам все равно потребуется по крайней мере 1000 ^ 3 операций для матрицы 1000x1000.

R использует по умолчанию процедуру LAPACK (DSYEVR, DGEEV, ZHEEV и ZGEEV). Однако вы можете указать EISPACK = TRUE в качестве параметра для использования процедур EISPACK RS, RG, CH и CG.

Наиболее популярными и хорошими пакетами с открытым исходным кодом для вычисления собственных значений являются LAPACK и EISPACK.

Ответ 2

С большими матрицами вам обычно не нужны все собственные значения. Вы просто хотите, чтобы топ-немногие сделали (скажем) уменьшение размера.

Канонический алгоритм - это итеративный алгоритм Арнольди-Ланцоса, реализованный в ARPACK:

www.caam.rice.edu/software/ARPACK/

В интерфейсе есть интерфейс matlab:

http://www.mathworks.com/access/helpdesk/help/techdoc/index.html?/access/helpdesk/help/techdoc/ref/eigs.html

eigs(A,k) and eigs(A,B,k) return the k largest magnitude eigenvalues.

И теперь есть интерфейс R:

http://igraph.sourceforge.net/doc-0.5/R/arpack.html

Ответ 3

Я предполагаю, что это помогает, если матрица разреженным?

Да, есть алгоритмы, которые хорошо работают на разреженных матрицах.

См. например: http://www.cise.ufl.edu/research/sparse/

Ответ 4

Сколько времени может потребоваться на практике, если У меня матрица 1000x1000?

MATLAB (на основе LAPACK) вычисляет на двухъядерном компьютере 1,83 ГГц все собственные значения 1000x1000 случайным образом примерно через 5 секунд. Когда матрица симметрична, вычисление может быть выполнено значительно быстрее и требуется всего около 1 секунды.

Ответ 5

Я бы рассмотрел алгоритмы собственных значений, которые ссылаются на несколько разных методов. Все они будут иметь разные характеристики, и, надеюсь, он будет подходящим для ваших целей.

Ответ 6

Apache Mahout - это фреймворк с открытым исходным кодом, построенный на map-reduce (т.е. он работает для действительно больших матриц). Обратите внимание, что для многих матричных материалов вопрос заключается не в том, "какова большая-во время выполнения", а скорее "насколько это возможно?". Mahout говорит, они используют Lanczos, которые могут быть запущены параллельно на столько процессоров, сколько вам нужно.

Ответ 7

Вы можете использовать пакет GuessCompx от CRAN, чтобы оценить эмпирическую сложность вычисления собственных значений и предсказать полное время выполнения (хотя оно все еще мало в вашем примере). Вам нужна небольшая вспомогательная функция, потому что процесс подбора только поднаборов строк, поэтому вы должны сделать матрицу квадратной:

library(GuessCompx)
m = matrix(rnorm(1e6), ncol=1000, nrow=1000)
# custom function  to subset the increasing-size matrix to a square one:
eigen. = function(m) eigen(as.matrix(m[, 1:nrow(m)]))
CompEst(m, eigen.)
#### $'TIME COMPLEXITY RESULTS'
#### $'TIME COMPLEXITY RESULTS'$best.model
#### [1] "CUBIC"
#### $'TIME COMPLEXITY RESULTS'$computation.time.on.full.dataset
#### [1] "5.23S"
#### $'TIME COMPLEXITY RESULTS'$p.value.model.significance
#### [1] 1.784406e-34

Вы получаете кубическую сложность для времени и сложность Nlog (N) для использования памяти функцией R base eigen(). На выполнение всех вычислений уходит 5,2 секунды и 37 МБ.

Ответ 8

Он использует QR-алгоритм. См. Wilkinson, J. H. (1965) Алгебраическая задача на собственные значения. Clarendon Press, Оксфорд. Он не использует разреженность.