Calcolo autovalori internet

[Kukadott]

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

[Megan00b]

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.

[Kukadott]

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.

[Megan00b]

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.

[Kukadott]

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...

[dissonance]

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.

[Megan00b]

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?

[Kukadott]

un algoritmo... il problema è che con matrici non simmetriche ottengo degli autovalori complessi,giusto? se è così non so proprio che farmene

[Megan00b]

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...
\( \displaystyle {A}={\left(\matrix{{1}&&&&{1}\\&{1}&&&\\&&\ddots&&\\&&&\ddots&\\&&&&{1}}\right)} \) ovvero le matrici con diagonale 1 e tutta 0 tranne l'elemento (1,n).
Ti bastano questi infiniti controesempi?

[Kukadott]

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