From 42faac936b505da9479f3e46acc1c4acc52b748d Mon Sep 17 00:00:00 2001
From: Leonardo Robol <leo@robol.it>
Date: Fri, 23 Oct 2009 13:59:16 +0200
Subject: [PATCH] Lezione di Bini del 23 ottobre.

---
 AppPageRank.tex | 83 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 83 insertions(+)

diff --git a/AppPageRank.tex b/AppPageRank.tex
index 1654714..d805f39 100644
--- a/AppPageRank.tex
+++ b/AppPageRank.tex
@@ -252,3 +252,86 @@ la matrice. In realtà possiamo usare un algoritmo di questo tipo
  END DO
 \end{lstlisting}
 
+\section{Una prima implementazione}
+In questa sezione ci occuperemo di presentare una prima implementazione della soluzione al problema.
+Non ci preoccuperemo troppo di ottimizzare il codice, compito che affronteremo in seguito. 
+Esporremo inizialmente la struttura generale del programma e poi costruiremo tutte le subroutine necessarie.
+
+\subsection{La struttura}
+Il programma dovrà comporsi delle seguenti parti
+\begin{description}
+ \item[Lettura della matrice] Supporremo di avere un file da cui leggere i dati della matrice. Dobbiamo
+ definire la sintassi del file e scrivere un subroutine per caricarlo in memoria;
+ \item[Calcolo del vettore d] Data la matrice di connessione $H$ vorremo calcolare la somma di ogni
+ riga che ci servirà in seguito per rinormalizzare il vettore di iterazione;
+ \item[Iterazione] Generiamo un vettore $x$ casuale e lo riscaliamo in modo che $\trasp{e} x = 1$. Fatto
+ questo cominciamo a calcolare l'iterazione, fino a che l'errore non è piccolo o ragguingiamo il massimo
+ numero di iterazioni impostato;
+ \item[Salvataggio] Salviamo su un file il vettore calcolato;
+\end{description}
+
+Per questo avremo bisogno anche di alcune subroutine, ad esempio quella che ci calcoli il prodotto matrice
+vettore data la matrice sparsa come l'abbiamo intesa noi. 
+
+\subsection{Prodotto di matrice sparsa per un vettore}
+Esponiamo qui un'idea di codice per calcolare questo prodotto matrice vettore. Ricordiamo che per noi una
+matrice sparsa è composta di due scalari \lstinline-n-,\lstinline-m- (rispettivamente dimensione e numero di elementi diversi da $0$)
+e due vettori \lstinline-i-, \lstinline-j- di dimensione $m$ che sono le coordinate dei punti che valgono $1$.\\
+Il codice è il seguente
+\begin{lstlisting}[frame=tb,caption=Calcolo del prodotto matrice vettore,label=lst:matrixvec]
+ SUBROUTINE dotprod(n,m,i,j,d,x,v,y)
+  IMPLICIT NONE
+  ! Il parametro dp dei tipi a doppia precisione
+  INTEGER, PARAMETER :: dp = KIND(0.D0)
+
+  ! Dichiarazione degli argomenti della funzione
+  INTEGER, INTENT(IN) :: n,m
+  INTEGER, DIMENSION(m), INTENT(IN) :: i,j
+  INTEGER, DIMENSION(n), INTENT(IN) :: d
+  REAL(dp), DIMENSION(n), INTENT(IN) :: x, v
+
+  ! Dato di output
+  REAL(dp), DIMENSION(n) :: y
+
+  ! Alcune variabili di comodo
+  REAL(dp), DIMENSION(n) :: xx
+  REAL(dp) :: s, gamma = 0.85
+  INTEGER :: k
+
+  ! Calcoliamo x trasposto per la matrice D con i d(i) sulla
+  ! diagonale,  e salviamolo in xx, in modo da non modificare x
+  ! Ricordiamo che i dati in fortrano vengono sempre passati per
+  ! riferimento! Se modificassimo x qui dentro risulterebbe cambiato
+  ! anche all'esterno. 
+  DO k=1,m
+   IF(d(k)/=0) THEN 
+     xx(i(k)) = x(i(k))/d(k)
+   ELSE
+     xx(i(k)) = x(i(k))/n
+   END IF
+  END DO
+  
+  ! Ora eseguiamo la moltiplicazione di xx per la parte non dangling
+  ! della matrice H cappuccio e salviamo il risultato in y
+  y = 0.D0
+  DO k=1,m
+    y(j(k)) = y(j(k)) + xx(i(k))
+  END DO
+
+  ! Ora calcoliamo le righe dangling dalle quali prima non siamo "passati"
+  ! perche' i(k) scorre solo sulle righe dove ci sono elementi non nulli
+  DO k=1,n
+    IF(d(k) == 0)
+      s = s + xx(k)
+    END IF
+  END DO
+
+  ! Sommiamo i due contributi
+  y = y + s
+
+  ! Calcolo la personalizzazione
+  y = y * gamma + (1-gamma)
+
+ END SUBROUTINE dotprod
+\end{lstlisting}
+
-- 
2.1.4