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 e 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 e 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
Quello che cerchi é la base numerica dell'algoritmo di pagerank di google. Trovi tutto quello che ti serve googlando un po' sulla chiave "metodi autovalori pagerank". Troverai dei metodi (ad esempio il metodo QR) standard per problemi agli autovalori di matrici grandi e sparse e alcune considerazioni specifiche sulla matrice del web che ha delle particolarità che vengono sfruttate dall'algoritmo di pagerank. Se poi non ti basta l'immensa letteratura che trovi in internet puoi provare con un testo di calcolo numerico ad esempio: "Bini-Capovani-Menchi--Metodi numerici per l'algebra lineare--Zanichelli" e forse anche sul Demmel o sul Watkins che al momento non ho con me e quindi non ne sono sicuro.
l'algoritmo di pagerank sembra non calcoli gli autovalori,ma a partire dalla matrice delle adiacenze e da un vettore calcoli direttamente il rank della pagine.
Sì, perchè il pagerank mira agli autovettori e non agli autovalori (tant'è che la matrice del web viene normalizzata rispetto al suo raggio spettrale).
Ti ho dato degli altri riferimenti, guarda su quelli, in particolare il metodo QR.
Ti ho dato degli altri riferimenti, guarda su quelli, in particolare il metodo QR.
Mi ha risposto un illustrissimo professore dell'università di milano che lavora laboratorio internazionale LAW e si occupa proprio di argomenti inerenti al web e mi ha detto che la cosa non si può fare. L'unica cosa fattibile è calcolarne alcunicon un eigensolver iterativo tipo ARPACK++ o simili (cerca implementazioni utilizzabili del metodo di Laczos con restart). Non è che abbia capito un granchè di quello che mi ha detto ma almeno adesso vedo una stella da seguire...
Ti dico la mia opinione, basata su quel pochissimo che so di calcolo numerico. Di metodi numerici per il calcolo di autovalori ed autovettori ce ne sono parecchi, ma proprio tanti eh. In genere si tratta di metodi iterativi (probabilmente è a questo che si riferisce il professorone con eigensolver iterativo): in parole povere questo genere di metodi fabbrica una successione convergente al risultato teorico, che approssima troncando la successione ad un passo abbastanza grande. Un metodo di questo tipo è quello QR che diceva Megan00b: nello specifico il metodo QR fabbrica una successione di matrici, tutte simili, convergente ad una matrice triangolare. Questa matrice avrà sulla diagonale principale tutti gli autovalori della matrice di partenza.
Quindi il metodo QR serve ad approssimare numericamente tutti gli autovalori di una matrice data. Ma non tutti i metodi sono così: alcuni calcolano solo un autovalore, ad esempio quello più grande in modulo. Se a te serve solo questo, ti conviene eccome cercare un metodo di questo tipo.
Il più semplice di tutti è sicuramente quello "delle potenze", facile da implementare. Di questo metodo, una variante studiata per funzionare bene con matrici sparse è quella di Lanczos. E molto probabilmente è questo metodo che ti ha consigliato il prof. Io non ne so più nulla, trovi i dettagli sul Bini-Capovani-Menchi che diceva anche Megan00b nel capitolo 6, paragrafo 13. Oppure in rete, sicuramente c'è materiale a tonnellate, occhio che sia affidabile.
Quindi il metodo QR serve ad approssimare numericamente tutti gli autovalori di una matrice data. Ma non tutti i metodi sono così: alcuni calcolano solo un autovalore, ad esempio quello più grande in modulo. Se a te serve solo questo, ti conviene eccome cercare un metodo di questo tipo.
Il più semplice di tutti è sicuramente quello "delle potenze", facile da implementare. Di questo metodo, una variante studiata per funzionare bene con matrici sparse è quella di Lanczos. E molto probabilmente è questo metodo che ti ha consigliato il prof. Io non ne so più nulla, trovi i dettagli sul Bini-Capovani-Menchi che diceva anche Megan00b nel capitolo 6, paragrafo 13. Oppure in rete, sicuramente c'è materiale a tonnellate, occhio che sia affidabile.
"Kukadott":
L'unica cosa fattibile è calcolarne alcunicon un eigensolver iterativo tipo ARPACK++ o simili (cerca implementazioni utilizzabili del metodo di Laczos con restart).
Sì ok, ma nella tua domanda chiedevi un software o un algoritmo?
un algoritmo... il problema è che con matrici non simmetriche ottengo degli autovalori complessi,giusto? se è così non so proprio che farmene
"Kukadott":
un algoritmo... il problema è che con matrici non simmetriche ottengo degli autovalori complessi,giusto? se è così non so proprio che farmene
Beh... questo si chiama essere catatrofisti...
$A=((1,,,,1),(,1,,,),(,,ddots,,),(,,,ddots,),(,,,,1))$ ovvero le matrici con diagonale 1 e tutta 0 tranne l'elemento (1,n).
Ti bastano questi infiniti controesempi?
Scua Megan00b ma cosa intendi dire? la mia è una matrice sparsa che rappresenta i link tra pagine del web!le pagine in esme sono circa 100 milioni
Volevo mostrarti che non è vero che una matrice non simmetrica ha necessariamente autovalori complessi.
Per il tuo problema ancora una volta ti rimando a quel libro che ti ha consigliato anche dissonance. Ci trovi tutto quello che ti serve. Poi ovviamente non ti aspettare che esista un metodo che in 5 secondi ti sforna gli autovalori. Su quel libro (o dove altro vuoi andare a vedere) ci troverai tutte le considerazioni opportune per valutare il metodo migliore per i tuoi scopi e per la matrice che devi trattare. Ti ho consigliato il QR perchè è probabilmente il migliore per problemi generici e a quanto ne so la matrice del web non presenta proprietà particolari che portano la scelta su altri metodi ma su questo posso sbagliarmi.
Buona lettura.
Per il tuo problema ancora una volta ti rimando a quel libro che ti ha consigliato anche dissonance. Ci trovi tutto quello che ti serve. Poi ovviamente non ti aspettare che esista un metodo che in 5 secondi ti sforna gli autovalori. Su quel libro (o dove altro vuoi andare a vedere) ci troverai tutte le considerazioni opportune per valutare il metodo migliore per i tuoi scopi e per la matrice che devi trattare. Ti ho consigliato il QR perchè è probabilmente il migliore per problemi generici e a quanto ne so la matrice del web non presenta proprietà particolari che portano la scelta su altri metodi ma su questo posso sbagliarmi.
Buona lettura.
ti ringrazio per il consiglio, ma da quello che mi hanno etto e che ho letto, il metodo QR non è applicabile in quanto non iterativo. I metodi iterativi sono gli unici capaci di gestire matrici di queste dimensioni. a quanto sembra potrei applicare Arnoldi in quanto la matrice non è simmetrica ma credo che per una matrice così grande sia molto facile che gli autovalori siano complessi.
Innanzitutto se non l'hanno cambiato nel frattempo il metodo QR è iterativo. Poi il fatto che gli autovalori siano complessi non dipende nè dalla simmetria nè dalla <> della matrice.
il problema della grandezza della matrice è solo nella manipolazione (spazio e tempo impiegati per le operazioni). Noto con piacere che sei molto più ferrata di me in materia,quindi ti chiedo: una matrice fatta come ti ho descritto(cioè di soli 0 e 1,sparsa e con tutti quegli elementi e con tutti gli lementi della diagonale a 0 in quanto non esistono link da una pagina a se stessa) è molto probabile che abbia autovalori complessi,vero?Grazie
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo