[Algoritmi]Calcolo autovalori internet
Ciao a tutti,
ho un piccolo problema...
Ho una matrice A nxn che rappresenta le adiacenze tra nodi di un grafo(quindi simmetrica con valori che posso essere 1 o 0). Devo calcolare gli autovalori A.
L'unico problema che ho è che la matrice rappresenta uno snapshot di internet, quindi n è circa 100 milioni.
Studiando un po',non ho mai avuto a che fare con cose così mostruose, ho capito che devo diagonalizzare A. Solo che non so proprio come procedere visto che l'unica modo che conosco per diagonalizzare è usando gli autovalori.
Grazie
ho un piccolo problema...
Ho una matrice A nxn che rappresenta le adiacenze tra nodi di un grafo(quindi simmetrica con valori che posso essere 1 o 0). Devo calcolare gli autovalori A.
L'unico problema che ho è che la matrice rappresenta uno snapshot di internet, quindi n è circa 100 milioni.
Studiando un po',non ho mai avuto a che fare con cose così mostruose, ho capito che devo diagonalizzare A. Solo che non so proprio come procedere visto che l'unica modo che conosco per diagonalizzare è usando gli autovalori.
Grazie
Risposte
sembra molto simile al caso Google...
Dai un occhio qui( http://www.google.com/url?sa=t&source=w ... lGFv29Qy1A )
Dai un occhio qui( http://www.google.com/url?sa=t&source=w ... lGFv29Qy1A )
avevo già dato un'occhiata a questo pdf. Ho capito come calcola il vettore r che rappresenta il page rank della pagina, ma non ho capito come risalire a tutti gli autovalori.a me servono quelli
un modo numerico è quello delle potenze..
Parti da un $x_0$ assegnato e poi ti crei una successione {$x^n$} tale che, al passo k-esimo, hai $x_k/||x_k|| = A^kx_0/||x_0||$.
Cosi però troveresti solo in più piccolo autovalore.
Oppure guardati la deflazione o delle potenze inverse(per il più grande autovalore).
Comunque, a livello numerico, il calcolo degli autovalori di matrici cosi grandi non è senza costo.
Ciao
P.S: ricorda che se A è simmetrica $lim_{k \to \infty} A^k$ è diagonale e nel caso generale $lim_{k \to \infty} A^k$ è triangolare superiore.
Parti da un $x_0$ assegnato e poi ti crei una successione {$x^n$} tale che, al passo k-esimo, hai $x_k/||x_k|| = A^kx_0/||x_0||$.
Cosi però troveresti solo in più piccolo autovalore.
Oppure guardati la deflazione o delle potenze inverse(per il più grande autovalore).
Comunque, a livello numerico, il calcolo degli autovalori di matrici cosi grandi non è senza costo.
Ciao
P.S: ricorda che se A è simmetrica $lim_{k \to \infty} A^k$ è diagonale e nel caso generale $lim_{k \to \infty} A^k$ è triangolare superiore.
però rileggendo il tuo testo forse ti va bene essendo simmetrica con soli 1/0...
mi sa che mi sono sbagliato...Essendo una matrice che rappresenta i link tra pagine del web,è composta solo da 0 e 1 ma non è simmetrica. Ottenere il più piccolo è punto grande autovalore non mi aiuta col mio problema. Devo calcolarli tutti:(
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo