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

Question

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

В чем сложность лучших алгоритмов?

Сколько времени может потребоваться на практике, если у меня есть матрица 1000 x 1000? Я полагаю, это поможет, если матрица разрежена?

Есть ли случаи, когда вычисление собственного значения не прекращалось бы?

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

m<-matrix( c(13,2, 5,4), ncol=2, nrow=2 )
eigen(m, only.values=1)
$values
[1] 14  3

Кто-нибудь знает, какой алгоритм он использует?

Существуют ли другие (с открытым исходным кодом) пакеты, которые вычисляют собственное значение?

Answer 1

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

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

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

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

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

Answer 2

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

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

www.caam.rice.edu / Программное обеспечение / ARPACK /

В eigs есть интерфейс 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

Answer 3

Я полагаю, это помогает, если матрица редкий

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

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

Answer 4

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

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

Answer 5

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

Answer 6

Вы можете использовать пакет 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 МБ.

Answer 7

Apache Mahout - это фреймворк с открытым исходным кодом, построенный на Map-Reduce (т.е. он работает для действительно очень больших матриц). Заметьте, что для многих матричных задач вопрос не в том, «что такое среда выполнения big-o», а в том, насколько «параллелизуем»? Махоут говорит, что они используют Lanczos, который, по сути, может работать параллельно на любом количестве процессоров, сколько вы пожелаете.

Answer 8

Используется алгоритм QR. См. Уилкинсон, Дж. Х. (1965) Алгебраическая проблема собственных значений. Кларендон Пресс, Оксфорд. Он не использует разреженность.