mod_C

Ministero dell'Universita' e della Ricerca scientifica e tecnologica

Programmi di ricerca cofinanziati - Modello C
Rendiconto di unita' di ricerca - ANNO 1997
prot. 9701091751_025

1. Area Scientifico Disciplinare principale 01: Scienze matematiche

2. Coordinatore Scientifico del programma di ricerca

3. Titolo del programma di ricerca

ANALISI NUMERICA: METODI E SOFTWARE MATEMATICO

4. Responsabile Scientifico dell'Unità di ricerca

5. Titolo del programma dell'unità di ricerca

Software matematico per architetture avanzate

6. Settore principale del Programma di Ricerca: A04A - Analisi numerica

7. Finanziamenti assegnati all'unità di ricerca

8. Obiettivo della ricerca eseguita

L'obiettivo e` di produrre un insieme di elementi di software matematico direttamente utilizzabili nelle applicazioni.

9. Descrizione della Ricerca eseguita e dei risultati ottenuti

Con l'obiettivo di produrre un insieme di elementi di software matematico per architetture avanzate da 
utilizzare direttamente nelle applicazioni, l'attivita` scien-tifica e` stata rivolta allo studio di metodi 
esistenti, alla selezione di algoritmi piu` promettenti, allo sviluppo di nuovi metodi piu` efficienti, 
all'implementazione di questi in elementi di software matematico. In particolare i campi di interesse sono 
stati 

- Problemi inversi e applicazioni; 

- Algebra lineare numerica e applicazioni; 

- Quadratura multidimensionale e applicazioni; 

- Risoluzione di equazioni differenziali alle derivate parziali e applicazioni; 

- Problemi di ottimizzazione non lineare. 

Le attivita` svolte e i risultati ottenuti possono essere cosi` sintetizzati. 


- Problemi inversi e applicazioni. 

L'attivita` svolta e` stata rivolta alla progettazione di metodi numerici, algoritmi e software per la 
risoluzione di problemi inversi mal posti su calcolatori MIMD a memoria distribuita. In particolare, sono 
stati affrontati i seguenti problemi. 

* Il calcolo numerico dell'antitrasformata di Laplace (inversione reale). 

Sono stati proposti due metodi d'inversione. Il primo e` ottenuto sviluppando l'antitrasformata in 
serie di Fourier e approssimando i coefficienti di Fourier utilizzando tecniche di regolarizzazione 
alla Tikhonov. Il secondo e` basato su una opportuna generalizzazione al problema d'inversione 
reale, della formula d'inversione di Riemann. 

* La ricostruzione di immagini bidimensionali degradate e affette da rumore. 

E` stato prodotto un elemento di software parallelo per la risoluzione del sistema lineare 
derivante dalla discretizzazione di equazioni integrali di Fredholm di prima specie. Il software 
fa uso di BLACS per le operazioni di message-passing, delle routine di PBLAS per le operazioni di 
algebra lineare di base, e di una versione parallela della FWPT (Fast Wavelet Packet Transform) 
bidimensionale. 

* Eliminazione del rumore da un'immagine. 

Sono stati sviluppati moduli di software parallelo per la ricostruzione di immagini sfocate e 
perturbate. Il metodo risolutivo utilizza tecniche di regolarizzazione basate sul funzionale di 
Totale Variazione. Il software e` scritto in linguaggio C, utilizza MPI come sistema di 
comunicazione e versioni parallele della FFT-radix2. 


- Algebra lineare numerica e applicazioni. 

In tale settore l'interesse e` stato rivolto allo sviluppo di algoritmi paralleli, e relativo software, per 
alcuni problemi di base. In particolare, l'attivita` ha riguardato i seguenti campi. 

* Algoritmi sistolici ed ipersistolici per il calcolo di prodotti di matrici. 

Tali algoritmi sono stati implementati e testati su macchine parallele di tipo SIMD. 

* Calcolo degli autovalori di matrici sparse. 

In particolare per le matrici sparse non strutturate si sono studiate 
tecniche di riortogonalizzazione adatte a calcolatori paralleli a 
memoria distribuita. Per le matrici sparse strutturate (a banda) si 
sono studiati gli algoritmi esistenti e si e` implementato un primo 
nucleo computazionale per architetture parallele di tipo MIMD a memoria 
distribuita. 


- Quadratura multidimensionale e applicazioni. 

In tale campo l'attivita` di ricerca si e` rivolta al calcolo del valore attuale di alcuni titoli 
finanziari (Collaterized Mortgage Obbligations) mediante metodi Quasi Monte Carlo su architetture parallele 
a basso costo (sistemi Beowulf). La soluzione di tale problema finanziario e` rappresentata da un 
integrale in elevate dimensioni (valori tipici sono 240 e 360) e i metodi utilizzati riescono, in alcuni 
casi, a superare il problema della lenta convergenza dei tradizionali metodi Monte Carlo. Oltre a cio` si 
e` sviluppato un software parallelo per la quadratura multidimensionale basato su un algoritmo adattativo. 
Tali algoritmi sono noti per la loro capacita` di raggiungere un buon compromesso tra accuratezza e 
efficienza per problemi di tipo generale. Il nucleo computazionale e` rappresentato da una sequenza di 
formule monomiali innestate in grado di stimare l'errore di troncamento senza valutazioni di funzioni 
aggiuntive. IL software e` stato sviluppato in Fortran 77 con libreria di comunicazione BLACS. La 
documentazione interna ed esterna e` stata sviluppata secondo lo stile NAG. 


