Matematica Computazionale: Calcolo Parallelo

Paola Favati  

Conoscenze di algebra lineare numerica.

Il corso intende fornire le conoscenze fondamentali per l'analisi e sintesi di algoritmi paralleli numerici, con particolare riguardo al caso di parallelismo illimitato. La scelta degli argomenti è stata effettuata considerando sia l'importanza dei problemi trattati sia la significatività delle tecniche algoritmiche utilizzate.

Preliminari: Parallelismo illimitato e parallelismo limitato. Modelli di calcolo: DAG,PRAM, Network. Misure di complessità; tempo, lavoro, speedup. Algoritmi fondamentali:

• Somma di n numeri, prodotto matrice-vettore, prodotto di matrici.
• Cenni al problema dell'analisi dell'errore.
• Ricorrenze lineari (calcolo di un polinomio, fattorizzazione LU di matrici tridiagonali, risoluzione di sistemi triangolari a banda.

Algoritmi per sistemi lineari:

• Sistemi tridiagonali (Riduzione pari-dispari, fattorizzazione e raddoppiamento ricorsivo).
• Sistemi triangolari.
• Sistemi con matrici dense (Algoritmo di Csanky, fattorizzazione LU e QR, calcolo del rango).

Trasformata di Fourier e applicazioni:

• Trasformata veloce di Fourier in parallelo.
• Moltiplicazione di polinomi e convoluzione. Quoziente di polinomi.
• Interpolazione polinomiale.
• Matrici di Toeplitz (prodotto matrice di Toeplitz per vettore, inversione di
• matrici triangolari di Toeplitz, matrici Circolanti, matrici Toeplitz-like).

J. JaJa ``An introduction to Parallel Algorithms", Addison-Wesley Pu. Co., Reading, MA, 1992. Dongarra,Duff, Sorensen, van der Vorst ''Numerical Linear Algebra for High-Performance Computers'' Siam, 1998

Orale