From 3a31c785e3d487fc7e8e3c8b2c212d4e51864884 Mon Sep 17 00:00:00 2001 From: Leonardo Robol Date: Fri, 16 Oct 2009 12:55:33 +0200 Subject: [PATCH] Lezioni di Bini del 16 ottobre --- AppPageRank.tex | 107 +++++++++++++++++++++++++++++++++++++++++++++++-- CalcoloScientifico.tex | 18 +++++++++ 2 files changed, 121 insertions(+), 4 deletions(-) diff --git a/AppPageRank.tex b/AppPageRank.tex index 5510c2c..1654714 100644 --- a/AppPageRank.tex +++ b/AppPageRank.tex @@ -124,7 +124,8 @@ ed un autovettore (destro) a lui associato è quello composto di tutti $1$. La v Per rispondere alle domande~(\ref{en:pagerank:c}) e (\ref{en:pagerank:d}) ci appoggiamo ad un risultato che non dimostreremo (in questa sede) ottenuto da Perron-Frobenius sulla Teoria delle Matrici non negative. \begin{te}[di Perron-Frobenius] \label{te:PerronFrobenius} - Se $A$ è irriducibile allora $\rs{A} > 0$ è un autovalore semplice e esistono $x,y$ autovettori destro e sinistro + Se $A$ è irriducibile allora $\rs{A} > 0$ è un autovalore semplice ed + esistono $x,y$ autovettori destro e sinistro con componenti strettamente positive. \end{te} \begin{os} @@ -138,7 +139,12 @@ diversi da $1$ potrebbero ancora avere modulo $1$\footnote{Come visto nella teor del metodo di iterazione è data dal rapporto fra il più grande autovalore diverso da quello di cui si sta cercando l'autovettore e l'autovalore in questione. In questo caso il rapporto potrebbe essere $1$, che darebbe una situazione di non convergenza}. -Per superare questo problema si può, ancora una volta, modificare il modello. Consideriamo che il visitatore +Introduciamo una definizione che ci permetterà di formalizzare meglio il problema. +\begin{de} + Una matrice $A$ si dice \emph{ciclica} se esiste un sottoinsieme dei suoi autovalori $J \subseteq \spe{A}$ + tale che $\forall \lambda,\mu \in J$ si ha che $|\lambda|=|\mu|$. +\end{de} +Per superare questa difficoltà si può, ancora una volta, modificare il modello. Consideriamo che il visitatore possa in ogni pagina, con probabilità $1-\gamma$, decidere di aprire una pagina a caso. Potremmo rappresentare questa nuova situazione sostituendo $M$ con la matrice \[ @@ -148,8 +154,101 @@ questa nuova situazione sostituendo $M$ con la matrice 1 \end{array} \right] \left[ 1 \: \hdots \: 1 \right] \] -%% TODO: Spiegare meglio la condizione di ciclicità ovvero con una combinazione convessa della matrice $M$ con la matrice di soli $1$. Il valore di $\gamma$ si può scegliere a piacimento; Google usa un valore $\gamma = 0.85$. In questo caso la matrice $A$ non ha elementi nulli e quindi è irriducibile e non è ciclica\footnote{La condizione di ciclicità è quella che crea problemi -con gli autovalori di modulo uguale al raggio spettrale}. \ No newline at end of file +con gli autovalori di modulo uguale al raggio spettrale}. Possiamo infine utilizzare un'ultima versione del Teorema~\ref{te:PerronFrobenius} +che dice +\begin{te} + Sia $A$ una matrice con elementi strettamente positivi. Allora per ogni suo autovalore $\lambda \neq \rs{A}$ si ha + che vale la diseguaglianza $|\lambda| < |\rs{A}|$. +\end{te} +Quest'ultimo ci assicura la convergenza del nostro metodo. + +\subsection{Implementazione del metodo delle potenze} +Presenteremo in questa sezione una versione del metodo delle potenze adattata alle nostre esigenze. +Consideriamo la matrice $A$ di cui vogliamo trovare l'autovettore sinistro relativo all'autovalore $1$. +Sappiamo che esiste la forma di Jordan di $A$ ed in particolare una matrice $S$ tale che +\[ + S^{-1} A S = J \qquad J = \left[ \begin{array}{c|cc} + 1 & \multicolumn{2}{|c}{\herm{0}} \\ \hline + \multirow{2}{*}{$0$} & \sblocke{\hat J}{2} \\ + & & + \end{array} \right] +\] +Osserviamo ora che $e_1$ è autovettore destro di $J$ ed anche autovettore sinistro. Entrambi sono relativi +al'autovalore $1$. Sappiamo quindi che $e = Se_1$ è autovalore destro di $A$ e quindi è il vettore +con tutte le componenti uguali ad $1$, mentre $\trasp{w} = \trasp{e_1}S^{-1}$ è autovettore sinistro di $A$, +ovvero il vettore che stiamo cercando. +In particolare quanto visto nella precedente sezione ci assicura che $\rs{\hat J} < 1$ e quindi possiamo osservare +che +\[ + \lim_{k\to\infty} J^{k} = e_1\trasp{e_1} \quad \text{e quindi} \quad \lim_{k\to\infty} A^{k} = + \lim_{k\to\infty} SJ^kS^{-1} = Se_1 \trasp{e_1}S^{-1} = e\trasp{w} +\] +Questo (apparentemente) risolve il nostro problema in quanto $e\trasp{w}$ non è altro che la matrice le cui +righe coincidono con il vettore $\trasp{w}$ che è precisamente quanto stiamo cercando. \\ +La complessità di questo calcolo non è però trascurabile, in quanto la moltiplicazione di una matrice +costa in generale $O(n^3)$, decisamente troppo se $n \approx 10^{10}$ come nel nostro caso. +\begin{os} + Consideriamo dunque un vettore $x_0$ tale che $\trasp{e}x_0 = 1 = ||x_0||_{1}$, e definiamo la successione per ricorrenza + \[ + \left\{ \begin{array}{ll} + \trasp{x_0} & = \trasp{x_0} \\ + \trasp{x_{k+1}} & = \trasp{x_{k}} A + \end{array} \right. + \] +Possiamo notare che in generale $x_k = x_0 A^{k}$ e quindi data la nostra scelta oculata di $x_0$ abbiamo +che +\[ + \lim_{k\to\infty} \trasp{x_k} = \lim_{k\to\infty} \trasp{x_0} A^{k} = x_0 e \trasp{w} = \trasp{w} +\] +In questo modo siamo scesi da una complessità $O(n^3)$ ad una $O(n^2)$. +\end{os} +Sfortunatamente $O(n^2)$ nel nostro caso continua ad essere un numero troppo grande; arrivati a questo +punto ci possiamo rendere conto che possiamo sfruttare la particolarità di $A$, che non è assolutamente +una matrice qualsiasi! +%% TODO: QUalcosa di più sull'implementazione del metodo + +\subsection{Note tecniche} +Analizzato il problema matematicamente, sorge il bisogno di analizzare le difficoltà di implementazione dovute +all'hardware attualmente disponibile. Una matrice delle dimensioni di $A$ non è realmente memorizzabile +elemento per elemento su nessun calcolatore, e non è pensabile nemmeno in alcun tipo di cluster. \\ +Un rapido conto mostra come, anche ipotizzando di usare dei tipi \verb-float- a 4 byte (in ogni +caso presumibilmente troppo imprecisi) otteniamo uno spazio necessario di $N^2 \cdot 4$ byte, ovvero +circa $10^{20}$ byte = $10^{11}$ GB di RAM, probabilmente un quantitativo superiore a quella di tutti i computer +del mondo messi assieme\footnote{può darsi che nei prossimi anni quest'affermazione smetta di essere vera, ma +non penso sia rilevante ai fini del problema}. +Dobbiamo quindi adottare degli stratagemmi per gestire la memoria in modo efficiente. + +Una prima osservazione è che la nostra matrice $A$ si può scrivere nel seguente modo +\[ +A = \gamma D^{-1} \hat H + (1-\gamma) e\trasp{v} +\] +dove $\gamma$ e $w$ sono rispettivamente il parametro ed il vettore di personalizzazione. Per memorizzare +$A$ possiamo quindi memorizzare $D$ ed $\hat H$, $\gamma$ e $w$. \\ +Questo ci dà dei vantaggi perché la matrice $\hat H$ è ``quasi nulla'' nel senso che è fatta solamente di $0$ ed $1$, +ma la percentuale di $0$ è molto alta\footnote{è infatti presumibile che il numero di link uscenti da una pagina +sia trascurabile rispetto al numero di pagine esistenti}. Possiamo quindi limitarci a memorizzare i seguenti dati: \\[5pt] +\begin{tabular}{|lll|} \hline + \textbf{Variabile} & \textbf{Descrizione} & \textbf{Spazio occupato} \\ \hline \hline + $N$ & l'ordine della matrice $A$, ovvero il numero di pagine esistenti & 4 byte \\ + $m$ & il numero di campi di $\hat H$ diversi da $0$ & \textasciitilde $N$ byte \\ + $i, j$ & vettori delle coordinate dei campi diversi da $0$ di $\hat H$ & \textasciitilde $N$ byte \\ + $\gamma$ & coefficiente di personalizzazione & 4 byte \\ + $w$ & Vettore di personalizzazione & \textasciitilde $N$ byte \\ + $d$ & il vettore con gli elementi diagonali di $D$ & \textasciitilde $N$ byte \\ +\hline \end{tabular} \\ + +Possiamo ora porci il problema di calcolare $d$. Questo è reso apparentemente più complicato dal modo in cui abbiamo salvato +la matrice. In realtà possiamo usare un algoritmo di questo tipo + +\begin{lstlisting}[frame=tb,caption=Calcolo di $d$,label=lst:calcolovettorepers]{} + ! Inizializziamo il vettore d a 0 + d = 0; + ! Questo ciclo calcola i link uscenti da i per ogni i + DO k=1,m + d(i(k)) = d(i(k)) + 1 + END DO +\end{lstlisting} + diff --git a/CalcoloScientifico.tex b/CalcoloScientifico.tex index cfc468e..5b13d6d 100644 --- a/CalcoloScientifico.tex +++ b/CalcoloScientifico.tex @@ -23,6 +23,7 @@ \usepackage[a4paper]{geometry} \usepackage[T1]{fontenc} \usepackage{pxfonts} +\usepackage{listings} %% %% Ci piace, a causa del carattere usato (pxfonts) @@ -121,6 +122,23 @@ %% \newcommand{\PhC}{\makebox[0.45\width]{P}\raisebox{-0.35ex}{H}\makebox[0.58\width]{C}\makebox[0.5\width]{ }} +%% Codice fortran +\definecolor{listinggray}{gray}{0.95} +\lstset{language=fortran} +\lstset{backgroundcolor=\color{listinggray}} +\lstset{frameround=trbl} +\lstset{% general command to set parameter(s) + basicstyle=\small\ttfamily, % print whole listing small + keywordstyle=\color{black}\bfseries\underbar, + % underlined bold black keywords + identifierstyle=, % nothing happens + commentstyle=\color{red!80}, % white comments + stringstyle=\ttfamily, % typewriter type for strings + numbers=left, % numbers + numberstyle=\scriptsize, % che non rompano troppo + showstringspaces=false} % no special string spaces +% \lstset{keywordstyle=\color{red}\bfseries\underbar} + %% %% Definizioni di tutti i tipi di teoremi, osservazioni, -- 2.1.4