- Risoluzione di equazioni differenziali alle derivate parziali e applicazioni. 

In tale ambito, l'interesse e` stato rivolto allo sviluppo di algoritmi e software paralleli per 
simulazioni numeriche di fenomeni di inquinamento atmosferico. In particolare, in collaborazione con un 
gruppo di chimici ambientali dell'Universita` di Napoli ``Federico II'' e con la Facolta` di Scienze 
Ambientali dell'Istituto Universitario Navale, e` stato sviluppato il software parallelo {em Parallel 
Naples Airshed Model (PNAM)}, per la simulazione di episodi di inquinamento fotochimico su mesoscala, in 
ambienti computazionali MIMD a memoria distribuita. Il dominio di riferimento di tale software e` la 
Regione Campania. PNAM e` basato su un modello euleriano del trasporto e delle trasformazioni fotochimiche 
di inquinanti atmosferici, che conduce ad un sistema di equazioni di convezione-diffusione-reazione non 
lineari e stiff. La risoluzione numerica di tale sistema e` basata su uno splitting degli operatori, in 
cui l'avvezione e` separata dalla diffusione e dalla chimica, che sono invece accoppiate. Particolare 
attenzione e` stata dedicata alla risoluzione delle ODE stiff derivanti dall'applicazione del metodo delle 
linee all'operatore di diffusione-chimica; un confronto tra differenti solver ha condotto alla scelta del 
noto software VODE, basato su metodi BDF, opportunamente modificato per trarre vantaggio dalla struttura 
delle matrici Jacobiane che si presentano durante la risoluzione. L'implementazione parallela e` basata su 
una tecnica di partizionamento della griglia, con un bilanciamento dinamico del carico computazionale. 
PNAM e` scritto in Fortran 90 ed usa la libreria parallela RSL (Runtime System Library), basata su MPI, per 
l'implementazione della decomposizione della griglia computazionale, delle comunicazioni tra i processori e 
dell'algoritmo di bilanciamento del carico. Sono state eseguite simulazioni di episodi realistici di smog 
fotochimico, verificatisi nella Regione Campania, utilizzando un IBM SP disponibile al Centro di Ricerche 
per il Calcolo Parallelo e i Supercalcolatori (CPS) del CNR di Napoli. 


- Problemi di ottimizzazione non lineare. 

In tale ambito l'interesse e` stato rivolto allo studio di metodi e alla progettazione di algoritmi e 
software parallelo per la risoluzione di alcuni problemi di ottimizzazione non lineare su calcolatori MIMD 
a memoria distribuita. In particolare, sono stati affrontati i seguenti problemi. 

* Problemi di ottimizzazione convessa. 

L'attenzione e` stata rivolta ad un metodo di tipo row-action in cui, ad ogni iterazione, si ha un 
sottoproblema che consiste nel determinare il minimo della funzione obiettivo sottoposta a uno o due 
vincoli lineari di uguaglianza, i quali costituiscono una linearizzazione dei vincoli del problema 
di partenza. Relativamente a tale metodo sono state sviluppate e analizzate sia la versione a 
blocchi sia quella simultanea. E` stato sviluppato un elemento di software, in linguaggio Fortran e 
utilizzando routine della libreria LAPACK, per la risoluzione di problemi con funzione obiettivo 
quadratica e vincoli non lineari. 

* Programmazione quadratica con vincoli di bound. 

In tale ambito l'attivita` di ricerca e` rivolta sia a metodi basati sulla strategia active set sia 
a metodi bastati sulla strategia interior point. In particolare, sono stati sviluppati due elementi 
di software parallelo per il caso di problemi densi: il primo e` basato su un algoritmo che usa il 
metodo del Gradiente Proiettato per accelerare l'identificazione dell'active set ottimale; il 
secondo implementa un metodo interior point basato sull'idea di ridurre, ad ogni iterazione, una 
opportuna funzione logaritmica, in modo da garantire la convergenza dei punti interni alla 
soluzione. Il parallelismo e` introdotto al livello dei nuclei computazionali di algebra lineare. 
Il software, scritto in FORTRAN, e` stato sviluppato utilizzando il sistema di comunicazione BLACS e 
la libreria ScaLapack.

10. Pubblicazioni

