Risoluzione numerica di sistemi di equazioni integrali di Volterra a grandi dimensioni

Sistemi di equazioni integrali di Volterra (VIEs) a grandi dimensioni sono modello di molti problemi evolutori con memoria, in particolare di problemi di dinamica delle popolazioni, di diffusione di epidemie e di reazione-diffusione. Tali sistemi nascono anche dalla semidiscretizzazione lungo lo spazio di equazioni di Volterra- Fredholm, le quali descrivono, per esempio, problemi parabolici a valori al contorno e lo sviluppo spazio-temporale di epidemie. La risoluzione numerica di un sistema di VIEs è molto costosa dal punto di vista computazionale a causa della pesante presenza del lag term, che è il termine che raccoglie tutte le informazioni relative alla storia passata della soluzione e che deriva dal carattere ereditario delle VIEs. Questo problema si amplifica notevolmente quando le dimensioni del sistema sono elevate. In questi casi l’uso di calcolatori paralleli pu`o fornire una soluzione in tempi di calcolo ragionevoli. A tal fine negli ultimi anni sono stati proposti alcuni metodi paralleli. Molti di essi realizzano un tipo di parallelismo lungo il metodo e pertanto hanno un basso grado di parallelismo. Metodi dotati di un elevato grado di parallelismo, e dunque particolarmente adatti per risolvere problemi a grandi dimensioni, sono invece quelli che realizzano un tipo di parallelismo lungo il sistema. In tale ambito si è svolto il lavoro di tesi. La prima parte della tesi riguarda la risoluzione di un sistema di VIEs di tipo Abel a grandi dimensioni. Nonostante i sistemi di equazioni di Volterra di tipo Abel abbiano un ampio campo di applicazione, allo stato attuale il software disponibile per problemi Di questo tipo è molto esiguo. Per esempio, nella libreria di calcolo scientifico NAG, l’unico codice disponibile è D05BDF, il quale risolve per`o solo problemi di tipo scalare. Risulta pertanto di fondamentale importanza ampliare l’offerta di software per sistemi di questo tipo. Con questo scopo, la nostra ricerca è stata dedicata alla progettazione ed allo sviluppo su architetture a memoria distribuita del codice parallelo NSWR4 per la risoluzione di sistemi di VIEs di tipo Abel con nucleo di convoluzione lineare ed esponente 1/2. Il metodo implementato è un metodo iterativo Waveform Relaxation non stazionario (NSWR) discreto di tipo Richardson, basato su un metodo numerico frazionale lineare di ordine 4 a passo fisso. Questo metodo è pienamente parallelo e presenta proprietà di convergenza ottimali, per un’opportuna scelta dei parametri che caratterizzano il metodo. Al fine di migliorare l’efficienza dell’algoritmo abbiamo implementato il metodo NSWR di tipo Richardson sviluppando speciali strategie: per accelerare la convergenza abbiamo effettuato un riordinamento dei parametri che caratterizzano il metodo ed abbiamo impiegato la tecnica dello windowing. Inoltre, abbiamo introdotto la strategia delle finestre dinamiche, riducendo il numero complessivo di iterazioni effettuate e il numero di comunicazioni fra i processori. Per il calcolo del lag term abbiamo esteso a sistemi di equazioni di Volterra la tecnica a blocchi di lag, che fa uso dell’algoritmo della Fast Fourier Transform, nota nel caso di problemi di tipo scalare. Tale tecnica è stata implementata in parallelo nel codice NSWR4. Questa operazione ha migliorato molto l’efficienza dell’algoritmo implementato, in quanto ha ridotto il costo computazionale e ha permesso di effettuare in parallelo una delle fasi pi`u onerose dell’intero processo risolutivo. I metodi implementati e le strategie utilizzate hanno reso il codice NSWR4 molto efficiente, come hanno provato gli esperimenti numerici effettuati su significativi esempi test. E’ stata ottenuta una riduzione del numero di iterazioni rispetto al metodo stazionario che in alcuni casi supera il 50%. Inoltre, mediante test effettuati su un cluster di 4 Workstations IBM Risc 6000, abbiamo provato che il metodo gode di un elevato grado di parallelismo, in quanto i valori di Speed-up e di Efficienza tendono ai loro valori ’ideali’ all’aumentare della dimensione del problema. La seconda parte della tesi riguarda la risoluzione efficiente di equazioni di Volterra-Fredholm non lineari. Metodi numerici per la discretizzazione lungo lo spazio e lungo il tempo sono statiproposti da diversi autori, i quali, in ogni caso, hanno dovuto affrontare l’elevato costo computazionale della doppia discretizzazione. Tali discretizzazioni, infatti, conducono alla formulazione di sistemi non lineari la cui risoluzione, mediante il metodo di Newton, genera ad ogni passo temporale e ad ogni iterazione un sistema lineare denso, la cui dimensione dipende dalla mesh spaziale. La risoluzione di tali sistemi costituisce il termine predominante nel costo computazionale del processo risolutivo. Nella ricerca di un metodo che consenta di abbattere tale costo, il nostro punto di partenza sono i metodi di tipo Nystrom lungo lo spazio e di tipo Quadratura Diretta (DQ) lungo il tempo. Supponiamo che il dominio spaziale sia discretizzato con una griglia cubica uniforme di lato h, e che l’intervallo [0, T] sia discretizzato con una rete uniforme di punti. Allora la discretizzazione dell’equazione VFIE attraverso tali metodi conduce a sistemi non lineari, dipendenti dai pesi dei metodi Nystrom e DQ utilizzati, (Un)m rappresenta l’approssimazione di u(tn, xm). Abbiamo dimostrato, per il metodo (3), il seguente teorema di convergenza: Teorema 1 Sia (Un)m la soluzione numerica di (2) in (tn, xm) ottenuta con un metodo di Nystr¨om di ordine p e un metodo DQ di ordine q. Allora, se u è sufficientemente regolare, l’errore totale nei punti di rete soddisfa: |u(tn, xm) − (Un)m| = O(h^p) + O(tau^q). Il nostro approccio consiste nell’applicare un metodo iterativo interno non stazionario ad ogni iterazione del metodo di Newton applicato al sistema. Ogni iterazione interna richiede ancora la risoluzione di un sistema lineare ma le componenti della soluzione possono ora anche essere calcolate in parallelo. Di questo metodo abbiamo dimostrato la convergenza e abbiamo determinato una stima dell’errore, che consente di individuare i parametri (che caratterizzano il metodo) ottimali rispetto alla velocit`a di convergenza. Abbiamo dimostrato che, nei casi in cui il nucleo k risulta degenere di rango L rispetto alle variabili spaziali, l’errore del processo iterativo interno si annulla in L + 1 iterazioni. Questo risultato è molto importante, dato che è possibile approssimare qualunque nucleo continuo k con un nucleo degenere, usando tecniche standard. Per nuclei di tipo Hammerstein abbiamo determinato in che misura tale approssimazione influenza l’errore totale, dimostrando un teorema nel quale proviamo qual è l’errore totale dovuto all’approssimazione mediante nucleo degenere e la successiva discretizzazione mediante i metodi da noi introdotti. Alla luce di questo risultato è stato possibile determinare condizioni per cui l’approssimazione del nucleo non influenza l’errore totale del metodo ed inoltre riduce notevolmente il costo computazionale, sia in termini di operazioni floating point che di valutazioni di funzione. Gli esperimenti numerici realizzati su significativi esempi test hanno ampiamente confermato i risultati teorici sulla velocità di convergenza del metodo iterativo interno e sulla stima dell’errore totale. Inoltre, sperimentalmente si è osservato che il numero di iterazioni interne usate nella pratica per ottenere una accuratezza fissata è di solito inferiore a quello richiesto dai risultati teorici, con una conseguente riduzione del costo computazionale. Abbiamo inoltre considerato i metodi di tipo Collocazione lungo lo spazio e Quadratura Diretta lungo il tempo e applicato il nostro metodo risolutivo, pervenendo a risultati sia teorici che sperimentali analoghi a quelli ottenuti per i metodi Nystrom/DQ. Abbiamo quindi sviluppato un codice prototipale su architetture a memoria distribuita che utilizza il metodo proposto, basato su un metodo di tipo Nystrom/DQ di ordine 2 per la discretizzazione spazio-temporale. In tale codice sono state effettuati in parallelo sia la risoluzione dei sistemi, sia il calcolo delle componenti del lag term, sfruttando la sua natura vettoriale. Attraverso test sperimentali effettuati su un cluster di 4 Workstations IBM Risc 6000, abbiamo provato che l’algoritmo realizzato gode di un elevato grado di parallelismo, in quanto gi`a per discretizzazioni non eccessivamente raffinate sono stati ottenuti valori di Speed-up e di Efficienza vicini a quelli ideali.