Metodi paralleli waveform relaxation accelerati per equazioni integrali di Volterra

Obiettivo di questo lavoro di tesi è l'analisi e lo sviluppo di metodi paralleli rapidamente convergenti per la risoluzione di equazioni integrali di Volterra (VIEs) a grandi dimensioni. Sistemi di equazioni integrali di Volterra a grandi dimensioni traggono origine sia da una vasta area di applicazioni (ad esempio in Bioottica, Biologia, reazione-diffusione in piccole celle, etc.) si ottengono discretizzando rispetto alle variabili spaziali equazioni di tipo Fredholm-Volterra. Essi richiedono per un'efficiente risoluzione numerica metodi a parallelismo massiccio. Nella tesi sono stati, pertanto, presi in considerazione metodi iterativi Waveform Relaxation (WR) che realizzano un parallelismo massiccio lungo il sistema. I metodi WR formano una classe di metodi iterativi introdotti nel 1982 nell'ambito del design di circuiti integrati VLSI con metodi di circuit simulation. Essi sono stati introdotti per velocizzare il calcolo della soluzione del problema differenziale che modellizza il circuito integrato. L'efficienza dimostrata da tali metodi applicati a sistemi di equazioni differenziali (ODEs) a grandi dimensioni, ha spinto la ricerca verso lo studio di metodi WR per VIEs. L'idea generale dei metodi è la seguente: considerato un sistema di equazioni integrali di dimensione d e scelta una funzione G(t; s; u; v) tale che G(t; s; u; u) = k(t; s; u), dove k è il nucleo del sistema di VIEs, calcoliamo la sequenza di funzioni, chiamate waveforms, mediante la funzione G. Naturalmente, se la successione delle waveforms è convergente, il suo limite è la soluzione y(t) del sistema di VIEs. La scelta della funzione G è di notevole importanza, poichè influenza fortemente sia il costo di calcolo che la velocità di convergenza della successione delle waveform. Se la scelta di G è tale da permettere che il sistema venga decomposto in sottosistemi indipendenti (che possono così essere risolti in parallelo), allora otterremo un metodo WR parallelo. Metodi Waveform Relaxation pienamente paralleli sono il metodo WR di Picard, di Richardson e di Jacobi. Essi, però, sono anche caratterizzati da una lenta convergenza verso la soluzione. Per costruire metodi rapidamente convergenti ma ancora pienamente paralleli, nella tesi sono state analizzate alcune tecniche e formulati nuovi metodi basati sui tre appena citati. Dapprima, vengono presentati i metodi WR con Overlapping Splittings per sistemi di equazioni integrali di Volterra. L'idea base di tali metodi consiste nel decomporre il sistema di VIEs in sottosistemi in modo tale che alcune componenti del vettore soluzione compaiano in due o più sottosistemi. Ogni sottosistema è risolto con un procedimento iterativo. Per le componenti che figurano in più sottosistemi viene assunta come soluzione una media pesata dei valori forniti da ciascun sottosistema. Per quanto riguarda la convergenza dei metodi WR con Overlapping Splittings per sistemi di VIEs si è dimostrato che sono sempre convergenti in [0; T], analogamente ai metodi WR. Da una sperimentazione numerica effettuata, pur ottenendo in alcuni casi buone prestazioni in termini di velocità di convergenza, non si evidenziano, però, risultati che suggeriscano un percorso nella scelta dei vari parametri che intervengono nell'uso di questa tecnica. Un'analoga situazione si verifica nell'uso del WR con Overlapping Splittings per risolvere sistemi di equazioni differenziali. Ciò è stato confermato, attraverso una corrispondenza, dai professori K.Burrage e R.Pohl, anche se ciò non era stato evidenziato nei loro lavori. Successivamente, nella tesi, vengono presentati metodi WR con accelerazione di Chebyshev. Viene, dapprima, presentato il metodo WR Chebyshev di Picard per equazioni lineari con nucleo di convoluzione ottenuto utilizzando una tecnica già nota per le equazioni differenziali ordinarie. Tale tecnica fa ricorso all'uso della trasformata di Laplace per ridurre equazioni dinamiche in statiche: da equazioni differenziali o integrali a sistemi di equazioni lineari algebriche. La risoluzione con metodi iterativi di quest'ultime viene accelerata con la tecnica di accelerazione polinomiale di Chebyshev. Applicando l'antitrasformata di Laplace si ritorna ad equazioni dinamiche ottenendo un metodo accelerato. Poi, nella tesi, vengono sviluppati metodi WR di Richardson accelerati per equazioni con nucleo di convoluzione lineare, ottenuti introducendo una tecnica di accelerazione che fa ricorso a polinomi di Chebyshev aventi per argomento un operatore integrale. Si dimostra una maggiorazione dell'errore attraverso la quale si evince l'accelerazione del metodo, confermata anche da prove numeriche. Come caso particolare ritroviamo il metodo WR Chebyshev di Picard già ottenuto, nel caso del nucleo di convoluzione lineare, con la tecnica che fa ricorso alla trasformata di Laplace. Questa stessa tecnica viene, poi, estesa ad equazioni a nucleo debolmente singolare arrivando a formulare nuovi metodi WR accelerati per questo tipo di equazioni. Vengono, poi, presentati test effettuati su problemi con nucleo di convoluzione lineare utilizzando matrici con spettri a caratteristiche differenti. Tali test hanno confermato i risultati teorici precedentemente trovati. In particolare, per problemi con spettro di ampiezza piccola e lontano dall'origine il numero delle iterate necessarie per approssimare la soluzione con una tolleranza prefissata si è ridotto anche di un fattore 30. Infine, viene progettato e valutato un codice parallelo basato sul metodo WR di Picard con accelerazione di Chebyshev per equazioni con nucleo di convoluzione lineare. L'algoritmo progettato si basa sul metodo WR accelerato, utilizzando come metodo underlying un metodo Volterra Runge{Kutta (VRK) esplicito a quattro stadi di tipo Pouzet [Bru.VdH]. L'e±cienza dell'algoritmo è stata potenziata adattando il metodo VRK al particolare problema considerato. Il codice è stato progettato a passo fisso su un cluster di WorkStations IBM RISC/6000 del Dipartimento di Matematica ed Applicazioni, connesse con una rete di tipo ETHERNET. Al fine di ottenere un software di ampia portabilità il codice è stato scritto in linguaggio di programmazione Fortran 77, in ambiente operativo UNIX usando il sistema di comunicazione MPI. La valutazione del codice è stata effettuata su problemi test appositamente creati, che si differenziano sia per la posizione degli autovalori della matrice del problema lungo il semiasse reale positivo, sia per la dimensione del sistema di VIEs. Il numero dei processori utilizzato varia da 2 a 4. I valori ottenuti di speedup ed efficiency risentono in parte della precarietà della rete di comunicazione del software. Essi sono stati valutati sia rispetto al tempo richiesto dalla versione seriale dell'algoritmo progettato sia rispetto ad un codice basato sul metodo Runge-Kutta utilizzato come metodo underlying del WR accelerato. Dai risultati ottenuti, riportati tutti in tabelle, si evince che il codice risulta un efficiente integratore di sistemi a grandi dimensioni con matrici con spettro di ampiezza piccola e lontano dall'origine.