11. Prodotti della Ricerca eseguita

I prodotti piu` significativi della ricerca eseguita sono i seguenti: 

- Problemi inversi e applicazioni. 

E` stato sviluppato un elemento di software per l'inversione numerica della trasformata di 
Laplace (caso reale). Il software e` scritto in Fortran 77. Inoltre, e` stato sviluppato un 
elemento di software parallelo per la Fast Wavelet Transform su calcolatori MIMD a memoria 
distribuita. Il software e` scritto in linguaggio C e utilizza il sistema di comunicazione 
BLACS. 

Riferimenti bibliografici: 

L. D'Amore, G. Laccetti, A. Murli - An Implementation of a Fourier Series Method for the 
Numerical Inversion of the Laplace Transform - ACM TOMS, vol. 25, n. 3, 1999, pp. 279-305. 

S. Corsaro, L. D'Amore, A. Murli - On the Parallel Implementation of the Fast Wavelet Packet 
Transform on MIMD Distributed Memory Environments - Lecture Notes in Computer Science 1557, P. 
Zinterhof et al. eds., Springer, 1999, pp. 257-366. 


- Quadratura multidimensionale e applicazioni 

E` stato sviluppato un elemento di software parallelo per calcolatori MIMD a memoria distribuita, 
utilizzando il linguaggio Fortran 77 e la libreria di comunicazione BLACS. Il software e` 
corredato di documentazione interna ed esterna. 

Riferimento bibliografico: 

G. Laccetti , M. Lapegna - PAMIHR: A Parallel FORTRAN Program for Multidimensional Quadrature 
on Distributed Memory Architectures - Lecture Notes on Computer Science 1685, P. Amestoy et al. 
eds, Springer Verlag, 1999, pp. 1144-1148. 


- Risoluzione di equazioni differenziali alle derivate parziali e aplicazioni. 

E` stato sviluppato il software Parallel Naples Airshed Model (PNAM), per la simulazione di 
episodi di inquinamento fotochimico su mesoscala, in ambienti computazionali MIMD a memoria 
distribuita. E' scritto in Fortran 90 ed utilizza la Runtime System Library (RSL), sviluppata 
all'Argonne National Laboratory, basata a sua volta su MPI. 

Riferimento bibliografico: 

G. Barone, P. D'Ambra, D. di Serafino, G. Giunta, A. Murli, A. Riccio - Parallel Numerical 
Simulation of Air Pollution in Southern Italy - in Large-Scale Computations in Air Pollution 
Modelling, Z. Zlatev et al. eds., Kluwer, 1999, pp. 39-52. 


- Problemi di ottimizzazione non lineare. 

Sono stati sviluppati due elementi di software parallelo per la risoluzione di problemi di 
programmazione quadratica convessa con vincoli di bound su calcolatori MIMD a memoria 
distribuita. Il software e' scritto in Fortran 77 ed utilizza il sistema di comunicazione BLACS 
e la libraria ScaLAPACK. 

Riferimenti bibliografici: 

M. D'Apuzzo, V. De Simone, M. Marino, G. Toraldo - Modifying the Cholesky Factorization on 
MIMD Distributed Memory Machines - in High Performance Algorithms and Software in Nonlinear 
Optimization - R. De Leone, A. Murli, P.M. Pardalos, G. Toraldo (Eds.), Kluwer Academic 
Publishers, 1998, pp. 125-141. 

M. D'Apuzzo, M. Marino, P.M. Pardalos, G. Toraldo - A Parallel Implementation of a Potential 
Reduction Algorithm for Box-Constrained Quadratic Programming - Centro di Ricerche per il Calcolo 
Parallelo e i Supercalcolatori, Tech. Rep. TR-2000-2, 2000 (in corso di stampa su Lecture Notes 
on Computer Science).

12. Componenti dell'Unità di ricerca che hanno effettivamente partecipato alla ricerca
Personale docente

Altro personale

Personale a contratto

13. Note relative ai componenti (p.12)

14. Risorse umane complessivamente ed effettivamente impegnate

15. Dati complessivi relativi al programma

16. Tabella delle spese sostenute: cifre spese, rimaste da pagare o impegnate(*)
(*) Da Impegnare LIMITATAMENTE a Pubblicazioni e Partecipazioni a Convegni e Congressi SOLAMENTE se inerenti i risultati della Ricerca cofinanziata per i quali si richiedera' successiva rendicontazione

Si ricorda che ogni variazione rispetto al Programma Iniziale sulla composizione delle Unità Operative e sulla diversa utilizzazione dei Fondi, doveva essere comunicata al Dipartimento Affari Economici come da nota n. 1709 del 22.7.98.

(per la copia da depositare presso l’Ateneo e per l’assenso alla diffusione via Internet delle informazioni riguardanti i programmi finanziati legge del 31.12.96 n° 675 sulla "Tutela dei dati personali")