Quanto è costoso calcolare gli autovalori di una matrice?

Question

Quanto è costoso calcolare gli autovalori di una matrice?

Qual è la complessità dei migliori algoritmi?

Quanto tempo è necessario in pratica se ho una matrice 1000 x 1000? Suppongo che aiuti se la matrice è scarsa?

Esistono casi in cui il calcolo degli autovalori non si interrompe?

In R, posso calcolare gli autovalori come nel seguente esempio giocattolo:

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

Qualcuno sa cosa algoritmo che utilizza?

Esistono altri pacchetti (open source) che calcolano l'autovalore?

Answer 1

Vorrei dare un'occhiata a Eigenvalue algorithms, che collegano a un numero di metodi diversi. Avranno tutti caratteristiche diverse e, si spera, uno sarà adatto ai tuoi scopi.

Answer 2

Suppongo che sia d'aiuto se la matrice è sparsa?

Sì, ci sono algoritmi, che funzionano bene su matrici sparse.

veda ad esempio: http://www.cise.ufl.edu/research/sparse/

Answer 3

maggior parte degli algoritmi di calcolo eigen valore scalare a grande-Oh (n^3), dove n è la dimensione della riga/colle della matrice (simmetrica e quadrato).

Per conoscere la complessità temporale dell'algoritmo migliore fino alla data, è necessario fare riferimento agli ultimi articoli di ricerca in Scientific Computing/Numerical Methods.

Ma anche se si presuppone il caso peggiore, occorrerebbero comunque almeno 1000^3 operazioni per una matrice 1000x1000.

R utilizza l'implementazione della routine LAPACK (DSYEVR, DGEEV, ZHEEV e ZGEEV) per impostazione predefinita. Tuttavia, è possibile specificare EISPACK = TRUE come parametro per utilizzare le routine RS, RG, CH e CG di EISPACK.

I pacchetti open source più popolari e validi per il calcolo degli autovalori sono LAPACK ed EISPACK.

Answer 4

Quanto tempo ci vuole in pratica se ho una matrice 1000x1000?

MATLAB (basato su LAPACK) calcola su una macchina dual-core a 1,83 GHz tutti gli autovalori di un 1000x1000 casuale in circa 5 secondi. Quando la matrice è simmetrica, il calcolo può essere eseguito molto più velocemente e richiede solo circa 1 secondo.

Answer 5

Con le matrici grandi di solito non si vogliono tutti gli autovalori. Vuoi solo i pochi migliori per fare (diciamo) una riduzione delle dimensioni.

L'algoritmo canonica è l'algoritmo iterativo Arnoldi-Lanczos implementato in ARPACK:

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

C'è un'interfaccia MATLAB in GIE:

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. 

E ora c'è un'interfaccia R pure:

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

Answer 6

Apache Mahout è un framework open-source costruito sulla cartina-ridurre (cioè funziona per matrici davvero molto grandi). Si noti che per un sacco di materiale a matrice la domanda non è "qual è il runtime di grandi dimensioni", ma piuttosto "quanto è parallelizzabile?" Mahout says usano Lanczos, che può essere essenzialmente eseguito in parallelo su tutti i processori che ti interessano.

Answer 7

Utilizza il QR algo. Vedi Wilkinson, J. H. (1965) The Algebraic Eigenvalue Problem. Clarendon Press, Oxford. Non sfrutta la scarsità.